More Web Proxy on the site http://driver.im/

research-article

Public Access

A supernodal all-pairs shortest path algorithm

Authors:

Ramakrishnan Kannan,

Richard VuducAuthors Info & Claims

PPoPP '20: Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

Pages 250 - 261

https://doi.org/10.1145/3332466.3374533

Published: 19 February 2020 Publication History

Abstract

We show how to exploit graph sparsity in the Floyd-Warshall algorithm for the all-pairs shortest path (Apsp) problem. Floyd-Warshall is an attractive choice for Apsp on high-performing systems due to its structural similarity to solving dense linear systems and matrix multiplication. However, if sparsity of the input graph is not properly exploited, Floyd-Warshall will perform unnecessary asymptotic work and thus may not be a suitable choice for many input graphs. To overcome this limitation, the key idea in our approach is to use the known algebraic relationship between Floyd-Warshall and Gaussian elimination, and import several algorithmic techniques from sparse Cholesky factorization, namely, fill-in reducing ordering, symbolic analysis, supernodal traversal, and elimination tree parallelism. When combined, these techniques reduce computation, improve locality and enhance parallelism. We implement these ideas in an efficient shared memory parallel prototype that is orders of magnitude faster than an efficient multi-threaded baseline Floyd-Warshall that does not exploit sparsity. Our experiments suggest that the Floyd-Warshall algorithm can compete with Dijkstra's algorithm (the algorithmic core of Johnson's algorithm) for several classes sparse graphs.

References

[1]

Alok Aggarwal, Ashok K Chandra, and Marc Snir. Communication complexity of prams. Theoretical Computer Science, 71(1):3--28, 1990.

Digital Library

[2]

CC Ashcraft. A taxonamy of distributed dense LU factorization methods. Engineering Computing and Analysis Technical Report ECA-TR-161, Boeing Computer Services(1991), 1991.

[3]

Roland C Backhouse and Bernard A Carré. Regular algebra applied to path-finding problems. IMA Journal of Applied Mathematics, 15(2):161--186, 1975.

[4]

Guy E Blelloch. Programming parallel algorithms. Communications of the ACM, 39(3):85--97, 1996.

Digital Library

[5]

Aydin Buluç, John R Gilbert, and Ceren Budak. Solving path problems on the gpu. Parallel Computing, 36(5-6):241--253, 2010.

Digital Library

[6]

Bernard A Carré. An algebra for network routing problems. IMA Journal of Applied Mathematics, 7(3):273--294, 1971.

[7]

Timothy M Chan. All-pairs shortest paths for unweighted undirected graphs in o (mn) time. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 514--523. Society for Industrial and Applied Mathematics, 2006.

Digital Library

[8]

Hristo Djidjev, Guillaume Chapuis, Rumen Andonov, Sunil Thulasidasan, and Dominique Lavenier. All-pairs shortest path algorithms for planar graph for gpu-accelerated clusters. Journal of Parallel and Distributed Computing, 85:91--103, 2015.

Digital Library

[9]

Iain S. Duff, A.M. Erisman, and John K. Ried. Direct methods for sparse matrices. Oxford University Press, 2nd edition, 2017.

[10]

Paul Erdös, Frank Harary, and William T Tutte. On the dimension of a graph. Mathematika, 12(2):118--122, 1965.

[11]

Greg N Federickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM Journal on Computing, 16(6):1004--1022, 1987.

Digital Library

[12]

Jeremy T. Fineman and Eric Robinson. Fundamental graph algorithms. In Jeremy Kepner and John Gilbert, editors, Graph Algorithms in the Language of Linear Algebra, chapter 5, pages 45--58. Society of Industrial and Applied Mathematics, Philadelphia, PA, USA, 2011.

[13]

A. George. Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis, 10(2):345--363, 1973.

Digital Library

[14]

Alan George. Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis, 10(2), 1973.

[15]

T. George, V. Saxena, A. Gupta, A. Singh, and A. Choudjury. Multi-frontal factorization of sparse SPD matrices on GPUs. In Proc. of IEEE International Parallel and Distributed Processing Symposium (IPDPS 2011), Anchorage, Alaska, May 16--20 2011.

