Конкурирующие алгоритмы поиска кратчайших путей между всеми парами вершин разреженных / плотных графов: реализация и сравнение

В статье рассматриваются два семейства конкурирующих алгоритмов поиска кратчайших путей между всеми парами вершин (APSP) в ориентированных взвешенных больших графах с различной плотностью ребер: Дейкстры и Флойда-Уоршелла. Для сравнения мы взяли алгоритм Дейкстры с динамически изменяемой двоичной кучей, который решает задачу APSP чисто параллельно путем многократного выполнения на всех вершинах графа, рассматриваемых в качестве исходных, и взяли блочный алгоритм Флойда-Уоршелла, который также является хорошо распараллеливаемым. Известно, что с точки зрения вычислительной сложности первый алгоритм предпочтительнее на разреженных графах, а второй – на плотных. В то же время неясно, каковы диапазоны плотностей графов, при которых первый алгоритм будет потреблять процессорное время, меньшее, чем второй алгоритм. В статье описаны реализации многопоточных параллельных алгоритмов на многоядерных процессорах, которые по-разному используют такие примитивы синхронизации, как мьютекс, условная переменная, блокировка и атомарная операция. Проведя вычислительные эксперименты на 8-ядерном процессоре Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz, мы обнаружили, что каждый алгоритм имеет предпочтительную плотность графов. В случае многопоточной параллельной реализации блочный алгоритм Флойда-Уоршелла имеет меньшее время работы, чем алгоритм Дейкстры, если плотность графа больше 0,5. В противном случае алгоритм Дейкстры работает быстрее. В случае однопоточной реализации точка разделения – 0,43.

разреженный граф, плотный граф, задача APSP, алгоритмы семейства Дейкстры, алгоритмы семейства Флойда-Уоршелла, многоядерный процессор, многопоточная реализация, сравнение

1. Madkour A., Aref W.G., Rehman F.U., Rahman M.A., Basalamah S. A Survey of Shortest-Path Algorithms. ArXiv: 1705.02044v1 [cs.DS], 4 May 2017, 26 p.

2. Dijkstra E.W. A note on two problems in connexion with graphs. Numerische Mathematik, 1959, vol. 1, no. 1, pp. 269-271.

3. Bellman R.E. On a routing problem. Quarterly of Applied Mathematics, 1958, vol. 16, no. 1, pp. 87-90.

4. Johnson D.B. Efficient Algorithms for Shortest Paths in Sparse Networks. J. ACM, 1977, vol. 24, no. 1, pp. 1-13.

5. Harish P., Narayanan P.J. Accelerating large graph algorithms on the GPU using CUDA. International conference on high-performance computing. Springer, 2007, pp. 197-208.

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

7. Katz G.J., Kider J.T. All-pairs shortest paths for large graphs on the GPU. GH’08: Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware. ACM, 2008, pp. 47-55.

8. Djidjev H., Thulasidasan S., Chapuis G., Andonov R. and Lavenier D. Efficient multi-GPU computation of all-pairs shortest paths. IEEE 28th International Parallel and Distributed Processing Symposium. IEEE, 2014, pp. 360-369.

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

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

11. Yang S., Liu X., Wang Y., He X., Tan G. Fast All-Pairs Shortest Paths Algorithm in Large Sparse Graph. ICS '23: Proceedings of the 37th International Conference on Supercomputing, 2023, pp. 277–288.

12. Прихожий А.А., Карасик О.Н. Усовершенствованный разнородный блочно-параллельный алгоритм поиска кратчайших путей на графе. Труды БГТУ. Сер. 3, Физико-математические науки и информатика, 2023, № 1 (266), с. 77-83.

13. Прихожий А.А., Карасик О.Н. Новые блочные алгоритмы поиска кратчайших путей между всеми парами вершин графа, работающие на блоках неравных размеров. Системный анализ и прикладная информатика. 2023, № 4, с. 4-13.

14. Карасик О.Н., Прихожий А.А. Блочный алгоритм поиска кратчайших путей между всеми парами вершин в графах со слабосвязанными кластерами. Системный анализ и прикладная информатика. 2024, № 2, с. 4-10.

15. Prihozhy А.A., Karasik O.N. Inference of shortest path algorithms with spatial and temporal locality for big data processing. Big Data and Advanced Analytics: сборник научный статей VIII Международной научно-практической конференции, Минск, 11-12 мая 2022 года. Минск, БГУИР, 2022, с. 56-66.

16. Карасик О.Н., Прихожий А.А. Настройка блочно-параллельного алгоритма поиска кратких путей на эф-фективную многоядерную реализацию. Системный анализ и прикладная информатика. 2022, № 3, с. 57-65.

17. Прихожий А.А. Генерация потоковых сетей акторов поиска кратчайших путей для параллельной многоядерной реализации. Информатика, 2023, № 2, с. 65-84.

18. Прихожий А.А. Оптимизация размещения данных в иерархической памяти для блочных алгоритмов поиска кратчайших путей. Системный анализ и прикладная информатика, 2021, no. 3, с. 40-50.

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

20. Прихожий А.А., Карасик О.Н. Влияние алгоритмов поиска кратчайших путей на энергопотребление многоядерных процессоров. Системный анализ и прикладная информатика, 2023, № 2, с. 4-12.