TY - GEN
T1 - DSMR
T2 - 30th International Conference on Supercomputing, ICS 2016
AU - Maleki, Saeed
AU - Nguyen, Donald
AU - Lenharth, Andrew
AU - Garzarán, María
AU - Padua, David
AU - Pingali, Keshav
N1 - Funding Information:
This material is based upon work supported by the National Science Foundation under Grant No. CNS 1111407. The authors thank the Argonne Leadership Computing Facility at Argonne National Lab for providing computation time on the Mira cluster.
Publisher Copyright:
© 2016 ACM.
PY - 2016/6/1
Y1 - 2016/6/1
N2 - The Single Source Shortest Path (SSSP) problem consists in finding the shortest paths from a vertex (the source vertex) to all other vertices in a graph. SSSP has numerous applications. For some algorithms and applications, it is useful to solve the SSSP problem in parallel. This is the case of Betweenness Centrality which solves the SSSP problem for multiple source vertices in large graphs. In this paper, we introduce the Dijkstra Strip Mined Relaxation (DSMR) algorithm, an efficient parallel SSSP algorithm for shared and distributed-memory systems. We also introduce a set of preprocessing optimization techniques that significantly reduce the communication overhead without increasing the total amount of work dramatically. Our results show that, DSMR is faster than the best previous algorithm, parallel Δ-Stepping, by up-to 7:38×.
AB - The Single Source Shortest Path (SSSP) problem consists in finding the shortest paths from a vertex (the source vertex) to all other vertices in a graph. SSSP has numerous applications. For some algorithms and applications, it is useful to solve the SSSP problem in parallel. This is the case of Betweenness Centrality which solves the SSSP problem for multiple source vertices in large graphs. In this paper, we introduce the Dijkstra Strip Mined Relaxation (DSMR) algorithm, an efficient parallel SSSP algorithm for shared and distributed-memory systems. We also introduce a set of preprocessing optimization techniques that significantly reduce the communication overhead without increasing the total amount of work dramatically. Our results show that, DSMR is faster than the best previous algorithm, parallel Δ-Stepping, by up-to 7:38×.
UR - http://www.scopus.com/inward/record.url?scp=84978540159&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84978540159&partnerID=8YFLogxK
U2 - 10.1145/2925426.2926287
DO - 10.1145/2925426.2926287
M3 - Conference contribution
AN - SCOPUS:84978540159
T3 - Proceedings of the International Conference on Supercomputing
BT - Proceedings of the 2016 International Conference on Supercomputing, ICS 2016
PB - Association for Computing Machinery
Y2 - 1 June 2016 through 3 June 2016
ER -