11110

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

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

}

Download Download (PDF)   View View   Source Source   

897

views

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-2017 hgpu.org

All rights belong to the respective authors

Contact us: