Новые блочные алгоритмы поиска кратчайших путей между всеми парами вершин графа, работающие на блоках неравных размеров

А. А. Прихожий; О. Н. Карасик

doi:10.21122/2309-4923-2023-4-4-13

Новые блочные алгоритмы поиска кратчайших путей между всеми парами вершин графа, работающие на блоках неравных размеров

А. А. Прихожий, О. Н. Карасик

https://doi.org/10.21122/2309-4923-2023-4-4-13

Полный текст:

Аннотация

Многие задачи на реальных сетях предполагают поиск кратчайших путей между всеми парами вершин графа и расстояний между вершинами (APSP). Решение крупномасштабной задачи APSP на современных многопроцессорных (многоядерных) системах является ключевым для различных областей применения. Вычислительные затраты на ее решение высоки, поэтому во многих случаях приемлемыми считаются приближенные решения. Перспективным подходом, позволяющим эффективно использовать множество процессоров (ядер) и их кэши в параллельном режиме, являются блочные алгоритмы APSP. В то же время, насколько нам известно, в блочных алгоритмах семейства Флойда-Уоршалла все блоки имеют одинаковый размер. Это свойство ограничивает применение алгоритмов. В статье предлагаются новые блочные алгоритмы, которые разбивают граф на неравные подграфы и разбивают матрицу расстояний между парами вершин на блоки неравного размера. Алгоритмы описывают плотные подграфы матрицей смежности, а разреженные подграфы и связи между ними ‒ списком смежности. Такой подход позволяет совместно использовать алгоритмы семейства Флойда-Уоршалла с алгоритмами семейства Дейкстры. Он может быть применен к большим графам, декомпозированным на плотные (кластеры) и разреженные подграфы. Новый гетерогенный алгоритм может существенно сократить время вычисления блоков в зависимости от типа и размера. Вклад статьи заключается в разработке нового семейства блочных алгоритмов APSP, которые работают с блоками неравных размеров, сохраняют и расширяют преимущества алгоритмов, работающих с блоками равных размеров. Предложенные алгоритмы реализованы в виде одно- и многопоточных параллельных приложений для многоядерных систем.

Ключ. слова

задача APSP, блочный алгоритм, неравные размеры блоков, разнородный алгоритм, многопоточная реализация, многоядерный процессор,

Об авторах

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

Белорусский национальный технический университет
Беларусь

Профессор кафедры «Программное обеспечение информационных систем и технологий»

г. Минск

О. Н. Карасик

ИССОФТ СОЛЮШЕНЗ
Беларусь

Ведущий инженер иностранного производственного унитарного предприятия «ИССОФТ СОЛЮШЕНЗ», кандидат технических наук

г. Минск

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

1. Dijkstra E.W. A note on two problems in connexion with graphs. Numerische Mathematik, 1959, vol. 1(1), pp. 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, pp. 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. Prihozhy А., Mlynek D. Design of parallel implementations by means of abstract dynamic critical path based profiling of complex sequential algorithms. Integrated Circuit and System Design. Power and Timing Modeling, Optimization and Simulation: 16th International Workshop, PATMOS 2006, Montpellier, France, September 13-15, 2006, pp. 1–11.

6. Prihozhy A.A., Casale-Brunet S., Bezati E., Mattavelli M. Pipeline Synthesis and Optimization from Branched Feedback Dataflow Programs. Journal of Signal Processing Systems, Springer Nature, 2020, vol. 92, pp. 1091–1099. doi: 10.1007/s11265-020-01568-5

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. Ortega-Arranz H., Torres Y., Llanos D.R. and Escribano A.G. The all-pair shortest-path problem in shared-memory heterogeneous systems. High-Performance Computing on Complex Environments, 2013, pp. 283–299.

9. 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.

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

11. 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.

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

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

14. 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.

15. Meyer U., Sanders P. Δ-stepping: a parallelizable shortest path algorithm. Journal of Algorithms, vol. 49, no. 1, 2003, pp. 114–152.

16. Прихожий, А.А. Разнородный блочный алгоритм поиска кратчайших путей между всеми парами вершин графа / А.А. Прихожий, О.Н. Карасик // Системный анализ и прикладная информатика. – 2017. – № 3. – С. 68–75.

17. Prihozhy А., Karasik O. Inference of shortest path algorithms with spatial and temporal locality for Big Data processing // Сборник материалов VIII Международной научно-практической конференции. – Минск: Беспринт, 2022. – С. 56–66.

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

19. Albalawi E., Thulasiraman P., Thulasiram R. Task Level Parallelization of All Pair Shortest Path Algorithm in OpenMP 3.0. 2nd International Conference on Advances in Computer Science and Engineering (CSE 2013). Los Angeles, CA, July 1–2, 2013, pp. 109–112.

20. 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.

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

22. Прихожий, А.А. Оптимизация размещения данных в иерархической памяти для блочных алгоритмов поиска кратчайших путей / А.А. Прихожий // Системный анализ и прикладная информатика. – 2021. – № 3. – С. 40–50. doi: 10.21122/2309-4923-2021-3-40-50

23. Прыхожы, А.А. Кааператыўныя блочна-паралельныя алгарытмы рашэння задач на шмат'ядравых сістэмах / А.А. Прыхожы, А.М. Карасiк // Системный анализ и прикладная информатика. – 2015. – № 2. – С. 10–18.

24. Карасик, О.Н. Потоковый блочно-параллельный алгоритм поиска кратчайших путей на графе / О.Н. Карасик, А.А. Прихожий // Доклады БГУИР. – 2018. – № 2. – С. 77–84.

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

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

27. Прихожий, А.А. Генерация потоковых сетей акторов поиска кратчайших путей для параллельной многоядерной реализации / А.А. Прихожий // Информатика. – 2023. – Т. 20. – № 2. – С. 65–84. doi: 10.37661/1816-0301-2023-20-2-65-84

Дополнительные файлы

Для цитирования: Прихожий А.А., Карасик О.Н. Новые блочные алгоритмы поиска кратчайших путей между всеми парами вершин графа, работающие на блоках неравных размеров. «Системный анализ и прикладная информатика». 2023;(4):4-13. https://doi.org/10.21122/2309-4923-2023-4-4-13

For citation: Prihozhy A.A., Karasik O.N. New blocked all-pairs shortest paths algorithms operating on blocks of unequal sizes. «System analysis and applied information science». 2023;(4):4-13. https://doi.org/10.21122/2309-4923-2023-4-4-13

Обратные ссылки

Обратные ссылки не определены.

Контент доступен под лицензией Creative Commons Attribution 4.0 License.

ISSN 2309-4923 (Print)
ISSN 2414-0481 (Online)

Логин
Пароль