Abstract
We show how to exploit graph sparsity in the Floyd-Warshall algorithm for the all-pairs shortest path (Apsp) problem. FloydWarshall 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 multithreaded 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.
Original language | English |
---|---|
Title of host publication | PPoPP 2020 - Proceedings of the 2020 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming |
Publisher | Association for Computing Machinery |
Pages | 250-261 |
Number of pages | 12 |
ISBN (Electronic) | 9781450368186 |
DOIs | |
State | Published - Feb 19 2020 |
Event | 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2020 - San Diego, United States Duration: Feb 22 2020 → Feb 26 2020 |
Publication series
Name | Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP |
---|
Conference
Conference | 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2020 |
---|---|
Country/Territory | United States |
City | San Diego |
Period | 02/22/20 → 02/26/20 |
Funding
This manuscript has been authored by UT-Battelle,LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. This research is partially support by Oak Ridge National Laboratory Director’s Research and Development Funding. Additional support comes from the Defense Advanced Research Projects Agency (DARPA) contract FA8750-18-2-0108, under the DARPA MTO Software Defined Hardware program, and the National Science Foundation (NSF) under Award 1710371. The publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan (http://energy.gov/downloads/ doe-public-access-plan).
Keywords
- Communication-avoiding algorithms
- Graph algorithm
- Shared-memory parallelism
- Sparse matrix computations