Digital Library

[16]

Michel Gondran and Michel Minoux. Graphs, dioids and semirings: new models and algorithms, volume 41. Springer Science & Business Media, 2008.

[17]

Kazushige Goto and Robert A Geijn. Anatomy of high-performance matrix multiplication. ACM Transactions on Mathematical Software (TOMS), 34(3):12, 2008.

[18]

Anshul Gupta, George Karypis, and Vipin Kumar. Highly scalable parallel algorithms for sparse matrix factorization. IEEE Transactions on Parallel and Distributed Systems, 8(5):502--520, 1997.

Digital Library

[19]

Michael T Heath, Esmond Ng, and Barry W Peyton. Parallel algorithms for sparse linear systems. SIAM review, 33(3):420--460, 1991.

Digital Library

[20]

Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439--561, 2006.

[21]

Donald B. Johnson. Efficient algorithms for shortest paths in sparse networks. Journal of the ACM (JACM), 24(1):1--13, 1 1977.

[22]

George Karypis and Vipin Kumar. A fast and high-quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing (SISC), 20(1), 1998.

[23]

Kyungjoo Kim and Victor Eijkhout. Scheduling a parallel sparse direct solver to multiple GPUs. In Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2013 IEEE 27th International, pages 1401--1408. IEEE, 2013.

Digital Library

[24]

G. Krawezik and G. Poole. Accelerating the ANSYS direct sparse solver with GPUs. In Proc. Symposium on Application Accelerators in High Performance Computing (SAAHPC), Urbana-Champaign, IL, NCSA, 2009.

[25]

Xavier Lacoste, Mathieu Faverge, George Bosilca, Pierre Ramet, and Samuel Thibault. Taking advantage of hybrid systems for sparse direct solvers via task-based runtimes. In Parallel & Distributed Processing Symposium Workshops (IPDPSW), 2014 IEEE International, pages 29--38. IEEE, 2014.

Digital Library

[26]

Richard J Lipton, Donald J Rose, and Robert Endre Tarjan. Generalized nested dissection. SIAM journal on numerical analysis, 16(2):346--358, 1979.

[27]

Richard J Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177--189, 1979.

Digital Library

[28]

Grigory L Litvinov. Idempotent/tropical analysis, the hamilton-jacobi and bellman equations. In Hamilton-jacobi equations: approximations, numerical analysis and applications, pages 251--301. Springer, 2013.

[29]

R. Lucas, G. Wagenbreth, D. Davis, and R. Grimes. Multifrontal computations on GPUs and their multi-core hosts. In VECPAR'10: Proc. 9th Intl. Meeting for High Performance Computing for Computational Science, Berkeley, CA, 2010.

Digital Library

[30]

Ulrich Meyer and Peter Sanders. Δ-stepping: A parallel single source shortest path algorithm. In European symposium on algorithms, pages 393--404. Springer, 1998.

[31]

François Pellegrini and Jean Roman. Scotch: A software package for static mapping by dual recursive bipartitioning of process and architecture graphs. In Proceedings of High-Performance Computing and Networking (HPCN-Ewrope), volume LNCS 1067, 1996.

[32]

Keshav Pingali. High-speed graph analytics with the galois system. In Proceedings of the first workshop on Parallel programming for analytics applications, pages 41--42. ACM, 2014.

Digital Library

[33]

Leon R Planken, Mathijs M de Weerdt, and Roman PJ van der Krogt. Computing all-pairs shortest paths by leveraging low treewidth. Journal of Artificial Intelligence Research, 43:353--388, 2012.

Digital Library

[34]

Edward Rothberg. Exploiting the memory hierarchy in sequential and parallel sparse Cholesky factorization. Technical report, Stanford University, Department of Computer Science, 1992.

[35]

Piyush Sao, Xiaoye S. Li, and Richard Vuduc. A communication-avoiding 3D LU factorization algorithm for sparse matrices. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS), Vancouver, BC, Canada, May 2018.

[36]

