Efficient Multi-GPU Computation of All-Pairs Shortest Paths
Los Alamos National Laboratory, Los Alamos, NM, USA
IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2014
@article{djidjev2014efficient,
title={Efficient Multi-GPU Computation of All-Pairs Shortest Paths},
author={Djidjev, Hristo and Thulasidasan, Sunil and Chapuis, Guillaume and Andonov, Rumen and Lavenier, Dominique},
year={2014}
}
We describe a new algorithm for solving the all-pairs shortest-path (APSP) problem for planar graphs and graphs with small separators that exploits the massive on-chip parallelism available in today’s Graphics Processing Units (GPUs). Our algorithm, based on the Floyd-Warshall algorithm, has near optimal complexity in terms of the total number of operations, while its matrix-based structure is regular enough to allow for efficient parallel implementation on the GPUs. By applying a divide-and-conquer approach, we are able to make use of multi-node GPU clusters, resulting in more than an order of magnitude speedup over the fastest known Dijkstra-based GPU implementation and a two-fold speedup over a parallel Dijkstra-based CPU implementation.
December 18, 2013 by hgpu
