Write a Blog >>
Tue 25 Feb 2020 14:25 - 14:50 - Graph (Mediterranean Ballroom) Chair(s): Jiajia Li

We show how to exploit graph sparsity in the \FW algorithm for the all-pairs shortest path (\APSP) problem. \FW 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, \FW 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 \FW and Gaussian elimination, and thereby 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 a baseline \FW that does not exploit sparsity. Our experiments suggest that \FW algorithm can be competitive with Dijkstra’s algorithm (the algorithmic core of Johnson’s algorithm) for several classes sparse graphs.

Tue 25 Feb
Times are displayed in time zone: (GMT-07:00) Tijuana, Baja California change

14:00 - 15:15: Main Conference - Graph (Mediterranean Ballroom)
Chair(s): Jiajia LiPacific Northwest National Laboratory
PPoPP-2020-papers14:00 - 14:25
PPoPP-2020-papers14:25 - 14:50
piyush kumar saoOak Ridge National Lab, Ramki KannanOak Ridge National Laboratory, Prasun GeraGeorgia Institute of Technology, Rich VuducGeorgia Institute of Technology
PPoPP-2020-papers14:50 - 15:15
Ghadeer AlabandiTexas State University, Evan PowersTexas State University, Martin BurtscherTexas State University