Efficient Multi-GPU Computation of All-Pairs Shortest Paths

Hristo Djidjev, Sunil Thulasidasan, Guillaume Chapuis, Rumen Andonov, Dominique Lavenier
Los Alamos National Laboratory, Los Alamos, NM, USA
IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2014


   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},



Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

* * *

HGPU group © 2010-2022 hgpu.org

All rights belong to the respective authors

Contact us: