|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
Fast Parallel Bellman-Ford-Moore Algorithm Implementation for Small Graphsстатья
- Авторы: Vezolainen Alexei, Salnikov Alexey, Klyuchikov Artem, Komech Sergey
- Журнал: Lecture Notes in Computer Science
- Том: 13708
- Год издания: 2022
- Первая страница: 436
- Последняя страница: 449
- DOI: 10.1007/978-3-031-22941-1_32
- Аннотация: We present a practical multicore solution for a classical routing problem known as Single Source Shortest Path (SSSP), or the Shortest Path Tree (SPT) search. Most of the practical graphs are relatively small and a commodity hardware can be used though a synchronization overhead is relatively huge. Computing SPT for the large graphs is slow though the multicore synchronization overhead diminishes. We propose an enhancement of the classical Bellman-Ford-Moore algorithm with aligned in memory bit arrays for the next updating vertices in order to reduce the number of cache misses. We considered IPRAN, Fat Tree, and random networks with 2000 to 500000 nodes. For our optimized parallel Bellman-Ford-Moore implementation we obtained the performance improvement (sim)4–9 times relative to the standard implementation of Dijkstra’s algorithm (e.g. in Boost Graph Library). Performance improvement >10 times was also obtained for large, more than 50000 nodes, random graphs.
- Добавил в систему: Сальников Алексей Николаевич