David A. Bader
IEEE Fellow
AAAS Fellow
College of Computing
Georgia Tech
Atlanta, GA 30332



Advanced Shortest Paths Algorithms on a Massively-Multithreaded Architecture

We present a study of multithreaded implementations of Thorup's algorithm for solving the Single Source Shortest Path (SSSP) problem for undirected graphs. Our implementations leverage the fledgling MultiThreaded Graph Library (MTGL) to perform operations such as finding connected components and extracting induced subgraphs. To achieve good parallel performance from this algorithm, we deviate from several theoretically optimal algorithmic steps. In this paper, we present simplifications that perform better in practice, and we describe details of the multithreaded implementation that were necessary for scalability.

We study synthetic graphs that model unstructured networks, such as social networks and economic transaction networks. Most of the recent progress in shortest path algorithms relies on structure that these networks do not have. In this work, we take a step back and explore the synergy between an elegant theoretical algorithm and an elegant computer architecture. Finally, we conclude with a prediction that this work will become relevant to shortest path computation on structured networks.

Publication History

Versions of this paper appeared as:
  1. J.R. Crobak, J.W. Berry, K. Madduri, and D.A. Bader, ``Advanced Shortest Paths Algorithms on a Massively-Multithreaded Architecture,'' First Workshop on Multithreaded Architectures and Applications (MTAAP), Long Beach, CA, March 30, 2007.

Download this report in Adobe PDF


Last updated: October 18, 2007


Computational Biology

Parallel Computing