Advanced heterogeneous block-parallel all-pairs shortest path algorithm

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.