ADVANCED HETEROGENEOUS BLOCK-PARALLEL ALL-PAIRS SHORTEST PATH ALGORITHM

UDC 004.272.2

  • Prihozhy Anatoly Alekseevich – DSc (Engineering), Professor, Professor, Department of Computer and System Software. Belarusian National Technical University (65, Nezavisimosti ave., 220013, Minsk, Republic of Belarus). E-mail: prihozhy@yahoo.com

  • Karasik Oleg Nikolayevich – PhD (Engineering), Lead Engineer, ISsoft Solutions (5, Chapaeva str., 220034, Minsk, Republic of Belarus). E-mail: karasik.oleg.nikolaevich@gmail.com

DOI: https://doi.org/10.52065/2520-6141-2023-266-1-13

Keywords: shortest path, blocked algorithm, heterogeneous algorithm, multi-core system, throughput.

For citation: Prihozhy А. А., Karasik O. N. Advanced heterogeneous block-parallel all-pairs shortest path algorithm. Proceedings of BSTU, issue 3, Physics and Mathematics. Informatics, 2023, no. 1 (266), pp. 77–83. DOI: https://doi.org/10.52065/2520-6141-2023-266-1-13.

Abstract

The problem of finding shortest paths between all pairs of vertices in a large-size graph has many application domains in industry, technology, science, economics, and society. The algorithms solving the problem and proposed in the literature target either lowering a computational complexity or efficient exploitation of computational resources. This paper proposes the advanced heterogeneous block-parallel shortest paths algorithm that is a result of further development and improvement of known blocked algorithms. Starting from the homogeneous blocked algorithm, it distinguishes four types of blocks: diagonal, vertical of cross, horizontal of cross, and peripheral. To speed up the computations, separate algorithms for all block types have been developed, which reduce the number of iterations in nested loops and account for the sequential reference locality of data in CPU caches. The algorithms improve the spatial and temporal reference locality in big data processing. Experiments carried out on a server equipped with two Intel Xeon E5-2620 v4 processors have shown the speedup of up to 60−70% the proposed single- and multi-threaded advanced heterogeneous blocked algorithms yield over the singleand multiple-threaded homogeneous blocked Floyd – Warshall algorithms.

Download

References

  1. Madkour A., Aref W. G., Rehman F. U., Rahman M. A., Basalamah S. A Survey of Shortest-Path Algorithms. ArXiv: 1705.02044v1 [cs.DS], 4 May 2017, 26 p.
  2. Glabowski M., Musznicki B., Nowak P. and Zwierzykowski P. Review and Performance Analysis of Shortest Path Problem Solving Algorithms. International Journal on Advances in Software, 2014, vol. 7, no. 1&2, pp. 20–30.
  3. Floyd R.W. Algorithm 97: Shortest path. Communications of the ACM, 1962, no. 5 (6), p. 345.
  4. Prihozhy A.A., Mattavelli M., Mlynek D. Data dependences critical path evaluation at C/C++ system level description. International Workshop PATMOS'2003, Springer, 2003, pp. 569–579. DOI:10.1007/978-3-540-39762-5_63.
  5. 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, pp. 109–112.DOI: 10.2991/cse.2013.26.
  6. Prihozhy A. A. Analiz, preobrazovaniуe i optimizatsiya dlya vysokoproizvoditel’nykh parallel’nykh vychisleniy [Analysis, transformation and optimization for high performance parallel computing]. Minsk, BNTU Publ., 2019. 229 p. (In Russian).
  7. Prihozhy A. A., Casale-Brunet S., Bezati E., Mattavelli. M. Pipeline Synthesis and Optimization from Branched Feedback Dataflow Programs. Journal of Signal Processing Systems, Springer Nature, 2020, vol. 92, pp. 1091–1099. Available at: https://doi.org/10.1007/s11265-020-01568-5 (accessed 29.09.2022). DOI:10.1007/s11265-020-01568-5.
  8. Prihozhy А. A., Karasik O. N. Inference of shortest path algorithms with spatial and temporal locality for big data processing. Big Data and Advanced Analytics: sbornik nauchnykh statey VIII Mezhdunarodnoy nauchno-prakticheskoy konferentsii [Big Data and Advanced Analytics: Proceedings of VIII International Conference]. Minsk, Bestprint Publ., 2022, pp. 56–66.
  9. Prihozhy A. A. Simulation of direct mapped, k-way and fully associative cache on all-pairs shortest paths algorithms. System analysis and applied information science, 2019, no. 4, pp. 10–18. Available at: https://doi.org/10.21122/2309-4923-2019-4-10-18 (accessed 29.01.2023). (In Russian). DOI:10.21122/2309-4923-2019-4-10-18.
  10. Venkataraman G., Sahni S., Mukhopadhyaya S. A Blocked All-Pairs Shortest Paths Algorithm. Journal of Experimental Algorithmics (JEA), 2003, vol. 8, pp. 857–874. DOI: 10.1145/996546.996553.
  11. Park J. S., Penner M., and Prasanna V. K. Optimizing graph algorithms for improved cache performance. IEEE Trans. on Parallel and Distributed Systems, 2004, no. 15 (9), pp.769–782. DOI:10.1109/TPDS.2004.44.
  12. Prihozhy A. A., Karasik O. N. Heterogeneous blocked all-pairs shortest paths algorithm. System analysis and Applied Information Science, 2017, no. 3, pp. 68–75. Available at: https://doi.org/10.21122/2309-4923-2017-3-68-75 (accessed 29.01.2023) (In Russian). DOI: 10.21122/2309-4923-2017-3-68-75.
  13. Karasik O. N., Prihozhy A. A. Threaded block-parallel algorithm for finding the shortest paths on graph. Doklady BGUIR [Reports BSUIR], 2018, no. 2, pp. 77–84 (In Russian).
  14. Karasik O. N., Prihozhy A. A. Tuning block-parallel all-pairs shortest path algorithm for efficient multicore implementation. Systemnyy analiz i prikladnaya informatika [System Analysis and Applied Information Science], 2022, no. 3, pp. 57–65 (In Russian). DOI: 10.21122/2309-4923-2022-3-57-65.
  15. Prihozhy A. A. Optimization of data allocation in hierarchical memory for blocked shortest paths algorithms. Systemnyy analiz i prikladnaya informatika [System Analysis and Applied Information Science], 2021, no. 3, pp. 40–50 (In Russian).
15.11.2022