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.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [47 references]  Display  Hide  Download

https://hal.inria.fr/hal-01245837
Contributor : Arthur Charguéraud <>
Submitted on : Friday, December 18, 2015 - 5:07:32 PM
Last modification on : Monday, November 26, 2018 - 1:28:01 PM
Document(s) archivé(s) le : Friday, May 5, 2017 - 6:20:21 PM

File

pdfs_sc15.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

467

Files downloads

197