Прихожий Анатолий Алексеевич – профессор кафедры программного обеспечения вычислительной техники и автоматизированных систем, доктор технических наук, профессор
Anatoly Prihozhy, doctor of science, professor, Computer and system software department
Minsk
Статья посвящена сокращению обмена данными между основной памятью и кэш прямого сопоставления при выполнении блочных алгоритмов поиска кратчайших путей, представляющих данные матрицей блоков D[M×M]. Для больших графов размер кэш S = d×M2, d < 1 меньше размера матрицы. Кэш назначает группу блоков основной памяти на один блок кэш. Алгоритмы пересчитывают блок матрицы через один или два других блока и могут обращаться сразу к трем блокам. Если эти блоки назначены на один блок кэш, между ними возникает конфликт, приводящий к активному обмену данными между уровнями памяти. Распределение блоков по группам и число конфликтов сильно зависят от размещения и упорядочения блоков матрицы в основной памяти. В статье предлагается решать проблему оптимального размещения на взвешенном графе конфликтов блоков и различать два случая назначения блоков на кэш: бесконфликтного и минимально-конфликтного. В первом случае формулируется проблема равномерной раскраски графа конфликтов, предлагаются детерминированный и случайный алгоритмы ее решения. Во втором случае формулируется проблема взвешенной дефектной раскраски графа при ограничении на число цветов, предлагается случайный алгоритм ее решения. Экспериментальные результаты показывают, что случайный алгоритм равномерной раскраски дает верхнюю границу размера кэш очень близкую к нижней границе, оцениваемой через полный подграф, и показывает, что бесконфликтное размещение матрицы возможно при d = 0.5 для M = 4 и при d = 0.1 для M = 20. Для малого размера кэш взвешенный дефектный алгоритм дает число оставшихся конфликтов до 8.8 раз меньшее чем начальное размещение. Предложенные модель и алгоритмы применимы также к k-канальному ассоциативному кэш.
This paper is devoted to the reduction of data transfer between the main memory and direct mapped cache for blocked shortest paths algorithms (BSPA), which represent data by a D[M×M] matrix of blocks. For large graphs, the cache size S = δ×M2, δ < 1 is smaller than the matrix size. The cache assigns a group of main memory blocks to a single cache block. BSPA performs multiple recalculations of a block over one or two other blocks and may access up to three blocks simultaneously. If the blocks are assigned to the same cache block, conflicts occur among the blocks, which imply active transfer of data between memory levels. The distribution of blocks on groups and the block conflict count strongly depends on the allocation and ordering of the matrix blocks in main memory. To solve the problem of optimal block allocation, the paper introduces a block conflict weighted graph and recognizes two cases of block mapping: non-conflict and minimum-conflict. In first case, it formulates an equitable color-class-size constrained coloring problem on the conflict graph and solves it by developing deterministic and random algorithms. In second case, the paper formulates a problem of weighted defective color-count constrained coloring of the conflict graph and solves it by developing a random algorithm. Experimental results show that the equitable random algorithm provides an upper bound of the cache size that is very close to the lower bound estimated over the size of a complete subgraph, and show that a non-conflict matrix allocation is possible at δ = 0.5 for M = 4 and at δ = 0.1 for M = 20. For a low cache size, the weighted defective algorithm gives the number of remaining conflicts that is up to 8.8 times less than the original BSPA gives. The proposed model and algorithms are applicable to set-associative cache as well.
The authors declare that there are no conflicts of interest present.