Parallel Shortest Path Algorithms for Solving Large-Scale Instances

We present an experimental study of the single source shortest path problem with non-negative edge weights (NSSP) on largescale graphs using the Delta-stepping parallel algorithm. We report performance results on the Cray MTA-2, a multithreaded parallel computer. The MTA-2 is a high-end shared memory system offering two unique features that aid the efficient parallel implementation of irregular algorithms: the ability to exploit fine-grained parallelism, and low-overhead synchronization primitives. Our implementation exhibits remarkable parallel speedup when compared with competitive sequential algorithms, for low-diameter sparse graphs. For instance, Delta-stepping on a directed scale-free graph of 100 million vertices and 1 billion edges takes less than ten seconds on 40 processors of the MTA-2, with a relative speedup of close to 30. To our knowledge, these are the first performance results of a shortest path problem on realistic graph instances in the order of billions of vertices and edges.

Publication History

1. K. Madduri, D.A. Bader, J.W. Berry, and J.R. Crobak, ``Parallel Shortest Path Algorithms for Solving Large-Scale Instances,'' 9th DIMACS Implementation Challenge -- The Shortest Path Problem, DIMACS Center, Rutgers University, Piscataway, NJ, November 13-14, 2006.
2. K. Madduri, D.A. Bader, J.W. Berry, and J.R. Crobak, ``An Experimental Study of A Parallel Shortest Path Algorithm for Solving Large-Scale Graph Instances,'' Workshop on Algorithm Engineering and Experiments (ALENEX), New Orleans, LA, January 6, 2007.

Download this report in Adobe PDF