A Work-Efficient Algorithm for Parallel Unordered Depth-First Search

Umut A. Acar 1, 2 Arthur Charguéraud 3, 4 Mike Rainey 2
3 TOCCATA - Certified Programs, Certified Tools, Certified Floating-Point Computations
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : Advances in processing power and memory technology have made multicore computers an important platform for high-performance graph-search (or graph-traversal) algorithms. Since the introduction of multicore, much progress has been made to improve parallel breadth-first search. However, less attention has been given to algorithms for unordered or loosely ordered traversals. We present a parallel algorithm for unordered depth-first-search on graphs. We prove that the algorithm is work efficient in a realistic algorithmic model that accounts for important scheduling costs. This work-efficiency result applies to all graphs, including those with high diameter and high out-degree vertices. The algorithmic techniques behind this result include a new data structure for representing the frontier of vertices in depth-first search, a new amortization technique for controlling excess parallelism, and an adaptation of the lazy-splitting technique to depth first search. We validate the theoretical results with an implementation and experiments. The experiments show that the algorithm performs well on a range of graphs and that it can lead to significant improvements over comparable algorithms.
Type de document :
Communication dans un congrès
Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, Nov 2015, Austin, Texas, United States. <10.1145/2807591.2807651>
Liste complète des métadonnées


https://hal.inria.fr/hal-01245837
Contributeur : Arthur Charguéraud <>
Soumis le : vendredi 18 décembre 2015 - 17:07:32
Dernière modification le : vendredi 17 février 2017 - 16:10:47
Document(s) archivé(s) le : vendredi 5 mai 2017 - 18:20:21

Fichier

pdfs_sc15.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Umut A. Acar, Arthur Charguéraud, Mike Rainey. A Work-Efficient Algorithm for Parallel Unordered Depth-First Search. Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, Nov 2015, Austin, Texas, United States. <10.1145/2807591.2807651>. <hal-01245837>

Partager

Métriques

Consultations de
la notice

149

Téléchargements du document

116