Threaded block-parallel algorithm for finding the shortest paths on graph
Abstract
The problem of finding the shortest paths on weighted graphs is considered. The variants of statement of the problem, known algorithms for it solving, areas of practical application and existing challenges, in particular, the challenge of scalability, are analyzed. The class of block-parallel algorithms, their advantages and disadvantages is investigated. A fast block-parallel threaded algorithm oriented to large-sized graphs is proposed. It differs by changing the order of block calculations, reducing the critical path and operating time on a multi-core system, decreasing the data exchanges among local caches of cores and between neighbor levels of hierarchical memory.
About the Authors
O. N. Karasik
Белорусский национальный технический университет
Belarus
Belarus
A. A. Prihozhy
Белорусский национальный технический университет
Belarus
Belarus
References
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.
Review
For citations:
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.)
Views:
664
Email this article 