Piyush Sao, Richard Vuduc, and Xiaoye Sherry Li. A distributed CPU-GPU sparse direct solver. In Euro-Par 2014 Parallel Processing, pages 487--498. Springer International Publishing, 2014.

[37]

Jeremy Siek, Andrew Lumsdaine, and Lie-Quan Lee. The boost graph library: user guide and reference manual. Addison-Wesley, 2002.

Digital Library

[38]

Edgar Solomonik, Aydin Buluç, and James Demmel. Minimizing communication in all-pairs shortest paths. In Proceedings of the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS), Boston, MA, USA, 5 2013.

[39]

Daniel A Spielmat and Shang-Hua Teng. Spectral partitioning works: Planar graphs and finite element meshes. In Proceedings of 37th Conference on Foundations of Computer Science, pages 96--105. IEEE, 1996.

[40]

Alexandre Tiskin. All-pairs shortest paths computation in the bsp model. In International Colloquium on Automata, Languages, and Programming, pages 178--189. Springer, 2001.

[41]

R. Vuduc, A. Chandramowlishwaran, J. Choi, M. Guney, and A. Shringarpure. On the limits of GPU acceleration. In Proc. of the 2nd USENIX conference on Hot topics in parallelism, HotPar'10, Berkeley, CA, 2010.

[42]

Oren Weimann and Raphael Yuster. Computing the girth of a planar graph in o(n\logn) time. SIAM Journal on Discrete Mathematics, 24(2):609--616, 2010.

Digital Library

[43]

R Ryan Williams. Faster all-pairs shortest paths via circuit complexity. SIAM Journal on Computing, 47(5):1965--1985, 2018.

Digital Library

[44]

Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 645--654. IEEE, 2010.

Digital Library

[45]

Ichitaro Yamazaki and Xiaoye S Li. New scheduling strategies and hybrid programming for a parallel right-looking sparse LU factorization algorithm on multicore cluster systems. In Parallel & Distributed Processing Symposium (IPDPS), 2012 IEEE 26th International, pages 619--630. IEEE, 2012.

Digital Library

[46]

C.D. Yu, W. Wang, and D. Pierce. A CPU-GPU hybrid approach for the unsymmetric multifrontal method. Parallel Computing, 37:759--770, 2011.

Digital Library

Cited By

Feng YWang HZhu YLiu XLu HLiu Q(2024)DAWN: Matrix Operation-Optimized Algorithm for Shortest Paths Problem on Unweighted GraphsProceedings of the 38th ACM International Conference on Supercomputing10.1145/3650200.3656600(1-13)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3650200.3656600
Alghamdi MHe LRen SMaray M(2024)Efficient Parallel Processing of All-Pairs Shortest Paths on Multicore and GPU SystemsIEEE Transactions on Consumer Electronics10.1109/TCE.2023.332732870:1(2896-2908)Online publication date: Feb-2024
https://doi.org/10.1109/TCE.2023.3327328
Wang CHua QJin HZheng C(2024)Massively parallel algorithms for fully dynamic all-pairs shortest pathsFrontiers of Computer Science10.1007/s11704-024-3452-218:4Online publication date: 8-Apr-2024
https://doi.org/10.1007/s11704-024-3452-2
Show More Cited By

Index Terms

A supernodal all-pairs shortest path algorithm

Index terms have been assigned to the content through auto-classification.

Recommendations

Fast All-Pairs Shortest Paths Algorithm in Large Sparse Graph
ICS '23: Proceedings of the 37th ACM International Conference on Supercomputing

Finding the All-Pairs Shortest Paths (APSP) in a graph is the key for various domains. Motivated by the graphs are sparse in most real-world applications, we store the whole graph as a compressed storage format in each process of the distributed ...
A Multiple Pairs Shortest Path Algorithm

The multiple pairs shortest path problem (MPSP) arises in many applications where the shortest paths and distances between only some specific pairs of origin-destination (OD) nodes in a network are desired. The traditional repeated single-source shortest ...
Efficient Parallel All-Pairs Shortest Paths Algorithm for Complex Graph Analysis
ICPP Workshops '18: Workshop Proceedings of the 47th International Conference on Parallel Processing

