Моделирование кэш прямого отображения и ассоциативных кэш на алгоритмах поиска кратчайших путей в графе

Кэш способен использовать временную и пространственную локальность данных во время выполнения программы. Когда процессор обращается к памяти, поведение кэш зависит от того, находятся ли данные в нем: попадание в кэш происходит, если данные там, в противном случае, имеет место промах кэш. В последнем случае кэш может потребоваться удалить другие данные. Промахи приводят к остановке процессора и замедляют вычисления. Стратегия замены выбирает данные для удаления, пытаясь предсказать будущие обращения к памяти. Частота попаданий и промахов зависит от типа кэш: прямого сопоставления, множественно-ассоциативный и полностью ассоциативный кэш. Стратегия удаления наименее недавно использованных данных обслуживает множества слотов. Уровень промахов сильно зависит от выполняемого алгоритма. Алгоритмы поиска кратчайших путей между всеми парами вершин графа решают многие практические задачи, и важно знать, какой алгоритм и какой тип кэш лучше подходят друг другу. В этой статье представлен метод моделирования кэш прямого отображения, k-канального ассоциативного и полностью ассоциативного кэш во время выполнения алгоритма, для измерения частоты чтения данных в кэш и записи данных в память. Мы измерили частоты в зависимости от размера кэш, размера блока данных, объема обработанных данных, типа кэш и типа алгоритма. После сравнения основного и блочного алгоритмов Флойда-Уоршелла, мы пришли к выводу, что блочный алгоритм хорошо локализует доступ к данным внутри одного блока, но не локализует зависимости данных между блоками. Кэш прямого отображения значительно уступает ассоциативным кэш; мы можем улучшить его производительность путем соответствующего отображения виртуальных адресов на физические адреса памяти.

1. Kozyrakis C. “Computer Systems Architecture. Advanced Caching Techniques”, Stanford University, pp. 1-35, 2012. [Online]. Available: https://web.archive.org/web/20120907012034/http://www.stanford.edu/class/ee282/08_handouts/L03-Cache.pdf.:

2. Mittal S. “A Survey of Techniques for Architecting TLBs”, Concurrency and computation: practice and experience, pp. 1-35. 2016. [Online]. Available: https://www.researchgate.net/publication/309583874_A_Survey_of_Techniques_for_Architecting_TLBs.

3. Hennessy J. L., Patterson D.A. “Computer Architecture. A Quantitative Approach”. Elsevier, Amsterdam, 2012, 857 p.

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

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

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

7. Prihozhy A., Mattavelli M. and Mlynek D. “Data Dependences Critical Path Evaluation at C/C++ System Level Description”, Chapter in Book “Integrated Circuit and System Design. Power and Timing Modeling, Optimization and Simulation”, LNCS 2799, Springer, 2003, pp.569-579.

8. Prihozhy A. “Analysis, transformation and optimization for high performance parallel computing”, Technical literature, Minsk, 2019. – 229 p.