Practical parallel Union-Find algorithms for transitive closure and clustering
Practical parallel Union-Find algorithms for transitive closure and clustering
复制标题
用于传递闭包和聚类的实用并行并查算法
DOI：
--
复制
发表时间：
1989
影响因子：
1.5
通讯作者：
J. Polito
中科院分区：
文献类型：
--
作者：
G. Cybenko;T. G. Allen;J. Polito
在经典序列并查找算法的基础上，描述并实现了用于计算二元关系传递闭包的实用并行算法，适用于共享内存和分布式内存并行计算机。通过实用算法，我们指的是对处理器数量有限的并行系统有效的算法，而不是处理器数量随问题规模增长的算法。传递闭包对于将许多应用程序问题分解为独立的子问题非常有用。这些实现是在ENCORE multiax共享内存机和NCUBE超立方体上实现的。我们的实现表明，传递闭包计算对于分布式内存并行机器来说本质上是困难的，因为需要全局信息。相比之下，我们在共享内存机器上的结果显示了出色的速度提升。
Practical parallel algorithms, based on classical sequential Union-Find algorithms for computing transitive closures of binary relations, are described and implemented for both shared memory and distributed memory parallel computers. By practical algorithms, we mean algorithms that are efficient for parallel systems with bounded numbers of processors as opposed to algorithms where the number of processors grows with the problem size. Transitive closures are useful for decomposing many applications problems into independent subproblems. The implementations were on an ENCORE Multimax shared memory machine and an NCUBE hypercube. Our implementations indicate that transitive closure computations are intrinsically difficult for distributed memory parallel machines because of the need for global information. By contrast, our results for shared memory machines exhibited excellent speedups.