Scalable Single Source Shortest Path Algorithms for Massively Parallel Systems.

We consider the single-source shortest path (SSSP) problem: given an undirected graph with integer edge weights and a source vertex v<alternatives> <inline-graphic xlink:href="chakaravarthy-ieq1-2634535.gif"/></alternatives>, find the shortest paths from v<alternatives> <inline-graphic xlink:href="chakaravarthy-ieq2-2634535.gif"/></alternatives> 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 2^38 <alternatives><inline-graphic xlink:href="chakaravarthy-ieq3-2634535.gif"/></alternatives> vertices and 2^42<alternatives> <inline-graphic xlink:href="chakaravarthy-ieq4-2634535.gif"/></alternatives> 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. [ABSTRACT FROM AUTHOR]