SHARE
Research Highlight

A Supernodal All-Pairs Shortest Path Algorithm

Topic:
(a) Nested Dissection (ND) on a 5×5 grid graph. Under an ND ordering, we find a graph separator (highlighted in yellow) and label the nodes in the separator in the end. (b) Shows the adjacency matrix of the graph permuted in ND ordering. (c) The elimination tree captures the dependency in elimination of different nodes. (d) Shows the final block sparse matrix obtained. CSMD Computer Science and Mathematics ORNL
(a) Nested Dissection (ND) on a 5×5 grid graph. Under an ND ordering, we find a graph separator (highlighted in yellow) and label the nodes in the separator in the end. (b) Shows the adjacency matrix of the graph permuted in ND ordering. (c) The elimination tree captures the dependency in elimination of different nodes. (d) Shows the final block sparse matrix obtained.

The Science

The researchers from ORNL have developed a new and faster algorithm for the graph all-pair shortest-path (APSP) problem for structured sparse graphs. The new supernodal APSP algorithm exploits the structured sparsity in the graphs by using "fill-in reducing ordering" that is typically used with sparse Cholesky factorization for solving a system of linear equations.

The Impact

The Supernodal APSP requires far fewer floating-point operations to compute APSP and shows a perfect parallel scalability. We achieved more than 50x  speedup over the current state of the art for several graphs. This proposed algorithm is expected to speed-up many knowledge graph analytics applications such as Literature Based Discovery, where computing APSP is the main computational bottleneck. 

PI/Facility Lead(s): Thomas E Potok
Research Lead : Piyush Sao, CSMD, Oak Ridge National Laboratory
ASCR PM: Robinson Pino
Funding: DOE ASCR
Publication: Piyush Sao, Ramakrishnan Kannan, Prasun Gera, Richard W. Vuduc: A supernodal all-pairs shortest path algorithm. PPoPP 2020: 250-261