虫孔路由Mesh上的连通分量算法及其应用

Connected Component Algorithm on Wormhole Routed Mesh and Its Applications

用倍增技术在带有 Wormhole路由技术的 n× n二维网孔机器上提出了时间复杂度为 O( log2 n)的连通分量和传递闭包并行算法 ,并在此基础上提出了一个时间复杂度为 O( log3n)的最小生成树并行算法 .这些都改进了Store- and- Forward路由技术下的时间复杂度下界 O( n) .同其他运行在非总线连接分布式存储并行计算机上的算法相比 ,此连通分量和传递闭包算法的时间复杂度是最优的 .

A connected component and transitive closure parallel algorithm using pointer jumping technique is presented in this paper, which runs on n×n wormhole routed 2D mesh in time O (log 2 n ). A minimum spanning tree (MST) parallel algorithm running on the same model in time O (log 3 n) is also presented. These improve the lower time bound O(n) on n×n store and forward routed 2D mesh. Compared with other known algorithms running on various non bus\|connected parallel machines with distributed memory, the time complexity of the connected component and transitive closure parallel algorithm is optimal.