Efficient Multi-GPU Algorithm for All-Pairs Shortest Paths

Abstract : The shortest-path problem is a fundamental computer science problem with applications in diverse areas such as transportation, robotics, network routing, and VLSI design. The problem is to find paths of minimum weight between pairs of nodes in edge-weighted graphs, where the weight of a path p is defined as the sum of the weights of all edges of p. The distance between two nodes v and w is defined as the minimum cost of a path between v and w. The objective of the all-pairs shortest path (APSP) problem is to compute the distances between all pairs of nodes of a graph. In this paper, we present a new approach to solving the APSP problem for planar graphs that exploits the massive on-chip parallelism available in today's Graphics Processing Units (GPU). To harness this computing power for solving path problems in planar graphs, we exploit the community structure of input graphs and reformulate the problem in terms of matrix computations. Our algorithm, based on the Floyd-Warshall algorithm, has near quadratic complexity with respect to the number of nodes, 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 fastest known Dijkstra-based GPU implementation and a two-fold speedup over a parallel Dijkstra-based CPU implementation.
Type de document :
Communication dans un congrès
IPDPS 2014, May 2014, Phoenix, United States. 2014
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

Contributeur : Guillaume Chapuis <>
Soumis le : lundi 18 novembre 2013 - 16:08:42
Dernière modification le : vendredi 16 novembre 2018 - 01:40:19
Document(s) archivé(s) le : samedi 8 avril 2017 - 00:56:40


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00905738, version 1


Guillaume Chapuis, Hristo Djidjev, Rumen Andonov, Sunil Thulasidasan, Dominique Lavenier. Efficient Multi-GPU Algorithm for All-Pairs Shortest Paths. IPDPS 2014, May 2014, Phoenix, United States. 2014. 〈hal-00905738〉



Consultations de la notice


Téléchargements de fichiers