并行深度优先搜索在有向无环图中的应用与速度提升
15 浏览量
更新于2024-07-14
收藏 851KB PDF 举报
"这篇论文是关于并行深度优先搜索(Parallel Depth-First Search)在有向无环图(Directed Acyclic Graphs, DAGs)中的应用。作者Divyanshu Talwar和Viraj Parimi来自印度国际信息技术学院(IIIT Delhi)。论文探讨了DFS作为拓扑排序、连通性检测和平面性测试等任务基础的重要性，并提出了一种工作高效的工作流算法，用于并行执行DAG的DFS遍历。论文中还将对比这种并行算法与串行实现的性能提升。
深度优先搜索(DFS)是一种广泛使用的算法，它在图论和计算机科学中有许多应用。在有向无环图中，DFS可以有效地进行拓扑排序，确定节点间的依赖关系，以及进行连通性和平面性测试等。传统的DFS算法是一种顺序执行的过程，而本文关注的是如何通过并行化来提高效率。
论文的关键字包括：深度优先搜索、并行编程、有向无环图和工作高效算法。作者指出，传统的按字典序的DFS算法由Floyd在1967年提出，该算法会为图中的每个节点计算父节点信息、前序（开始时间）和后序（结束时间）。
文献调查部分，作者将有向无环图的DFS问题分为两类主要算法：(1)基于栈的算法和(2)基于树的算法。前者包括经典的DFS，如Tarjan的低点算法和Kosaraju的两次DFS，这些方法主要处理强连通分量和桥的检测；后者则包括像BFS（广度优先搜索）的变体，有时用于找到最短路径。这些传统算法在单线程环境下运行，而本文提出的并行算法旨在利用多核处理器的并行计算能力，以提高大规模图处理的效率。
在方法部分，作者可能详细介绍了他们提出的并行DFS算法的实现细节，包括如何分配任务、同步节点访问和避免死锁等问题。此外，实验部分可能会展示在不同规模的DAG上运行并行DFS和串行DFS的结果，比较两者在时间和空间复杂度上的差异，并提供速度提升的定量分析。
这篇论文对于理解并行算法如何优化DFS在有向无环图中的应用具有重要意义，对于并行计算和图算法研究者来说是一份有价值的资源。其贡献在于提供了更高效的工作流策略，以适应现代计算环境的需求，尤其是在大数据处理和高性能计算领域。"
Algorithm 2 Pre- and Post-Order (top-down traversal)
1: Initialize pre and post-order of every node to 0.
2: Find roots and insert them into queue Q.
3: while Q , {ϕ} do
4: for node p ∈ Q do in parallel
5: Let pre = pre-order(p) and post = post-order(p)
6: Let C
p
be a set of children of p and queue P = {ϕ}
7: for node i ∈ C
p
do in parallel
8: Set pre-order(i) = pre +
˜
ζ
i
9: Set post-order(i) = pre +
˜
ζ
i
10: Mark i incoming edge (p, i) as visited
11: Insert i into P if all incoming edges are visited
12: end for
13: Set pre-order(p) = pre + depth(p)
14: Set post-order(p) = post + (ζ
p
− 1)
15: end for
16: Set Q = P for the next iteration
17: end while
Denition 2. Let
P
r,p
= {r, i
1
, i
2
, .., i
k−1
, p}
and
Q
r,p
= {r, j
1
, j
2
, .., j
k−1
, p}
be two paths of potentially dierent
length to node p. We say that path P has the rst lexicographically smallest node and denote it by
P
r,p
< Q
r,p
(4)
when during the pair-wise comparison of the elements in the two paths going from left-to-right the path
P
r,p
has
the lexicographically smallest element in the rst mismatch.
For example, in Fig. 1 the two paths to node f are
P
r,p
= [a, b, e, f ]
Q
r,p
= [a, c, d, f ]
Clearly P
r,p
= [a, b, e, f ] ≤ Q
r,p
= [a, c, d, f ] as b ≤ c lexicographically.
Theorem 2. Let
P
r,p
= {r, i
1
, i
2
, .., i
k−1
, p}
and
Q
r,p
= {r, j
1
, j
2
, .., j
k−1
, p}
be two paths of potentially dierent
length to node p. If P
r,p
< Q
r,p
then P
r,p
is the path taken by DFS traversal.
Putting it all together, the parallel DFS algorithm can be written as Algorithm 4.
3 ANALYSIS
3.1 Complexity Analysis
The following denitions, lemmas and theorems establish the fact that the aforementioned algorithm is a
work-ecient one.
Denition 3. Let
k
i
be the number of elements inserted into the queue at iteration
i
and
k = max
i
k
i
in
Algorithms 1-3.
Denition 4. Let d
i
denote the degree of node i and d = max
i
d
i
denote the maximum degree in DAG.
Denition 5. Let δ
i
denote the minimum depth of node i and δ = max
i
δ
i
denote the diameter in a DAG.
3
剩余14页未读，继续阅读
2021-04-22 上传
2023-06-10 上传
2023-07-14 上传
2023-06-10 上传
2023-05-23 上传
2023-06-10 上传
2023-08-15 上传
2023-05-23 上传
2023-05-18 上传
weixin_38502929
- 粉丝: 7
- 资源: 959
我的内容管理
展开
最新资源
- 构建Cadence PSpice仿真模型库教程
- VMware 10.0安装指南：步骤详解与网络、文件共享解决方案
- 中国互联网20周年必读：影响行业的100本经典书籍
- SQL Server 2000 Analysis Services的经典MDX查询示例
- VC6.0 MFC操作Excel教程：亲测Win7下的应用与保存技巧
- 使用Python NetworkX处理网络图
- 科技驱动：计算机控制技术的革新与应用
- MF-1型机器人硬件与robobasic编程详解
- ADC性能指标解析：超越位数、SNR和谐波
- 通用示波器改造为逻辑分析仪：0-1字符显示与电路设计
- C++实现TCP控制台客户端
- SOA架构下ESB在卷烟厂的信息整合与决策支持
- 三维人脸识别：技术进展与应用解析
- 单张人脸图像的眼镜边框自动去除方法
- C语言绘制图形：余弦曲线与正弦函数示例
- Matlab 文件操作入门：fopen、fclose、fprintf、fscanf 等函数使用详解
