Provably Fast and Space-Efficient Parallel Biconnectivity
Provably Fast and Space-Efficient Parallel Biconnectivity
复制标题
经证明快速且节省空间的并行双连接
DOI：
10.1145/3572848.3577483
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Sun, Yihan
中科院分区：
文献类型：
--
作者：
Dong, Xiaojun;Wang, Letong;Gu, Yan;Sun, Yihan
计算图的双连通分支是一个基本的图问题。经典的并行BCC算法是Tarjan-Vishkin算法，它在n个顶点和中边的图上具有O（n + m）的最优工作和多对数跨度。然而，Tarjan-Vishkin在实践中并没有广泛使用。我们认为原因是空间效率低下（它使用O（m）额外空间）。在实践中，现有的并行实现是基于呼吸优先搜索（BFS）。由于BFS的跨度与图的直径成正比，现有的并行BCC实现在大直径图上的性能较差，并且在许多现实世界的图上比顺序算法慢，我们提出了第一个并行B连通性算法（FAST-BCC），该算法具有最佳工作，多对数跨度，并且是空间有效的。我们的算法基于输入图的任何生成树创建骨架图。然后我们使用骨架的连接信息来计算原始输入的双连接性。我们详细分析了算法的正确性，并实现了FAST-BCC，并将其与已有的GBBS算法、Slota和Madduri算法以及顺序Hopcroft-Tarjan算法进行了比较。我们在96核机器上测试了27个具有不同边缘分布的图形。FAST-BCC是最快的onallgraphs。平均（几何平均），FAST-BCC比每个图上的最佳现有基线快3.1倍。
Computing biconnected components (BCC) of a graph is a fundamental graph problem. The canonical parallel BCC algorithm is the Tarjan-Vishkin algorithm, which hasO(n + m) optimal work and polylogarithmic span on a graph withnvertices andmedges. However, Tarjan-Vishkin is not widely used in practice. We believe the reason is the space-inefficiency (it usesO(m) extra space). In practice, existing parallel implementations are based on breath-first search (BFS). Since BFS has span proportional to the diameter of the graph, existing parallel BCC implementations suffer from poor performance on large-diameter graphs and can be slower than the sequential algorithm on many real-world graphs.We propose the first p arallel b iconnectivity algorithm (FAST-BCC) that has optimal work, polylogarithmic span, and is space-efficient. Our algorithm creates a skeleton graph based on any spanning tree of the input graph. Then we use the connectivity information of the skeleton to compute the biconnectivity of the original input. We carefully analyze the correctness of our algorithm, which is highly non-trivial.We implemented FAST-BCC and compared it with existing implementations, including GBBS, Slota and Madduri's algorithm, and the sequential Hopcroft-Tarjan algorithm. We tested them on a 96-core machine on 27 graphs with varying edge distributions. FAST-BCC is the fastest onallgraphs. On average (geometric means), FAST-BCC is 3.1× faster than thebest existing baselineon each graph.
登录
查看更多内容
DOI：
10.1109/ipdps.2018.00081
发表时间：
2017-10
期刊：
2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
影响因子：
--
作者：
N. Ben-David;G. Blelloch;Jeremy T. Fineman;Phillip B. Gibbons;Yan Gu;Charles McGuffey;Julian Shun
通讯作者：
N. Ben-David;G. Blelloch;Jeremy T. Fineman;Phillip B. Gibbons;Yan Gu;Charles McGuffey;Julian Shun
用于种族检测的高效访问历史记录
DOI：
10.1145/3409964.3461825
发表时间：
2022
期刊：
022 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX
影响因子：
--
作者：
Xu, Yifan;Zhou, Anchengcheng;Yin, Grace Q.;Agrawal, Kunal;Lee, I-Ting Angelina;Schardl, Tao B.
通讯作者：
Schardl, Tao B.
DOI：
10.1145/3210377.3210380
发表时间：
2018-05
期刊：
Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
G. Blelloch;Yan Gu;Yihan Sun;Julian Shun
通讯作者：
G. Blelloch;Yan Gu;Yihan Sun;Julian Shun
线性时间内的径向平面度测试和嵌入
DOI：
10.1007/978-3-540-24595-7_37
发表时间：
2003
期刊：
2011 7th International Wireless Communications and Mobile Computing Conference
影响因子：
--
作者：
C. Bachmaier;F. Brandenburg;Michael Forster
通讯作者：
Michael Forster
DOI：
10.1145/2935764.2935767
发表时间：
2016-07
期刊：
Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
N. Ben-David;G. Blelloch;Jeremy T. Fineman;Phillip B. Gibbons;Yan Gu;Charles McGuffey;Julian Shun
通讯作者：
N. Ben-David;G. Blelloch;Jeremy T. Fineman;Phillip B. Gibbons;Yan Gu;Charles McGuffey;Julian Shun