Меню
Публикации
2025
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
Главный редактор
НИКИФОРОВ
Владимир Олегович
д.т.н., профессор
Партнеры
doi: 10.17586/2226-1494-2025-25-5-866-875
УДК 004.424.4
Ускорение и анализ производительности алгоритмов поиска кратчайшего пути на GPU с использованием платформы CUDA: алгоритмы Беллмана–Форда, Дейкстры и Флойда–Уоршелла
Читать статью полностью
Язык статьи - английский
Ссылка для цитирования:
Аннотация
Ссылка для цитирования:
Бодра Д., Хайрнар С. Ускорение и анализ производительности алгоритмов поиска кратчайшего пути на GPU с использованием платформы CUDA: алгоритмы Беллмана–Форда, Дейкстры и Флойда–Уоршелла // Научно-технический вестник информационных технологий, механики и оптики. 2025. Т. 25, № 5. С. 866–875 (на англ. яз.). doi: 10.17586/2226-1494-2025-25-866-875
Аннотация
Вычислительные требования к алгоритмам поиска кратчайшего пути на больших графах с миллионами вершин и ребер представляют собой значительную проблему для последовательных реализаций, часто требуя многочасового времени выполнения даже с помощью мощных процессоров. В работе выполнена оценка реализации на графических процессорах трех фундаментальных алгоритмов поиска кратчайшего пути: Беллмана–Форда, Дейкстры и Флойда–Уоршелла с использованием платформы NVIDIA CUDA. Проведено сравнение нескольких вариантов каждого алгоритма, от базовых параллельных подходов до специфических алгоритмов улучшения. Исследованы базовые методы оптимизации, включая циклы с шагом сетки, использование общей памяти, объединение памяти. Также выполнен анализ алгоритмов улучшения, таких как раннее завершение на основе флагов для алгоритма Беллмана–Форда и тайловые вычисления для алгоритма Флойда–Уоршелла. В исследовании представлен анализ производительности, выполнено сравнение различных стратегий оптимизации и их эффективности на различных наборах графовых данных.
Ключевые слова: вычисления на GPU, платформа CUDA, алгоритмы поиска кратчайшего пути, параллельные алгоритмы, алгоритмы графов, Беллман–Форд, Дейкстра, Флойд–Уоршелл, оптимизация производительности
Список литературы
Список литературы
1. Harish P., Narayanan P.J. Accelerating large graph algorithms on the GPU using CUDA // Lecture Notes in Computer Science. 2007.V. 4873. P. 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. P. 47–55.
4. Лебедев C.C., Новиков Ф.А. Необходимое и достаточное условие применимости алгоритма Дейкстры // Компьютерные инструменты в образовании. 2017. № 4. С. 5–13.
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. V. 213. P. 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. URL: https://developer.nvidia.com/blog/cuda-pro-tip-write-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. P. 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. V. 39. N 1. P. 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. V. 13. N 2. P. 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. V. 110. N 13. P. 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. V. 15. N 11. P. 673. https://doi.org/10.3390/info15110673
16. Leskovec J., Krevl A. SNAP Datasets: Stanford large network dataset collection. 2014. URL: http://snap.stanford.edu/data
17. Buluç A., Gilbert J.R., Budak C. Solving path problems on the GPU // Parallel Computing. 2010. V.36. N 5-6. P. 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. V. 47. N 8. P. 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. V. 6. N 2. P. 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. V. 4. N 2. P. 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. V. 16. N 7. P. 1–8. https://doi.org/10.14569/ijacsa.2025.0160796
