TY - GEN
T1 - DSMR
T2 - 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016
AU - Maleki, Saeed
AU - Nguyen, Donald
AU - Lenharth, Andrew
AU - Garzarán, María
AU - Padua, David
AU - Pingali, Keshav
N1 - Funding Information:
The work presented in this paper has been supported by the National Science Foundation grant CNS 1111407. This research used resources of the Argonne Leadership Computing Facility, which is a DOE office of Science User Facility supported under Contract DE-AC02-06CH11357.
Publisher Copyright:
© 2016 ACM.
PY - 2016/2/27
Y1 - 2016/2/27
N2 - The Single-Source Shortest Path (SSSP) problem is to find the shortest paths from a source vertex to all other vertices in a graph. In this paper, we introduce the Dijkstra Strip-Mined Relaxation (DSMR) algorithm, an efficient parallel SSSP algorithm for shared and distributed memory systems. Our results show that, DSMR is faster than parallel Δ-Stepping by a factor of up-to 1:66.
AB - The Single-Source Shortest Path (SSSP) problem is to find the shortest paths from a source vertex to all other vertices in a graph. In this paper, we introduce the Dijkstra Strip-Mined Relaxation (DSMR) algorithm, an efficient parallel SSSP algorithm for shared and distributed memory systems. Our results show that, DSMR is faster than parallel Δ-Stepping by a factor of up-to 1:66.
UR - http://www.scopus.com/inward/record.url?scp=84963725674&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84963725674&partnerID=8YFLogxK
U2 - 10.1145/2851141.2851183
DO - 10.1145/2851141.2851183
M3 - Conference contribution
AN - SCOPUS:84963725674
T3 - Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP
BT - 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016 - Proceedings
PB - Association for Computing Machinery
Y2 - 12 March 2016 through 16 March 2016
ER -