sapiСистемный анализ и прикладная информатика«System analysis and applied information science»2309-49232414-0481Belarusian National Technical University10.21122/2309-4923-2022-3-57-65sapi-582Research ArticleОбработка информации и принятие решенийData processing and decision–makingНастройка блочно-параллельного алгоритма поиска кратких путей на эффективную многоядерную реализациюTuning block-parallel all-pairs shortest path algorithm for efficient multi-core implementationКарасикО. Н.KarasikO. N.

Карасик Олег, технический директор компании ISsoft Solutions (часть Coherent Solutions) в Минске, кандидат технических наук

Минск

Karasik Oleg, Technology Lead at ISsoft Solutions (part of Coherent Solutions) in Minsk, Belarus, and PhD in Technical Science

 Minsk

ПрихожийА. А.PrihozhyA. A.

Анатолий Прихожий, профессор кафедры Программное обеспечение информационных систем и технологий, доктор технических наук, профессор

Минск

Anatoly Prihozhy, full professor at the Computer and system software department of Belarus national technical university, doctor of science and full professor

Minsk

Белорусский национальный технический университетБеларусьBelarusian National Technical UniversityBelarus202206122022035765Copyright © Карасик О.Н., Прихожий А.А., 20222022Карасик О.Н., Прихожий А.А.Karasik O.N., Prihozhy A.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://sapi.bntu.by/jour/article/view/582

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

Finding shortest paths in a weighted graph is one of the key problems in computer-science, which has numerous practical applications in multiple domains. This paper analyzes the parallel blocked all-pairs shortest path algorithm at the aim of evaluating the influence of the multi-core system and its hierarchical cache memory on the parameters of algorithm implementation depending on the size of the graph and the size of distance matrix’s block. It proposes a technique of tuning the block-size to the given multi-core system. The technique involves profiling tools in the tuning process and allows the increase of the parallel algorithm throughput. Computational experiments carried out on a rack server equipped with two Intel Xeon E5-2620 v4 processors of 8 cores and 16 hardware threads each have convincingly shown for various graph sizes that the behavior and parameters of the hierarchical cache memory operation don’t depend on the graph size and are determined only by the distance matrix’s block size. To tune the algorithm to the target multi-core system, the preferable block size can be found once for the graph size whose in-memory matrix representation is larger than the size of cache shared among all processor’s cores. Then this blocksize can be reused on graphs of bigger size for efficient solving the all-pairs shortest path problem

кратчайший путьалгоритм Флойда-Уоршеллаблочный алгоритммногопоточный алгоритммногопроцессорная системаиерархическая кэш памятьпараллелизмshortest pathFloyd-Warshall algorithmblocked algorithmmultithreaded applicationmulti-core systemhierarchical cache memoryparallelismthroughput.ReferencesSchrijver, A. On the history of the shortest path problem / A. Schrijver // Documenta Mathematica. – 2012. – Vol. 17, №. 1. – P. 155–167.Schrijver, A. On the history of the shortest path problem / A. Schrijver // Documenta Mathematica. – 2012. – Vol. 17, №. 1. – P. 155–167.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.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.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.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.Zheng, Y. Performance evaluation of exclusive cache hierarchies / Y. Zheng, B. T. Davis, M. Jordan. – 2004. – P. 89–96.Zheng, Y. Performance evaluation of exclusive cache hierarchies / Y. Zheng, B. T. Davis, M. Jordan. – 2004. – P. 89–96.Прихожий А.А., Карасик О.Н. Исследование методов реализации многопоточных приложений на многоядерных системах // Информатизация образования, 2014, № 1, с. 43–62.Prihozhy, A.A. Investigation of methods for implementing multithreaded applications on multicore systems / A.A. Prihozhy, O.N. Karasik // Informatization of education. – 2014. – No. 1. – P. 43–62.Прихожий А.А., Карасик О.Н. Кооперативная модель оптимизации выполнения потоков на многоядерной системе // Системный анализ и прикладная информатика, 2014, № 4, с. 13–20.Prihozhy, A.A. Cooperative model for optimization of execution of threads on multi-core system / A.A. Prihozhy, O.N. Karasik // System analysis and applied information science. – 2014. – No. 4. – P. 13–20.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.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.Floyd, R. W. Algorithm 97: Shortest Path / R. W. Floyd // Communications of the ACM. – 1962. – Vol. 5, №. 6. – P. 345-.Floyd, R. W. Algorithm 97: Shortest Path / R. W. Floyd // Communications of the ACM. – 1962. – Vol. 5, №. 6. – P. 345-.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.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.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.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.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.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.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.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.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.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.Карасик, О. Н. Кооперативный многопоточный планировщик и блочно-параллельные алгоритмы решения задач на многоядерных системах / О. Н. Карасик. – Белорусский государственный университет информатики и радиоэлектроники, 2019.Karasik, O.N. Cooperative multi-threaded scheduler and block-parallel algorithms of solving tasks on multi-core systems / O.N. Karasik. – Belarusian state university of informatics and radio-electronics, 2019.Карасик, О. Н. Потоковый блочно-параллельный алгоритм поиска кратчайших путей на графе / О. Н. Карасик, А. А. Прихожий // Доклады БГУИР. – 2018. – №. 2. – С. 77–84.Karasik, O.N. Threaded block-parallel algorithm for finding the shortest pats on graph / O.N. Karasik, A.A. Prihozhy // Doklady BGUIR. – 2018. – No. 2. – P. 77–84.Прыхожы, А. А. Кааператыўныя блочна-паралельныя алгарытмы рашэння задач на шмат’ядравых сістэмах / А. А. Прыхожы, А. М. Карасік // Сістэмны аналіз і прыкладная інфарматыка. – 2015. – №. 2. – С. 10–18.Prihozhy, A.A. Cooperative block-parallel algorithms for task execution on multi-core system / A.A. Prihozhy, O.N. Karasik // System analysis and applied information science. – 2015. – No. 2. – P. 10–18.Прихожий, А.А. Моделирование кэш прямого отображениея и ассоциативных кэш на алгоритмах поиска кратчайших путей на графе / А.А. Прихожий // Системный анализ и прикладная информатика. – 2019. – No. 4. – С. 10–18.Prihozhy, A.A. Simulation of direct mapped, k-way and fully associative cache on all pairs shortest paths algorithms / A.A. Prihozhy // System analysis and applied information science. – 2019. – No. 4. – P. 10–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.Prihozhy, А.A. Inference of shortest path algorithms with spatial and temporal locality for Big Data processing / A.A. Prihozhy, O.N. Karasik // Big Data and Advanced Analytics: Proc. VIII Intern. Conf., Minsk, May 11-12, 2022. – Minsk: Bestprint, 2022. – P. 56–66.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.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.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).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).

The authors declare that there are no conflicts of interest present.