Настройка блочно-параллельного алгоритма поиска кратких путей на эффективную многоядерную реализацию

Поиск кратчайших путей во взвешенном графе — одна из ключевых задач компьютерных наук, которая имеет множество практических приложений в различных областях. В данной работе анализируется блочно-параллельный алгоритм поиска кратчайших путей с целью оценки влияния многоядерной системы и ее иерархической кэш-памяти на параметры реализации алгоритма в зависимости от размера графа и размера блока матрицы расстояний. В ней предлагается метод настройки размера блока на особенности многоядерной системы. Метод предполагает использование инструментов профилирования в процессе настройки и позволяет увеличить производительность параллельного алгоритма. Вычислительные эксперименты, проведенные на стоечном сервере, оснащенном двумя процессорами Intel Xeon E5-2620 v4, состоящих из 8 ядер и 16 аппаратных потоков каждый, убедительно показали для различных размеров графов, что поведение и параметры работы иерархической кэш-памяти слабо зависят от размера графа и определяются размером блока матрицы расстояний. Чтобы настроить алгоритм на целевую многоядерную систему, предпочтительный размер блока может быть найден один раз для графа, размер представления которого превышает размер кэша, совместно используемого ядрами процессора. После этого найденный размер блока можно многократно использовать для эффективного решения задачи о кратчайших путях на графах большего размера.

1. Schrijver, A. On the history of the shortest path problem / A. Schrijver // Documenta Mathematica. – 2012. – Vol. 17, №. 1. – P. 155–167.

2. Anu, P. Finding All-Pairs Shortest Path for a Large-Scale Transportation Network Using Parallel Floyd-Warshall and Parallel Dijkstra Algorithms / P. Anu, M. G. (Kumar) // Journal of Computing in Civil Engineering. – 2013. – Vol. 27, №. 3. – P. 263–273.

3. Atachiants, R. Parallel Performance Problems on Shared-Memory Multicore Systems: Taxonomy and Observation / R. Atachiants, G. Doherty, D. Gregg // IEEE Transactions on Software Engineering. – 2016. – Vol. 42, №. 8. – P. 764–785.

4. Zheng, Y. Performance evaluation of exclusive cache hierarchies / Y. Zheng, B. T. Davis, M. Jordan. – 2004. – P. 89–96.

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

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

7. Park, J. Optimizing graph algorithms for improved cache performance / J. Park, M. Penner, V. K. Prasanna // IEEE Transactions on Parallel and Distributed Systems. – 2004. – Vol. 15, №. 9. – P. 769–782.

8. Floyd, R. W. Algorithm 97: Shortest Path / R. W. Floyd // Communications of the ACM. – 1962. – Vol. 5, №. 6. – P. 345-.

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

10. Albalwi, E. Task Level Parallelization of All Pair Shortest Path Algorithm in OpenMP 3.0 / E. Albalwi, P. Thulasiraman, R. Thulasiram // Advances in Computer Science and Engineering (CSE 2013), Los Angeles. – Los Angeles: Atlantis Press, 2013. – P. 109–112.

11. Tang, P. Rapid development of parallel blocked all-pairs shortest paths code for multi-core computers / P. Tang // IEEE SOUTHEASTCON 2014, Lexington, KY, USA. – Lexington, KY, USA: IEEE, 2014. – P. 1–7.

12. Singh, A. Performance Analysis of Floyd Warshall Algorithm vs Rectangular Algorithm / A. Singh, P. K. Mishra // International Journal of Computer Applications. – 2014. – Vol. 107, №. 16. – P. 23–27.

13. An Experimental Study of a Parallel Shortest Path Algorithm for Solving Large-Scale Graph Instances / K. Madduri [et al.] // 2007 Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX). – Society for Industrial and Applied Mathematics, 2007. – P. 23–35.

14. Карасик, О. Н. Кооперативный многопоточный планировщик и блочно-параллельные алгоритмы решения задач на многоядерных системах / О. Н. Карасик. – Белорусский государственный университет информатики и радиоэлектроники, 2019.

15. Карасик, О. Н. Потоковый блочно-параллельный алгоритм поиска кратчайших путей на графе / О. Н. Карасик, А. А. Прихожий // Доклады БГУИР. – 2018. – №. 2. – С. 77–84.

16. Прыхожы, А. А. Кааператыўныя блочна-паралельныя алгарытмы рашэння задач на шмат’ядравых сістэмах / А. А. Прыхожы, А. М. Карасік // Сістэмны аналіз і прыкладная інфарматыка. – 2015. – №. 2. – С. 10–18.

17. Прихожий, А.А. Моделирование кэш прямого отображениея и ассоциативных кэш на алгоритмах поиска кратчайших путей на графе / А.А. Прихожий // Системный анализ и прикладная информатика. – 2019. – No. 4. – С. 10–18.

18. Prihozhy, А. Inference of shortest path algorithms with spatial and temporal locality for Big Data processing / А. Prihozhy, O. Karasik // Big Data and Advanced Analytics: сб. материалов VIII Междунар. науч.-практ. конф., Минск, 11-12 мая 2022. – Минск: Беспринт, 2022. – P. 56–66.

19. Intel Corporation. Allow Multiple Runs or Multiplex Events [Electronic resource]. – Mode of access: URL: https://www.intel.com/content/www/us/en/develop/documentation/vtune-help/top/analyze-performance/hw-event-based-sampling-collection/allow-multiple-runs-or-multiplex-events.html. – Date of access: 07.03.2022.

20. Intel Corporation. Hardware Event-based Sampling Collection [Electronic resource]. – Mode of access: URL: https://www.intel.com/content/www/us/en/develop/documentation/vtune-help/top/analyze-performance/hw-event-based-sampling-collection.html – Date of access: 07.03.2022).