David A. Bader
IEEE Fellow
AAAS Fellow
Professor
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



Combinatorics