New blocked all-pairs shortest paths algorithms operating on blocks of unequal sizes

In real-world networks, many problems imply finding the All-Pairs Shortest Paths (APSP) and their distances in a graph. Solving the large-scale APSP problem on modern multi-processor (multi-core) systems is the key for various application domains. The computational cost of solving the problem is high, therefore in many cases approximate solutions are considered as acceptable. The blocked APSP algorithms are a promising approach which can exploit many processors (cores) and their caches in parallel mode efficiently. At the same time, to our best knowledge, all blocked algorithms of the Floyd-Warshall family use blocks of equal sizes. This property limits application of the algorithms. In this paper we propose new blocked algorithms which divide the input graph into unequal subgraphs and divide the matrix of distances between pairs of vertices into blocks of unequal sizes. The algorithms describe the dense subgraphs by the adjacency matrix and describe sparse subgraphs and connections between them by the adjacency list. This approach allows the Floyd-Warshall family algorithms to be used together with Dijkstra family algorithms. It can be applied to large graphs decomposed into dense (clusters) and sparse subgraphs. A new heterogeneous algorithm can significantly reduce the computation time of blocks depending on the block type and size. The contribution of the paper is the development of a new family of blocked APSP algorithms which can handle blocks of unequal sizes, save and extend the advantages of the state-of-the-art algorithms operating on blocks of equal sizes. The proposed algorithms are implemented as single- and multiple-threaded parallel applications for multi-core systems.

1. Dijkstra E.W. A note on two problems in connexion with graphs. Numerische Mathematik, 1959, vol. 1(1), pp. 269–271.

2. Floyd R.W. Algorithm 97: Shortest path. Communications of the ACM, 1962, no. 5(6), p. 345.

3. 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.

4. 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.

5. Prihozhy А., Mlynek D. Design of parallel implementations by means of abstract dynamic critical path based profiling of complex sequential algorithms. Integrated Circuit and System Design. Power and Timing Modeling, Optimization and Simulation: 16th International Workshop, PATMOS 2006, Montpellier, France, September 13-15, 2006, pp. 1–11.

6. 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. doi: 10.1007/s11265-020-01568-5

7. Katz G.J., Kider J.T. All-pairs shortest-paths for large graphs on the GPU. GH’08: Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware. ACM, 2008, pp. 47–55.

8. Ortega-Arranz H., Torres Y., Llanos D.R, and Escribano A.G. The all-pair shortest-path problem in shared-memory heterogeneous systems. High-Performance Computing on Complex Environments, 2013, pp. 283–299.

9. Djidjev H., Thulasidasan S., Chapuis G., Andonov R. and Lavenier D. Efficient multi-GPU computation of all-pairs shortest paths. IEEE 28th International Parallel and Distributed Processing Symposium. IEEE, 2014, pp. 360–369.

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.

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.

12. Bellman R.E. On a routing problem. Quarterly of Applied Mathematics, 1958, vol. 16, no. 1, pp. 87–90.

13. Johnson D.B. Efficient Algorithms for Shortest Paths in Sparse Networks. J. ACM, 1977, vol. 24 no. 1, pp. 1 – 13.

14. Harish P., Narayanan P.J. Accelerating large graph algorithms on the GPU using CUDA. International conference on high-performance computing. Springer, 2007, pp. 197–208.

15. Meyer U. and Sanders P. Δ-stepping: a parallelizable shortest path algorithm. Journal of Algorithms, vol. 49, no. 1, 2003, pp. 114–152.

16. 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. (In Russian).

17. Prihozhy А.A., Karasik O.N. Inference of shortest path algorithms with spatial and temporal locality for big data processing. [Big Data and Advanced Analytics: proceedings of VIII international conference]. Minsk, Bestprint Publ., 2022, pp. 56–66.

18. 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: 10.52065/2520-6141-2023-266-1-13

19. 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.

20. Yang S., Liu X., Wang Y., He X., Tan G. Fast All-Pairs Shortest Paths Algorithm in Large Sparse Graph. ICS '23: Proceedings of the 37th International Conference on Supercomputing, 2023, pp. 277–288.

21. 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.

22. Prihozhy A.A. Optimization of data allocation in hierarchical memory for blocked shortest paths algorithms. System analysis and applied information science, 2021, no. 3, pp. 40–50. doi: 10.21122/2309-4923-2021-3-40-50

23. Prihozhy A.A., Karasik O.N. Cooperative block-parallel algorithms for task execution on multi-core system. System analysis and applied information science, 2015, no. 2, pp. 10–18.

24. Karasik O.N., Prihozhy A.A. Threaded block-parallel algorithm for finding the shortest paths on graph. Doklady BGUIR, 2018, no. 2, pp. 77–84. (In Russian).

25. Karasik O.N., Prihozhy A.A. Tuning block-parallel all-pairs shortest path algorithm for efficient multi-core implementation. System analysis and applied information science, 2022, no. 3, pp. 57–65. doi: 10.21122/2309-4923-2022-3-57-65

26. Prihozhy A.A., Karasik O.N. Influence of shortest path algorithms on energy consumption of multi-core processors. System analysis and applied information science, 2023, no. 2, pp. 4–12. doi: 10.21122/2309-4923-2023-2-4-12

27. Prihozhy A.A. Generation of shortest path search dataflow networks of actors for parallel multicore implementation. Informatics, 2023, vol. 20, no. 2, pp. 65–84. doi: 10.37661/1816-0301-2023-20-2-65-84