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

Abstract

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.

Keywords

• apsp problem
• blocked algorithm
• unequal sizes of blocks
• heterogeneous algorithm
• multi-core processor
• multi-threaded implementation