An experimental study of a parallel shortest path algorithm for solving large-scale graph instances

Kamesh Madduri, David A. Bader, W. Berry Jonathan, Joseph R. Crobak

Research output: Chapter in Book/Report/Conference proceedingConference contribution

56 Scopus citations

Abstract

We present an experimental study of the single source shortest path problem with non-negative edge weights (NSSP) on large-scale graphs using the △-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, △-stepping on a directed scalefree 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.

Original languageEnglish (US)
Title of host publicationProceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics
PublisherSociety for Industrial and Applied Mathematics Publications
Pages23-35
Number of pages13
ISBN (Print)0898716284, 9780898716283
DOIs
StatePublished - 2007
Externally publishedYes
Event9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics - New Orleans, LA, United States
Duration: Jan 6 2007Jan 6 2007

Publication series

NameProceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics

Conference

Conference9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics
Country/TerritoryUnited States
CityNew Orleans, LA
Period1/6/071/6/07

All Science Journal Classification (ASJC) codes

  • General Engineering
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'An experimental study of a parallel shortest path algorithm for solving large-scale graph instances'. Together they form a unique fingerprint.

Cite this