Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

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

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
Complete list of metadata

Cited literature [47 references]  Display  Hide  Download
Contributor : Arthur Charguéraud Connect in order to contact the contributor
Submitted on : Friday, December 18, 2015 - 5:07:32 PM
Last modification on : Saturday, June 25, 2022 - 10:18:36 PM
Long-term archiving on: : Friday, May 5, 2017 - 6:20:21 PM


Files produced by the author(s)



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⟩



Record views


Files downloads