Show simple item record

dc.contributor.authorMadduri, Kamesh
dc.contributor.authorBader, David A.
dc.contributor.authorBerry, Jonathan W.
dc.contributor.authorCrobak, Joseph R.
dc.date.accessioned2007-05-24T17:23:16Z
dc.date.available2007-05-24T17:23:16Z
dc.date.issued2006-08-30
dc.identifier.urihttp://hdl.handle.net/1853/14449
dc.description.abstractWe present an experimental study of parallel algorithms for solving the single source shortest path problem with non-negative edge weights (NSSP) on large-scale graphs. We implement Meyer and Sander's Δ-stepping algorithm and report performance results on the Cray MTA-2, a multithreaded parallel architecture. The MTA-2 is a high-end shared memory system offering two unique features that aid the efficient implementation of irregular parallel graph algorithms: the ability to exploit fine-grained parallelism, and low-overhead synchronization primitives. Our implementation exhibits remarkable parallel speedup when compared with a competitive sequential algorithm, for low-diameter sparse graphs. For instance, Δ-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 parallel NSSP problem on realistic graph instances in the order of billions of vertices and edges.en_US
dc.language.isoen_USen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.relation.ispartofseriesCSE Technical Reports; GT-CSE-06-19en_US
dc.subjectMultithreaded architectureen_US
dc.subjectNon-negative edge weights (NSSP)en_US
dc.subjectParallel algorithmsen_US
dc.subjectShared memory systemen_US
dc.titleParallel Shortest Path Algorithms for Solving Large-Scale Instancesen_US
dc.typeTechnical Reporten_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record