Scalable Single Source Shortest Path Algorithms for Massively Parallel Systems

Abstract

We consider the single-source shortest path (SSSP) problem: given an undirected graph with integer edge weights and a source vertex <inline-formula><tex-math notation="LaTeX">$v$</tex-math></inline-formula> , find the shortest paths from <inline-formula><tex-math notation="LaTeX">$v$</tex-math></inline-formula> to all other vertices. In this paper, we introduce a novel parallel algorithm, derived from the Bellman-Ford and Delta-stepping algorithms. We employ various pruning techniques, such as edge classification and direction-optimization, to dramatically reduce inter-node communication traffic, and we propose load balancing strategies to handle higher-degree vertices. These techniques are particularly effective on power-law graphs, as demonstrated by our extensive performance analysis. In the largest tested configuration, an R-MAT graph with <inline-formula><tex-math notation="LaTeX">$2^{38}$</tex-math> </inline-formula> vertices and <inline-formula><tex-math notation="LaTeX">$2^{42}$</tex-math></inline-formula> edges on 32,768 Blue Gene/Q nodes, we have achieved a processing rate of three Trillion Edges Per Second (TTEPS), a four orders of magnitude improvement over the best published results.