Оптимизация размещения данных в иерархической памяти для блочных алгоритмов поиска кратчайших путей

Статья посвящена сокращению обмена данными между основной памятью и кэш прямого сопоставления при выполнении блочных алгоритмов поиска кратчайших путей, представляющих данные матрицей блоков D[M×M]. Для больших графов размер кэш S = d×M2, d < 1 меньше размера матрицы. Кэш назначает группу блоков основной памяти на один блок кэш. Алгоритмы пересчитывают блок матрицы через один или два других блока и могут обращаться сразу к трем блокам. Если эти блоки назначены на один блок кэш, между ними возникает конфликт, приводящий к активному обмену данными между уровнями памяти. Распределение блоков по группам и число конфликтов сильно зависят от размещения и упорядочения блоков матрицы в основной памяти. В статье предлагается решать проблему оптимального размещения на взвешенном графе конфликтов блоков и различать два случая назначения блоков на кэш: бесконфликтного и минимально-конфликтного. В первом случае формулируется проблема равномерной раскраски графа конфликтов, предлагаются детерминированный и случайный алгоритмы ее решения. Во втором случае формулируется проблема взвешенной дефектной раскраски графа при ограничении на число цветов, предлагается случайный алгоритм ее решения. Экспериментальные результаты показывают, что случайный алгоритм равномерной раскраски дает верхнюю границу размера кэш очень близкую к нижней границе, оцениваемой через полный подграф, и показывает, что бесконфликтное размещение матрицы возможно при d = 0.5 для M = 4 и при d = 0.1 для M = 20. Для малого размера кэш взвешенный дефектный алгоритм дает число оставшихся конфликтов до 8.8 раз меньшее чем начальное размещение. Предложенные модель и алгоритмы применимы также к k-канальному ассоциативному кэш.

1. R. W. Floyd “Algorithm 97: Shortest path”, Communications of the ACM, 1962, 5(6), p. 345.

2. Hofner, P. Dijkstra, Floyd and Warshall Meet Kleene / P. Hofner and B. Moller // Formal Aspect of Computing, Vol. 24, No. 4, 2012, № 2, pp. 459–476.

3. G. Venkataraman, S. Sahni, S. Mukhopadhyaya “A Blocked All-Pairs Shortest Paths Algorithm”, Journal of Experimental Algorithmics (JEA), Vol 8, 2003, pp. 857–874

4. Прихожий, А. А. Разнородный блочный алгоритм поиска кратчайших путей между всеми парами вершин графа / А. А. Прихожий, О. Н. Карасик // Системный анализ и прикладная информатика. – № 3. – 2017. – С. 68–75.

5. C. Kozyrakis “Computer Systems Architecture. Advanced Caching Techniques”, Stanford University, pp. 1–35, 2012.

6. Smith, A.J. “Cache Memories”, Computing Surveys. 1982, 14 (3): 473–530.

7. J. S. Park, M. Penner, and V. K. Prasanna “Optimizing graph algorithms for improved cache performance” / J. S. Park, // IEEE Trans. on Parallel and Distributed Systems, 2004, 15(9), pp.769–782.

8. Prihozhy A.A. Simulation of direct mapped, k-way and fully associative cache on all pairs shortest paths algorithms. «System analysis and applied information science». 2019; (4):10–18.

9. Solomonik, E. Minimizing Communication in All Pairs Shortest Paths / E. Solomonik, A. Buluc, and J. Demmel // IEEE 27th International Symposium on Parallel & Distributed Processing, 2013, pp. 548–559.

10. Tang, P. Rapid Development of Parallel Blocked All-Pairs Shortest Paths Code for Multi-Core Computers / P. Tang // IEEE SOUTHEASTCON 2014, pp. 1–7.

11. Прихожий, А. А. Адаптивное управление памятью / А. А. Прихожий // Автоматика и вычислительная техника, 1988, № 3, с. 58–65

12. Prihozhy, A.A. Asynchronous scheduling and allocation / A.A. Prihozhy / Proceedings Design, Automation and Test in Europe. Paris, France. – IEEE, 1998, pp. 963–964.

13. Прихожий, А. А. Исследование методов реализации многопоточных приложений на многоядерных системах / А. А. Прихожий, О. Н. Карасик // Информатизация образования, 2014, № 1, с. 43–62.

14. Прихожий, А. А. Кооперативная модель оптимизации выполнения потоков на многоядерной системе / А. А. Прихожий, О. Н. Карасик // Системный анализ и прикладная информатика, 2014, № 4, с. 13–20.

15. Chaitin, G. J. “Register allocation & spilling via graph colouring”, Proc. 1982 SIGPLAN Symposium on Computer Construction, 1982, pp. 98–105.

16. Bodlaender, H.L., Fomin, F.V. “Equitable colorings of bounded treewidth graphs”, Theoretical Computer Science, 2005, 349 (1): 22–30.

17. Hajnal, A., Szemeredi E. “Proof of a conjecture of P. Erdős”, Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), North-Holland, 1970, pp. 601–623

18. Cowen, L. J., Cowen, R. H., Woodall, D. R. “Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency”. Journal of Graph Theory, 2006, 10 (2): 187–195.