https://libeldoc.bsuir.by/handle/123456789/43906| Title: | All pairs shortest paths search in large graphs |
| Other Titles: | Поиск кратчайших путей между всеми парами вершин в графах большого размера |
| Authors: | Prihozhy, A. A. Karasik, O. N. |
| Keywords: | публикации ученых;материалы конференций;block algorithms;multithreaded algorithm;cooperative execution;блочные алгоритмы;многопоточные алгоритмы;hierarchical memory;иерархическая память |
| Issue Date: | 2021 |
| Publisher: | Бестпринт |
| Citation: | Prihozhy, А. А. All pairs shortest paths search in large graphs / А. А. Prihozhy, O. N. Karasik // BIG DATA and Advanced Analytics = BIG DATA и анализ высокого уровня : сборник научных статей VII Международной научно-практической конференции, Минск, 19-20 мая 2021 года / редкол.: В. А. Богуш [и др.]. – Минск : Бестпринт, 2021. – С. 39–49. |
| Abstract: | The all pairs shortest paths search in a graph has many different application domains. This paper analyzes the known algorithms for solving the problem and considers its parallelization and scaling to the graph size and multiprocessor architecture. It considers a class of shortest paths block-parallel algorithms and studies their advantages and disadvantages. Modeling and simulation have shown that the block algorithms give a manifold reduction in the exchange of data between the hierarchical memory levels for certain ratios of the graph size to the cache memory size. |
| Alternative abstract: | Проблема поиска кратчайших путей между всеми парами вершин графа имеет много разнообразных областей практического применения. В статье дан анализ известных алгоритмов ее решения и рассмотрена проблема распараллеливания и масштабирования к размеру графа и архитектуре многопроцессорной системы. Исследован класс блочно-параллельных алгоритмов поиска кратчайших путей, изучены их достоинства и недостатки. Путем имитационного моделирования показано, что при определенных соотношениях размера графа и размера кэш памяти, блочный алгоритм дает многократное сокращение обмена данными между уровнями иерархической памяти, однако при слишком большом увеличении размера графа его характеристики приближаются к характеристикам алгоритма Флойда-Уоршелла. С целью повышения производительности, однородный блочный алгоритм трансформирован в разнородный, сокращающий время расчета одного блока. Дальнейшее улучшение характеристик достигнуто за счет разработки кооперативного потокового планировщика и блочно-параллельного алгоритма, ориентированного на графы большого размера и отличающегося изменением порядка расчета блоков, локализацией обработки данных, сокращением критического пути, уменьшением времени работы на многоядерной системе, улучшением работы иерархической памяти. |
| URI: | https://libeldoc.bsuir.by/handle/123456789/43906 |
| ISBN: | 978-985-7267-09-5 |
| Appears in Collections: | BIG DATA and Advanced Analytics = BIG DATA и анализ высокого уровня : сборник научных статей (2021) |
| File | Description | Size | Format | |
|---|---|---|---|---|
| Prihozhy_All.pdf | 1.06 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.