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 -