@inproceedings{e5fc53f133164e07ba1406bfb8ecb2fb,

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

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.",

author = "Kamesh Madduri and Bader, {David A.} and Jonathan, {W. Berry} and Crobak, {Joseph R.}",

year = "2007",

doi = "10.1137/1.9781611972870.3",

language = "English (US)",

isbn = "0898716284",

series = "Proceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics",

publisher = "Society for Industrial and Applied Mathematics Publications",

pages = "23--35",

booktitle = "Proceedings of the 9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics",

address = "United States",

note = "9th Workshop on Algorithm Engineering and Experiments and the 4th Workshop on Analytic Algorithms and Combinatorics ; Conference date: 06-01-2007 Through 06-01-2007",

}