research-article

Public Access

DSMR: A Parallel Algorithm for Single-Source Shortest Path Problem

Authors:

Andrew Lenharth,

María Garzarán,

Keshav PingaliAuthors Info & Claims

ICS '16: Proceedings of the 2016 International Conference on Supercomputing

Article No.: 32, Pages 1 - 14

https://doi.org/10.1145/2925426.2926287

Published: 01 June 2016 Publication History

Abstract

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×.

References

[1]

9th dimacs implementation challenge - shortest paths. http://www.dis.uniroma1.it/challenge9/.

[2]

David A. Bader and Kamesh Madduri. Design and implementation of the hpcs graph analysis benchmark on symmetric multiprocessors. In Proceedings of the 12th International Conference on High Performance Computing, HiPC'05, pages 465--476, Berlin, Heidelberg, 2005. Springer-Verlag.

Digital Library

[3]

Albert-Laszlo Barabasi and Reka Albert. Emergence of scaling in random networks. Science, 286(5439):509--512, 1999.

[4]

Richard Bellman. On a Routing Problem. Quarterly of Applied Mathematics, 16:87--90, 1958.

[5]

J. W. Berry, B. Hendrickson, S. Kahan, and P. Konecny. Software and algorithms for graph queries on multithreaded architectures. In 2007 IEEE International Parallel and Distributed Processing Symposium, pages 1--14, March 2007.

[6]

Aydin Buluç and John R Gilbert. The combinatorial blas: Design, implementation, and applications. Int. J. High Perform. Comput. Appl., 25(4):496--509, November 2011.

Digital Library

[7]

V. T. Chakaravarthy, F. Checconi, F. Petrini, and Y. Sabharwal. Scalable single source shortest path algorithms for massively parallel systems. In Parallel and Distributed Processing Symposium, 2014 IEEE 28th International, pages 889--901, May 2014.

Digital Library

[8]

Deepayan Chakrabarti, Yiping Zhan, and Christos Faloutsos. R-MAT: A Recursive Model for Graph Mining. In Fourth SIAM International Conference on Data Mining, April 2004.

[9]

D. Chazan and W. Miranker. Chaotic Relaxation. Linear Algebra and Its Applications'69, 2(7):199--222, 1969.

[10]

Reuven Cohen and Shlomo Havlin. Scale-free networks are ultrasmall. Phys. Rev. Lett., 90:058701, Feb 2003.

[11]

Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck. Phast: Hardware-accelerated shortest path trees. In Proceedings of the 2011 IEEE International Parallel & Distributed Processing Symposium, IPDPS '11, pages 921--931, Washington, DC, USA, 2011. IEEE Computer Society.

Digital Library

[12]

Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson. Implementation challenge for shortest paths. In Ming-Yang Kao, editor, Encyclopedia of Algorithms, pages 1--99. Springer US, 2008.

[13]

E. W. Dijkstra. A note on two problems in connexion with graphs. NUMERISCHE MATHEMATIK, 1(1):269--271, 1959.

Digital Library

[14]

Nick Edmonds, Alex Breuer, Douglas Gregor, and Andrew Lumsdaine. Single-source shortest paths with the parallel boost graph library.

[15]

Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596--615, July 1987.

Digital Library

[16]

Linton C. Freeman. A Set of Measures of Centrality Based on Betweenness. Sociometry, 40(1):35--41, March 1977.

[17]

Galois system. http://iss.ices.utexas.edu/?p=projects/galois.

[18]

Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. Contraction hierarchies: Faster and simpler hierarchical routing in road networks. In Proceedings of the 7th International Conference on Experimental Algorithms, WEA'08, pages 319--333, Berlin, Heidelberg, 2008. Springer-Verlag.

Digital Library

[19]

Andrew Goldberg. Shortest path algorithms: Engineering aspects. In In Proc. ESAAC âĂ&Zacute;01, Lecture Notes in Computer Science, pages 502--513. Springer-Verlag, 2001.

Digital Library

[20]

Andrew V. Goldberg. A practical shortest path algorithm with linear expected time. SIAM J. Comput., 37(5):1637--1655, February 2008.

Digital Library

[21]

Andrew V. Goldberg, Haim Kaplan, and Renato F. Werneck. Reach for A*: Efficient point-to-point shortest path algorithms. In IN WORKSHOP ON ALGORITHM ENGINEERING & EXPERIMENTS, pages 129--143, 2006.

