2014 · 36 citations · 13 references
ComputingComputer ScienceHigh-performance ComputingAlgorithmsParallel AlgorithmsParallel ComputingGraph AlgorithmsGraphics Processing Unit ArchitectureGraphics Processing Unit ComputingGraphics Processing UnitsParallel ArchitecturesShortest Path AlgorithmsAll-pairs Shortest PathsComplexityGpu Parallel AlgorithmsGraph ProcessingMulti-gpu ComputingPlanar GraphsShortest Path In Planar GraphsShortest Path Problems
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-War shall 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.
13
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations