Work-efficient parallel union-find: Work-efficient parallel union-find
Work-efficient parallel union-find: Work-efficient parallel union-find
复制标题
高效工作的并行联合查找： 高效工作的并行联合查找
DOI：
10.1002/cpe.4333
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Wu, Kun-Lung
中科院分区：
文献类型：
--
作者：
Simsiri, Natcha;Tangwongsan, Kanat;Tirthapura, Srikanta;Wu, Kun-Lung
增量图连通性（IGC）问题是维护一种数据结构，该数据结构可以快速回答图中的两个给定顶点是否连通，同时允许更多的边添加到图中。IGC是一个基本问题，可以在顺序设置中使用经典的并集查找问题的解决方案来有效地解决。然而，顺序解决方案不足以处理现代大型，快速变化的图，其中边缘更新达到非常高的速率。我们提出了第一个用于union-find的共享内存并行数据结构（相当于IGC），它既可以证明是有效的（即，执行的工作不比最好的顺序对应物多），又具有多对数并行深度。我们还提出了一个简单的算法，略差的理论性质，但它更容易实现，并具有良好的实际性能。我们在具有各种度分布的大型图流上的实验表明，它具有良好的实用性能，能够使用20核机器每秒处理数亿条边。
The incremental graph connectivity (IGC) problem is to maintain a data structure that can quickly answer whether two given vertices in a graph are connected, while allowing more edges to be added to the graph. IGC is a fundamental problem and can be solved efficiently in the sequential setting using a solution to the classical union‐find problem. However, sequential solutions are not sufficient to handle modern‐day large, rapidly‐changing graphs where edge updates arrive at a very high rate. We present the first shared‐memory parallel data structure for union‐find (equivalently, IGC) that is both provably work‐efficient (ie, performs no more work than the best sequential counterpart) and has polylogarithmic parallel depth. We also present a simpler algorithm with slightly worse theoretical properties, but which is easier to implement and has good practical performance. Our experiments on large graph streams with various degree distributions show that it has good practical performance, capable of processing hundreds of millions of edges per second using a 20‐core machine.