Digital Library

[22]

Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. Powergraph: Distributed graph-parallel computation on natural graphs. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI'12, pages 17--30, Berkeley, CA, USA, 2012. USENIX Association.

Digital Library

[23]

Graph 500. http://www.graph500.org/.

[24]

Douglas Gregor and Andrew Lumsdaine. The parallel bgl: A generic library for distributed graph computations. In In Parallel Object-Oriented Scientific Computing (POOSC), 2005.

[25]

Ron Gutman. Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks. In Proceedings 6th Workshop on Algorithm Engineering and Experiments (ALENEX), pages 100--111. SIAM, 2004.

[26]

IBM XL C/C++ Compiler for Blue Gene/Q. http://www-03.ibm.com/software/products/en/xlcc+forbluegene.

[27]

Intel C/C++ Compiler. http://software.intel.com/en-us/c-compilers.

[28]

Valdis Krebs. Mapping networks of terrorist cells. CONNECTIONS, 24(3):43--52, 2002.

[29]

Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. What is twitter, a social network or a news media? In Proceedings of the 19th International Conference on World Wide Web, WWW '10, pages 591--600, New York, NY, USA, 2010. ACM.

Digital Library

[30]

Ekkehard KÃűhler, Rolf H. MÃűhring, and Heiko Schilling. Fast point-to-point shortest path computations with arc-flags. In IN: 9TH DIMACS IMPLEMENTATION CHALLENGE {29, 2006.

[31]

F. Liljeros, C. R. Edling, L. A. N. Amaral, H. E. Stanley, and Y. Åberg. The Web of Human Sexual Contacts. Nature, 411:907--908, 2001.

[32]

Yucheng Low, Joseph Gonzalez, Aapo Kyrola, Danny Bickson, Carlos Guestrin, and Joseph M. Hellerstein. Graphlab: A new parallel framework for machine learning. In Conference on Uncertainty in Artificial Intelligence (UAI), Catalina Island, California, July 2010.

Digital Library

[33]

Kamesh Madduri, David A. Bader, Jonathan W. Berry, and Joseph R. Crobak. An experimental study of a parallel shortest path algorithm for solving large-scale graph instances. In Proceedings of the Meeting on Algorithm Engineering & Expermiments, pages 23--35, Philadelphia, PA, USA, 2007. Society for Industrial and Applied Mathematics.

Digital Library

[34]

Saeed Maleki, G. Carl Evans, and David A. Padua. Languages and Compilers for Parallel Computing: 27th International Workshop, LCPC 2014, Hillsboro, OR, USA, September 15-17, 2014, Revised Selected Papers, chapter Tiled Linear Algebra a System for Parallel Graph Algorithms, pages 116--130. Springer International Publishing, Cham, 2015.

[35]

U. Meyer and P. Sanders. Delta-stepping: A parallelizable shortest path algorithm. J. Algorithms'03, 49(1):114--152, October 2003.

Digital Library

[36]

Ulrich Meyer. Average-case complexity of single-source shortest-paths algorithms: Lower and upper bounds. J. Algorithms, 48(1):91--134, August 2003.

Digital Library

[37]

MPICH: High-Performance Portable MPI. http://www.mpich.org/.

[38]

Gergely Palla, IllÃl's J Farkas, PÃl'ter Pollner, Imre DerÃl'nyi, and TamÃąs Vicsek. Fundamental statistical features and self-similar properties of tagged networks. New Journal of Physics, 10(12):123026, 2008.

[39]

Dimitrios Prountzos, Roman Manevich, and Keshav Pingali. Elixir: A system for synthesizing concurrent graph programs. In Proceedings of the Conference on Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA '12, 2012.

Digital Library

[40]

Leslie G. Valiant. A bridging model for parallel computation. Commun. ACM, 33(8):103--111, August 1990.

Digital Library

Cited By

Xu XWang FJiang HCheng YFeng DFang P(2024)A disk I/O optimized system for concurrent graph processing jobsFrontiers of Computer Science10.1007/s11704-023-2361-018:3Online publication date: 22-Jan-2024
https://doi.org/10.1007/s11704-023-2361-0
Shichkina YNguyen XHa MTran D(2024)Shortest Path Search Method on a Graph with CyclesComputational Science and Its Applications – ICCSA 2024 Workshops10.1007/978-3-031-65343-8_26(344-356)Online publication date: 30-Jul-2024
https://doi.org/10.1007/978-3-031-65343-8_26
Zhang YCao HZhang JSun YDun MHuang JAn XYe X(2023)A Bucket-aware Asynchronous Single-Source Shortest Path Algorithm on GPUProceedings of the 52nd International Conference on Parallel Processing Workshops10.1145/3605731.3605746(50-60)Online publication date: 7-Aug-2023
https://dl.acm.org/doi/10.1145/3605731.3605746
Show More Cited By

DSMR: A Parallel Algorithm for Single-Source Shortest Path Problem
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

DSMR: a shared and distributed memory algorithm for single-source shortest path problem
PPoPP '16

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 ...
DSMR: a shared and distributed memory algorithm for single-source shortest path problem
PPoPP '16: Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

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 ...
Fast methods for computing all-to-all geodesic paths for the eikonal equation

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ICS '16: Proceedings of the 2016 International Conference on Supercomputing

June 2016

547 pages

ISBN:9781450343619

DOI:10.1145/2925426

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

Conference

ICS '16

Sponsor:

SIGARCH

ICS '16: 2016 International Conference on Supercomputing

June 1 - 3, 2016

Istanbul, Turkey

Acceptance Rates

Overall Acceptance Rate 629 of 2,180 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
6,075
Total Downloads

Downloads (Last 12 months)2,666
Downloads (Last 6 weeks)53

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Xu XWang FJiang HCheng YFeng DFang P(2024)A disk I/O optimized system for concurrent graph processing jobsFrontiers of Computer Science10.1007/s11704-023-2361-018:3Online publication date: 22-Jan-2024
https://doi.org/10.1007/s11704-023-2361-0
Shichkina YNguyen XHa MTran D(2024)Shortest Path Search Method on a Graph with CyclesComputational Science and Its Applications – ICCSA 2024 Workshops10.1007/978-3-031-65343-8_26(344-356)Online publication date: 30-Jul-2024
https://doi.org/10.1007/978-3-031-65343-8_26
Zhang YCao HZhang JSun YDun MHuang JAn XYe X(2023)A Bucket-aware Asynchronous Single-Source Shortest Path Algorithm on GPUProceedings of the 52nd International Conference on Parallel Processing Workshops10.1145/3605731.3605746(50-60)Online publication date: 7-Aug-2023
https://dl.acm.org/doi/10.1145/3605731.3605746
van der Grinten ACusters GThanh DMeyerhenke H(2022)An MPI-Parallel Algorithm for Static and Dynamic Top-k Harmonic Centrality2022 IEEE 34th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD)10.1109/SBAC-PAD55451.2022.00021(100-109)Online publication date: Nov-2022
https://doi.org/10.1109/SBAC-PAD55451.2022.00021
Kumar PSingh A(2022)VDS: A Variant of Δ-stepping Algorithm for Parallel SSSP Problem2022 IEEE International Conference on Data Science and Information System (ICDSIS)10.1109/ICDSIS55133.2022.9915894(1-7)Online publication date: 29-Jul-2022
https://doi.org/10.1109/ICDSIS55133.2022.9915894
Shan MKhan O(2022)HD-CPS: Hardware-assisted Drift-aware Concurrent Priority Scheduler for Shared Memory Multicores2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA53966.2022.00046(528-542)Online publication date: Apr-2022
https://doi.org/10.1109/HPCA53966.2022.00046
Maurya SAnand A(2022)A Novel GPU-Based Approach to Exploit Time-Respectingness in Public Transport Networks for Efficient Computation of Earliest Arrival TimeIEEE Access10.1109/ACCESS.2022.319244310(81877-81887)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3192443
Yuan-Tong MAi-Hua Z(2022)Fast and accurate calculation of seismic wave travel time in 3D TTI mediaApplied Geophysics10.1007/s11770-021-0917-z18:4(545-556)Online publication date: 2-May-2022
https://doi.org/10.1007/s11770-021-0917-z
Cui HLiu RXu SZhou C(2021)DMGAScientific Programming10.1155/2021/66390082021Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1155/2021/6639008
Dhulipala LBlelloch GShun J(2021)Theoretically Efficient Parallel Graph Algorithms Can Be Fast and ScalableACM Transactions on Parallel Computing10.1145/34343938:1(1-70)Online publication date: 22-Apr-2021
https://dl.acm.org/doi/10.1145/3434393
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten