БЫСТРЫЙ ПОИСК КРАТЧАЙШИХ ПУТЕЙ В БОЛЬШИХ РАЗРЕЖЕННЫХ ГРАФАХ, РАЗДЕЛЕННЫХ НА СВЯЗНЫЕ ПЛОТНЫЕ КЛАСТЕРЫ

УДК 004.4−004.9

 

Прихожий Анатолий Алексеевич − доктор технических наук, профессор, профессор кафедры программного обеспечения информационных систем и технологий. Белорусский национальный технический университет (220013, г. Минск, пр. Независимости 65, Республика Беларусь). E-mail: prihozhy@yahoo.com

Карасик Олег Николаевич − кандидат технических наук, ведущий инженер. Иностранное производственное унитарное предприятие «Иссофт Солюшенз». (220034, г. Минск, ул. Чапаева 5, Республика Беларусь). E-mail: karasik.oleg.nikolaevich@gmail.com

 

DOI: https://doi.org/ 10.52065/2520-6141-2024-284-13.

 

Ключевые слова: разреженный граф, кластер, задача о кратчайших путях, блочный алгоритм, блоки неравных размеров, пространственная и временная эффективность.

Для цитирования: Прихожий А. А., Карасик О. Н. Быстрый поиск кратчайших путей в больших разреженных графах, разделенных на связные плотные кластеры // Труды БГТУ. Сер. 3. Физико-математические науки и информатика. 2024. № 2 (284). С. 96–103 (На англ.). DOI: 10.52065/2520-6141-2024-284-13.

Аннотация

Целью статьи является решение задачи поиска кратчайших путей между всеми парами вершин в простых ориентированных взвешенных больших разреженных графах. Предполагается, что графы с положительными и отрицательными действительными весами ребер декомпозированы на слабосвязанные кластеры разного размера. Поскольку задача имеет множество практических приложений в различных областях, а графы могут быть слишком большими, наша цель − ускорить решение задачи на современных гетерогенных многопроцессорных системах и многоядерных процессорах. В статье расширяются возможности существующих блочных алгоритмов за счет использования блоков неравных размеров. Расширение поддерживает естественное и адекватное графовое моделирование реальных сетей и позволяет использовать большие разреженные графы, разделенные на плотные слабосвязанные кластеры, при решении задач о кратчайших путях. Наш подход заключается в том, чтобы заранее вычислять кратчайшие пути для всех пар вершин кластеров, представленных матрицей стоимости-смежности, а затем по запросу определять кратчайшие пути между вершинами разных кластеров в реальном времени. Подход основан на разработке новой быстрой операции, которая точно вычисляет кратчайшие пути между вершинами одного кластера, проходящие через вершины другого соседнего кластера и через ребра, соединяющие кластеры. Применение этой операции к парам кластеров позволило нам разработать приближенный распараллеливаемый алгоритм, эффективный по потребляемым процессорному времени и объему памяти, вычисляющий кратчайшие пути внутри кластеров, а затем между кластерами. Алгоритм может вносить неточности в кратчайшие пути, когда веса ребер, соединяющих кластеры, малы. Он находит точные решения, когда веса этих ребер больше, чем веса ребер внутри кластеров, например, в случае дорожных сетей.

Скачать

Список литературы

  1. Dijkstra E. W. A note on two problems in connexion with graphs // Numerische Mathematik. 1959. Vol. 1, no. 1. P. 269–271.
  2. Floyd R.W. Algorithm 97: Shortest path // Communications of the ACM. 1962. No. 5 (6). P. 345.
  3. Glabowski M., Musznicki B., Nowak P. and Zwierzykowski P. Review and Performance Analysis of Shortest Path Problem Solving Algorithms // International Journal on Advances in Software. 2014. Vol. 7, no. 1&2. P. 20–30.
  4. 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.
  5. Venkataraman G., Sahni S., Mukhopadhyaya S. A Blocked All-Pairs Shortest Paths Algorithm. Journal of Experimental Algorithmics (JEA). 2003. Vol. 8. P. 857–874.
  6. Park J. S., Penner M., Prasanna V. K. Optimizing graph algorithms for improved cache performance // IEEE Trans. on Parallel and Distributed Systems. 2004. No. 15 (9). P. 769–782.
  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. 2008. P. 47–55.
  8. Прихожий А. А., Карасик О. Н. Разнородный блочный алгоритм поиска кратчайших путей между всеми парами вершин графа // Системный анализ и прикладная информатика. 2017. № 3. С. 68–75.
  9. Prihozhy А. А., Karasik O. N. Advanced heterogeneous block-parallel all-pairs shortest path algorithm // Труды БГТУ. Сер. 3, Физико-математические науки и информатика. 2023. № 1 (266). С. 77–83.
  10. Prihozhy A. A., Karasik O. N. Influence of shortest path algorithms on energy consumption of multicore processors // System analysis and applied information science. 2023. No. 2. P. 4–12.
  11. Prihozhy A., Karasik O. New blocked all-pairs shortest paths algorithms operating on blocks of unequal sizes // System analysis and applied information science. 2023. No. 4. P. 4–13.
  12. 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. P. 360–369.
  13. Yang S. Liu X., Wang Y. He X., Tan G. Fast All-Pairs Shortest Paths Algorithm in Large Sparse Graph // ICS’23 Proceedings of 37th International conference on supercomputing. 2023. P. 277–288.
  14. Prihozhy A. A. Optimization of data allocation in hierarchical memory for blocked shortest paths algorithms // System analysis and applied information science. 2021. No. 3. P. 40–50.
  15. Karasik O. N., Prihozhy A. A. Tuning block-parallel all-pairs shortest path algorithm for efficient multi-core implementation // System analysis and applied information science. 2022. No. 3. P. 57–65.
  16. Prihozhy А. A., Karasik O. N. Inference of shortest path algorithms with spatial and temporal locality for big data processing // Big Data and Advanced Analytics: proceedings of VIII International conference.Minsk: Bestprint Publ., 2022. P. 56–66.
  17. Prihozhy A. A. Generation of shortest path search dataflow networks of actors for parallel multicore implementation // Informatics. 2023. Vol. 20, no. 2. P. 65−84.
  18. Prihozhy A., Merdjani R., Iskandar F. Automatic Parallelization of Net Algorithms // Proceedings of the International conference on parallel computing in electrical engineering (PARELEC’00). Quebec, Canada, 2000. P. 24–28.

Поступила 15.03.2024