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

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

Connected Component Algorithm on Wormhole Routed Mesh and Its Applications

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²n). A minimum spanning tree (MST) parallel algorithm running on the same model in time O(log³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.