 |
Center for Nonlinear Studies |
The All-Pair Shortest Path (APSP) problem asks to compute the shortest paths or distances between all pairs of nodes of a graph. Once computed, APSP distances allows linear computations of various other graph measures such as the betweenness centrality of the nodes of a network and the radius and diameter of the graph. These measures have applications in domains such as social network analysis, protein-protein interactions, and road network problems.
Unfortunately, the APSP problem is hard to efficiently implement on the GPU platform. Efficient sequential algorithms have number of operations roughly quadratic to the number of the nodes of the graph, but their data communication structure is unsuitable for the GPU architecture, while the algorithms that have nice structures run in cubic time.
We propose a novel algorithm for computing APSP and its efficient distributed GPU implementation. For graphs with good community structure, the total number of operations of our algorithm is almost optimal (close to quadratic), but it has a structure allowing both high parallelism and a regular data communication pattern suitable for GPU. Our implementation is geared towards solving APSP for large graphs. So far, instances of up to 512k vertices (corresponding to computing more than 200 billion shortest paths) have been solved in less than 6 minutes.
Host: Hristo Djidjev