Scalable Single Source Shortest Path Algorithms for Massively Parallel Systems

Scalable Single Source Shortest Path Algorithms for Massively Parallel Systems

Venkatesan T. Chakaravarthy∗, Fabio Checconi†, Fabrizio Petrini†, Yogish Sabharwal∗

∗ IBM Research – India, New Delhi. {vechakra,ysabharwal}@in.ibm.com
† IBM T J Watson Research Center, USA. {fchecco,fpetrin}@us.ibm.com

Abstract—In the single-source shortest path (SSSP) problem, we have to find the shortest paths from a source vertex v to all other vertices in a graph. 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. The ex- tensive performance analysis shows that our algorithms work well on scale-free and real-world graphs. In the largest tested configuration, an R-MAT graph with 238 vertices and 242 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.

Download article (.PDF)sssp-ipdps2014

You may also like...