The all-pairs shortest path problem is a classic problem to study characteristics of the given graphs. Though many efficient all-pairs shortest path algorithms have been published, it is still a very expensive computing task, especially with large graph ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PPoPP '20: Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

February 2020

454 pages

ISBN:9781450368186

DOI:10.1145/3332466

General Chair:
Rajiv Gupta
UC Riverside
,
Program Chair:
Xipeng Shen
NCSU

Copyright © 2020 ACM.

© 2020 Association for Computing Machinery. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of the United States government. As such, the United States Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 February 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Oak Ridge National Laboratory
National Science Foundation (NSF)
Defense Advanced Research Projects Agency (DARPA)

Conference

PPoPP '20

Sponsor:

PPoPP '20: 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

February 22 - 26, 2020

California, San Diego

Acceptance Rates

PPoPP '20 Paper Acceptance Rate 28 of 121 submissions, 23%;

Overall Acceptance Rate 230 of 1,014 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
1,466
Total Downloads

Downloads (Last 12 months)255
Downloads (Last 6 weeks)52

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Feng YWang HZhu YLiu XLu HLiu Q(2024)DAWN: Matrix Operation-Optimized Algorithm for Shortest Paths Problem on Unweighted GraphsProceedings of the 38th ACM International Conference on Supercomputing10.1145/3650200.3656600(1-13)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3650200.3656600
Alghamdi MHe LRen SMaray M(2024)Efficient Parallel Processing of All-Pairs Shortest Paths on Multicore and GPU SystemsIEEE Transactions on Consumer Electronics10.1109/TCE.2023.332732870:1(2896-2908)Online publication date: Feb-2024
https://doi.org/10.1109/TCE.2023.3327328
Wang CHua QJin HZheng C(2024)Massively parallel algorithms for fully dynamic all-pairs shortest pathsFrontiers of Computer Science10.1007/s11704-024-3452-218:4Online publication date: 8-Apr-2024
https://doi.org/10.1007/s11704-024-3452-2
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
Lu HSao PMatheson MKannan RWang FPotok T(2023)Optimizing Communication in 2D Grid-Based MPI Applications at ExascaleProceedings of the 30th European MPI Users' Group Meeting10.1145/3615318.3615327(1-11)Online publication date: 11-Sep-2023
https://dl.acm.org/doi/10.1145/3615318.3615327
Yang SLiu XWang YHe XTan GGallivan KNikolopoulos DBeivide RGallopoulos E(2023)Fast All-Pairs Shortest Paths Algorithm in Large Sparse GraphProceedings of the 37th International Conference on Supercomputing10.1145/3577193.3593728(277-288)Online publication date: 21-Jun-2023
https://dl.acm.org/doi/10.1145/3577193.3593728
Xu X(2023)Path Inference Based on Voronoi GraphAdvances and Trends in Artificial Intelligence. Theory and Applications10.1007/978-3-031-36822-6_13(153-158)Online publication date: 15-Jul-2023
https://doi.org/10.1007/978-3-031-36822-6_13
Gaihre ALi XLiu H(2022)gSoFa: Scalable Sparse Symbolic LU Factorization on GPUsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2021.309031633:4(1015-1026)Online publication date: 1-Apr-2022
https://doi.org/10.1109/TPDS.2021.3090316
Xia YJiang PAgrawal GRamnath R(2022)Scaling and Selecting GPU Methods for All Pairs Shortest Paths (APSP) Computations2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS53621.2022.00027(190-200)Online publication date: May-2022
https://doi.org/10.1109/IPDPS53621.2022.00027
Huang PChen MChen KYe SYu L(2022)Study on an emergency evacuation model considering information transfer and rerouting: Taking a simplified H-shape metro station hall as an exampleTunnelling and Underground Space Technology10.1016/j.tust.2022.104485124(104485)Online publication date: Jun-2022
https://doi.org/10.1016/j.tust.2022.104485
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

Media

Figures

Other

Tables

View Table of Contents