A work-efficient algorithm for parallel unordered depth-first search
A work-efficient algorithm for parallel unordered depth-first search
复制标题
一种高效的并行无序深度优先搜索算法
DOI：
10.1145/2807591.2807651
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Mike Rainey
中科院分区：
文献类型：
--
作者：
Umut A. Acar;A. Charguéraud;Mike Rainey
处理能力和内存技术的进步使多核算计算机成为高性能图形搜索（或图形传播）算法的重要平台。自从引入多核心以来，已经取得了很多进展来改善平行广度优先的搜索。但是，对无序或松散有序的遍历算法的关注较少。我们提出了一种平行算法，用于在图形上进行无序的深度搜索。我们证明该算法在一个重要的计划成本的现实算法模型中是有效的。该工作效率结果适用于所有图，包括直径高且高度顶点的图。此结果背后的算法技术包括一种新的数据结构，用于在深度优先搜索中代表顶点的前沿，一种用于控制过剩并行性的新摊销技术，以及对懒惰技术的适应深度进行深度的首次搜索。我们通过实施和实验来验证理论结果。实验表明，该算法在一系列图范围内表现良好，并且可以导致对可比较算法的显着改善。
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.