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


https://doi.org/10.21122/2309-4923-2019-4-10-18

Полный текст:


Аннотация

Кэш способен использовать временную и пространственную локальность данных во время выполнения программы. Когда процессор обращается к памяти, поведение кэш зависит от того, находятся ли данные в нем: попадание в кэш происходит, если данные там, в противном случае, имеет место промах кэш. В последнем случае кэш может потребоваться удалить другие данные. Промахи приводят к остановке процессора и замедляют вычисления. Стратегия замены выбирает данные для удаления, пытаясь предсказать будущие обращения к памяти. Частота попаданий и промахов зависит от типа кэш: прямого сопоставления, множественно-ассоциативный и полностью ассоциативный кэш. Стратегия удаления наименее недавно использованных данных обслуживает множества слотов. Уровень промахов сильно зависит от выполняемого алгоритма. Алгоритмы поиска кратчайших путей между всеми парами вершин графа решают многие практические задачи, и важно знать, какой алгоритм и какой тип кэш лучше подходят друг другу. В этой статье представлен метод моделирования кэш прямого отображения, 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.


Дополнительные файлы

Для цитирования: Прихожий А.А. Моделирование кэш прямого отображения и ассоциативных кэш на алгоритмах поиска кратчайших путей в графе. «Системный анализ и прикладная информатика». 2019;(4):10-18. https://doi.org/10.21122/2309-4923-2019-4-10-18

For citation: 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. https://doi.org/10.21122/2309-4923-2019-4-10-18

Просмотров: 30

Обратные ссылки

  • Обратные ссылки не определены.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2309-4923 (Print)
ISSN 2414-0481 (Online)