TY - GEN
T1 - Advanced shortest paths algorithms on a massively-multithreaded architecture
AU - Crobak, Joseph R.
AU - Berry, Jonathan W.
AU - Madduri, Kamesh
AU - Bader, David A.
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=34548784575&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34548784575&partnerID=8YFLogxK
U2 - 10.1109/IPDPS.2007.370687
DO - 10.1109/IPDPS.2007.370687
M3 - Conference contribution
AN - SCOPUS:34548784575
SN - 1424409101
SN - 9781424409105
T3 - Proceedings - 21st International Parallel and Distributed Processing Symposium, IPDPS 2007; Abstracts and CD-ROM
BT - Proceedings - 21st International Parallel and Distributed Processing Symposium, IPDPS 2007; Abstracts and CD-ROM
T2 - 21st International Parallel and Distributed Processing Symposium, IPDPS 2007
Y2 - 26 March 2007 through 30 March 2007
ER -