Ускорение и анализ производительности алгоритмов поиска кратчайшего пути на GPU с использованием платформы CUDA: алгоритмы Беллмана–Форда, Дейкстры и Флойда–Уоршелла

Вычислительные требования к алгоритмам поиска кратчайшего пути на больших графах с миллионами вершин и ребер представляют собой значительную проблему для последовательных реализаций, часто требуя многочасового времени выполнения даже с помощью мощных процессоров. В работе выполнена оценка реализации на графических процессорах трех фундаментальных алгоритмов поиска кратчайшего пути: Беллмана–Форда, Дейкстры и Флойда–Уоршелла с использованием платформы NVIDIA CUDA. Проведено сравнение нескольких вариантов каждого алгоритма, от базовых параллельных подходов до специфических алгоритмов улучшения. Исследованы базовые методы оптимизации, включая циклы с шагом сетки, использование общей памяти, объединение памяти. Также выполнен анализ алгоритмов улучшения, таких как раннее завершение на основе флагов для алгоритма Беллмана–Форда и тайловые вычисления для алгоритма Флойда–Уоршелла. В исследовании представлен анализ производительности, выполнено сравнение различных стратегий оптимизации и их эффективности на различных наборах графовых данных.

1. Harish P., Narayanan P.J. Accelerating large graph algorithms on the GPU using CUDA. Lecture Notes in Computer Science, 2007, vol. 4873, pp. 197–208. https://doi.org/10.1007/978-3-540-77220-0_21

2. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C. Introduction to Algorithms. MIT press, 2009. 1292 p.

3. Katz G.J., Kider J.T. All-pairs shortest-paths for large graphs on the GPU. Proc. of the 23rd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, 2008, pp. 47–55.

4. Lebedev S.S., Novikov F.A. The Necessary and sufficient condition for Dijkstra’s algorithm applicability. Computer Tools in Education, 2017, no. 4, pp. 5–13. (in Russian)

5. Lund B., Smith J.W. A multi-stage cuda kernel for floyd-warshall. arXiv, 2010, arXiv:1001.4108. https://doi.org/10.48550/arXiv.1001.4108

6. Winkler D., Meister M., Rezavand M., Rauch W. gpuSPHASE—A shared memory caching implementation for 2D SPH using CUDA. Computer Physics Communications, 2017, vol. 213, pp. 165–180. https://doi.org/10.1016/j.cpc.2016.11.011

7. Harris M. CUDA Pro Tip: write flexible kernels with grid-stride loops. Available at: https://developer.nvidia.com/blog/cuda-pro-tipwrite-flexible-kernels-grid-stride-loops. (accessed: 30.05.2025)

8. Yang S., Liu X., Wang Y., He X., Tan G. Fast All-Pairs Shortest Paths algorithm in large sparse graph. Proc. of the 37th International Conference on Supercomputing, 2023, pp. 277–288. https://doi.org/10.1145/3577193.3593728

9. Tang W., Chen T., Armstrong M.P. GPU-accelerated parallel all-pair shortest path routing within stochastic road networks. International Journal of Geographical Information Science, 2025, vol. 39, no. 1, pp. 53–85. https://doi.org/10.1080/13658816.2024.2394651

10. Spridon D.E., Deaconu A.M., Tayyebi J. Novel GPU-based method for the generalized maximum flow problem. Computation, 2025, vol. 13, no. 2, pp. 40. https://doi.org/10.3390/computation13020040

11. Agarwal P., Dutta M. New approach of Bellman Ford algorithm on GPU using compute unified design architecture (CUDA). International Journal of Computer Applications, 2015, vol. 110, no. 13, pp. 1–5. https://doi.org/10.5120/19375-1027

12. Song B. High-performance parallelization of Dijkstra’s algorithm using MPI and CUDA. arXiv, 2025, arXiv:2504.03667. https://doi.org/10.48550/arXiv.2504.03667

13. Bengtsson M., Wittsten J., Waidringer J. Warehouse storage and retrieval optimization via clustering, dynamic systems modeling, and GPU-accelerated routing. arXiv, 2025, arXiv:2504.20655. https://doi.org/10.48550/arXiv.2504.20655

14. Kumar H.S., Singh A., Ojha M.K. Artificial intelligence based navigation in quasi structured environment. arXiv, 2024, arXiv:2407.17508. https://doi.org/10.48550/arXiv.2407.17508

15. Morgan N., Yenusah C., Diaz A., Dunning D., Moore J., Heilman E., et al. On a simplified approach to achieve parallel performance and portability across CPU and GPU architectures. Information, 2024, vol. 15, no. 11, pp. 673. https://doi.org/10.3390/info15110673

16. Leskovec J., Krevl A. SNAP Datasets: Stanford large network dataset collection. 2014. Available at: http://snap.stanford.edu/data

17. Buluç A., Gilbert J.R., Budak C. Solving path problems on the GPU. Parallel Computing, 2010, vol. 36, no. 5-6, pp. 241–253. https://doi.org/10.1016/j.parco.2009.12.002

18. Merrill D., Garland M., Grimshaw A. Scalable GPU graph traversal. ACM SIGPLAN Notices, 2012, vol. 47, no. 8, pp. 117–128. https://doi.org/10.1145/2370036.2145832

19. Kirk D.B., Hwu W.M.W. Programming Massively Parallel Processors: a Hands-on Approach. Morgan Kaufmann, 2016, 576 p.

20. Nickolls J., Buck I., Garland M., Skadron K. Scalable parallel programming with CUDA. Queue, 2008, vol. 6, no. 2, pp. 40–53. https://doi.org/10.1145/1365490.1365500

21. Bodra D., Khairnar S. Comparative performance analysis of modern NoSQL data technologies: Redis, Aerospike, and Dragonfly. Journal of Research, Innovation and Technologies, 2025, vol. 4, no. 2, pp. 193–200. https://doi.org/10.57017/jorit.v4.2(8).05

22. Khairnar S., Bodra D. Recommendation engine for Amazon magazine subscriptions. International Journal of Advanced Computer Science and Applications, 2025, vol. 16, no. 7, pp. 1–8. https://doi.org/10.14569/ijacsa.2025.0160796