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
A. A. Prihozhy
Белорусский национальный технический университет
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. Prikhozhii A.A., Karasik O.N. Raznorodnyi blochnyi algoritm poiska kratchaishikh putei mezhdu vsemi parami vershin grafa // Sistemnyi analiz i prikladnaya informatika. 2017. № 3. S. 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. Prikhozhii A.A., Karasik O.N. Kooperativnaya model' optimizatsii vypolneniya potokov na mnogoyadernoi sisteme // Sistemnyi analiz i prikladnaya informatika. 2014. № 4. S. 13-20.
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:
667