Preview

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

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

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

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

Аннотация

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

Об авторах

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


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


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

1. Floyd R.W. Algorithm 97: Shortest path // Communications of the ACM. 1962. № 5(6). P. 345.

2. Venkataraman G., Sahni S., Mukhopadhyaya S. A Blocked All-Pairs Shortest Paths Algorithm // Journal of Experimental Algorithmics (JEA). 2003. Vol. 8. P. 857-874.

3. Park J.S., Penner M., Prasanna V.K. Optimizing graph algorithms for improved cache performance // IEEE Trans. on Parallel and Distributed Systems. 2004. № 15 (9). P. 769-782.

4. 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. P. 109-112.

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

6. Synthesis and Optimization of Pipelines for HW Implementations of Dataflow Programs / A. Prihozhy [et al.] // IEEE Trans. on CAD of Integrated Circuits and Systems. 2015. Vol. 34, No. 10. P. 1613-1626.

7. Прихожий А.А., Карасик О.Н. Кооперативная модель оптимизации выполнения потоков на многоядерной системе // Системный анализ и прикладная информатика. 2014. № 4. С. 13-20.


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


Карасик О.Н., Прихожий А.А. ПОТОКОВЫЙ БЛОЧНО-ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ ПОИСКА КРАТЧАЙШИХ ПУТЕЙ НА ГРАФЕ. Доклады БГУИР. 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.)

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


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


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