Preview

Доклады БГУИР

Расширенный поиск

ПОТОКОВЫЙ БЛОЧНО-ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ПОИСКА КРАТЧАЙШИХ ПУТЕЙ НА ГРАФЕ

Аннотация

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

Для цитирования:


Карасик О.Н., Прихожий А.А. ПОТОКОВЫЙ БЛОЧНО-ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ПОИСКА КРАТЧАЙШИХ ПУТЕЙ НА ГРАФЕ. Доклады БГУИР. 2018;(2):77-84.

For citation:


Karasik O.N., Prihozhy A.A. Threaded block-parallel algorithm for finding the shortest paths on graph. Doklady BGUIR. 2018;(2):77-84. (In Russ.)

Просмотров: 573


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


ISSN 1729-7648 (Print)
ISSN 2708-0382 (Online)