Generalized blocked Floyd – Warshall algorithm

DOI: https://doi.org/10.33581/2520-6508-2019-3-84-92

Abstract

One of the most commonly used on practice all-pairs shortest paths algorithms on weighted graphs is Floyd – Warshall algorithm. Blocked version serves as a basis for obtaining effective parallel algorithms to be implemented on multicore central processing units, on computers with distributed memory, on graphics processing units (GPU). Increasing computation granularity in blocked versions of algorithm leads to a more efficient usage of caches and more efficient organization of parallel computations. In this paper we introduce generalization of blocked Floyd – Warshall algorithm. Computing blocks execution order was reorganized in such a way that array elements which participate in communication operations, both reading and writing, are pushed out of fast-access memory less often. This means that in GPU implementation slow global memory is used less often, compared with the original blocked algorithm.

Author Biography

Nikolai A. Likhoded, Belarusian State University, 4 Niezaliežnasci Avenue, Minsk 220030, Belarus

doctor of science (physics and mathematics), full professor; professor at the department of computational mathematics, faculty of applied mathematics and computer science

References

  1. Venkataraman G, Sahni S, Mukhopadhyaya S. A blocked all-pairs shortest-paths algorithm. Journal of Experimental Algorithmics. 2003;8:857– 874. DOI: 10.1145/996546.996553.
  2. Park J, Penner M, Prasanna VK. Optimizing graph algorithms for improved cache performance. IEEE Transactions on Parallel and Distributed Systems. 2004;15(9):769 –782. DOI: 10.1109/TPDS.2004.44.
  3. Srinivasan T, Balakrishnan R, Gangadharan SA, Hayawardh V. A scalable parallelization of all-pairs shortest path algorithm for a high performance cluster environment. In: Proceedings of the 13th International Conference on Parallel and Distributed Systems; 2007 December 5–7; Hsinchu, Taiwan. Washington: IEEE Computer Society; 2007. p. 1– 8. DOI: 10.1109/ICPADS.2007.4447721.
  4. Lund BD, Smith JW. A multi-stage CUDA kernel for Floyd – Warshall. arXiv:1001.4108. 2010 [Preprint]. 2010 [cited 2019 June 3]. Available from: https://arxiv.org/abs/1001.4108.
  5. Mullapudi RT, Bondhugula U. Tiling for dynamic scheduling. In: IMPACT 2014. Proceedings of the 4th International Workshop on Polyhedral Compilation Techniques; 2014 January 20 –22; Vienna, Austria. [S. l.]: [s. n.]; 2014.
  6. Prihozhy AA, Karasik ON. Heterogenious blocked all-pairs shortest paths algorithm. Sistemnyi analiz i prikladnaya informatika. 2017;3:68 –75. Russian. DOI: 10.21122/2309-4923-2017-3-68-75.
  7. Voevodin VlV, Voevodin VadV. [The fortunate locality of supercomputers]. Otkrytye sistemy. SUBD. 2013;9:12–15. Russian.
  8. Buluc A, Gilberta JR, Budak C. Solving path problems on the GPU. Parallel Computing. 2010;36(5– 6):241–253. DOI: 10.1016/j.parco.2009.12.002.
  9. Likhoded NA, Paliashchuk MA. Conditions for privatizing the elements of arrays by computing threads. Journal of the Belarusian State University. Mathematics and Informatics. 2018;3:59 – 67. Russian.
  10. Harish P, Narayanan P. Accelerating large graph algorithms on the GPU using CUDA. In: High Performance Computing – HiPC 2007. Proceedings of the 14th International Conference; 2007 December 18–21; Goa, India. Berlin: Springer-Verlag; 2007. p. 197–208. DOI: 10.1007/978-3-540-77220-0_21.
  11. Katz GJ, Kider JT. All-pairs shortest-paths for large graphs on the GPU. In: Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware; 2008 June 20 –21; Sarajevo, Bosnia and Herzegovina. Aire-la-Ville: Eurographics Association; 2008. p. 47–55.
Published
2019-11-25
Keywords: parallel algorithms, shortest paths, graphs, Floyd – Warshall algorithm, block algorithm, GPU
Supporting Agencies The prepared report was sponsored by the government program of scientific research of the Republic of Belarus «Convergence-2020» (subprogram «Methods of mathematical modeling of complex systems»).
How to Cite
Likhoded, N. A. (2019). Generalized blocked Floyd – Warshall algorithm. Journal of the Belarusian State University. Mathematics and Informatics, 3, 84-92. https://doi.org/10.33581/2520-6508-2019-3-84-92
Issue
No 3 (2019): Journal of the Belarusian State University. Mathematics and Informatics
Section
Discrete Mathematics and Mathematical Cybernetics

Copyright (c) 2019 Journal of the Belarusian State University. Mathematics and Informatics

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

The authors who are published in this journal agree to the following:

  1. The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
  3. The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)