Электронный каталог НБ БНТУ

Книга (аналит. описание)

Prihozhy, A. A.
All pairs shortest paths search in large graphs = Поиск кратчайших путей между всеми парами вершин в графах большого размера / A. A. Prihozhy, O. N. Karasik // Big Data и анализ высокого уровня = Big Data and advanced analytics: сборник материалов VII Международной научно-практической конференции (Республика Беларусь, Минск, 19―20 мая 2021 года) / [редкол.: В. А. Богуш и др.]. – Минск: Бестпринт, 2021. – С. 39-49. – На англ. яз.

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.
Проблема поиска кратчайших путей между всеми парами вершин графа имеет много разнообразных областей практического применения. В статье дан анализ известных алгоритмов ее решения и рассмотрена проблема распараллеливания и масштабирования к размеру графа и архитектуре многопроцессорной системы. Исследован класс блочно-параллельных алгоритмов поиска кратчайших путей, изучены их достоинства и недостатки. Путем имитационного моделирования показано, что при определенных соотношениях размера графа и размера кэш памяти, блочный алгоритм дает многократное сокращение обмена данными между уровнями иерархической памяти, однако при слишком большом увеличении размера графа его характеристики приближаются к характеристикам алгоритма Флойда-Уоршелла. С целью повышения производительности, однородный блочный алгоритм трансформирован в разнородный, сокращающий время расчета одного блока. Дальнейшее улучшение характеристик достигнуто за счет разработки кооперативного потокового планировщика и блочно-параллельного алгоритма, ориентированного на графы большого размера и отличающегося изменением порядка расчета блоков, локализацией обработки данных, сокращением критического пути, уменьшением времени работы на многоядерной системе, улучшением работы иерархической памяти.

004.421

общий = БД Труды научных работников БНТУ : 2021г.
труды сотрудников БНТУ = Факультет информационных технологий и робототехники : кафедра "Программное обеспечение информационных систем и технологий"
труды сотрудников БНТУ = Автоматика. Вычислительная техника (труды)
общий = МАСШТАБИРОВАНИЕ (программирование)
общий = АЛГОРИТМЫ (мат., информатика)
общий = АЛГОРИТМЫ НА ГРАФАХ
общий = МНОГОПРОЦЕССОРНЫЕ СИСТЕМЫ
общий = ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