| 摘要: |
| 用倍增技术在带有Wormhole路由技术的n×n二维网孔机器上提出了时间复杂度为O(log2n)的连通分量和传递闭包并行算法,并在此基础上提出了一个时间复杂度为O(log3n)的最小生成树并行算法.这些都改进了Store-and-Forward路由技术下的时间复杂度下界O(n).同其他运行在非总线连接分布式存储并行计算机上的算法相比,此连通分量和传递闭包算法的时间复杂度是最优的. |
| 关键词: 连通分量 图论算法 并行算法 虫孔路由 网孔机器 |
| DOI： |
| 分类号: |
| 基金项目:国家教育部博士点基金资助项目(9703825) |
|
| Connected Component Algorithm on Wormhole Routed Mesh and Its Applications |
|
XU Yin-long,WAN Ying-yu,GU Xiao-dong,CHEN Guo-liang
|
| Abstract: |
| 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(log2n). A minimum spanning tree (MST) parallel algorithm running on the same model in time O(log3n) 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. |
| Key words: connected component graph algorithm parallel algorithm wormhole routing mesh |
