All-Pairs Shortest Path Algorithms for Planar Graph for GPU-Accelerated Clusters

Hristo Djidjev 1 Guillaume Chapuis 2 Rumen Andonov 2 Sunil Thulasidasan 1 Dominique Lavenier 2
1 LANL - Los Alamos National Laboratory
2 GenScale - Scalable, Optimized and Parallel Algorithms for Genomics
Inria Rennes – Bretagne Atlantique , IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
Abstract : • We develop a new approach for the All-Pairs Shortest Path problem in planar graphs. • We target execution on large CPU–GPU clusters and graphs with millions of vertices. • We design a centralized (master/slave) and a decentralized (distributed) version. • Our algorithms are work-efficient and allow a high-degree of parallelism. • Our algorithms are significantly faster than the previous ones. a b s t r a c t We present a new approach for solving the All-Pairs Shortest-Path (APSP) problem for planar graphs that exploits the massive on-chip parallelism available in today's Graphics Processing Units (GPUs). We describe two new algorithms based on our approach. Both algorithms use Floyd–Warshall method, have near optimal complexity in terms of the total number of operations, while their 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 twofold speedup over a parallel Dijkstra-based CPU implementation.
Type de document :
Article dans une revue
Journal of Parallel and Distributed Computing, Elsevier, 2015, 85, pp.91-103. 〈10.1016/j.jpdc.2015.06.008〉
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01235348
Contributeur : Dominique Lavenier <>
Soumis le : jeudi 3 décembre 2015 - 08:37:16
Dernière modification le : jeudi 15 novembre 2018 - 11:57:53
Document(s) archivé(s) le : samedi 29 avril 2017 - 03:09:26

Fichier

APSP-JPDC2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

INRIA | IRISA | UR1-UFR-ISTIC | CENTRALESUPELEC | UNIV-RENNES

Citation

Hristo Djidjev, Guillaume Chapuis, Rumen Andonov, Sunil Thulasidasan, Dominique Lavenier. All-Pairs Shortest Path Algorithms for Planar Graph for GPU-Accelerated Clusters. Journal of Parallel and Distributed Computing, Elsevier, 2015, 85, pp.91-103. 〈10.1016/j.jpdc.2015.06.008〉. 〈hal-01235348〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

555

Téléchargements de fichiers

513

Contact


archive-ouverte@inria.fr