###
DOI:
Journal of Software:2001.12(2):233-240

虫孔路由Mesh上的连通分量算法及其应用
许胤龙,万颖瑜,顾晓东,陈国良
(中国科学技术大学 计算机科学技术系,安徽 合肥 230027 国家高性能计算中心,安徽 合肥 230027)
Connected Component Algorithm on Wormhole Routed Mesh and Its Applications
XU Yin-long,WAN Ying-yu,GU Xiao-dong,CHEN Guo-liang
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 2678   Download 2744
Received:August 04, 1999    Revised:November 12, 1999
> 中文摘要: 用倍增技术在带有Wormhole路由技术的n×n二维网孔机器上提出了时间复杂度为O(log2n)的连通分量和传递闭包并行算法,并在此基础上提出了一个时间复杂度为O(log3n)的最小生成树并行算法.这些都改进了Store-and-Forward路由技术下的时间复杂度下界O(n).同其他运行在非总线连接分布式存储并行计算机上的算法相比,此连通分量和传递闭包算法的时间复杂度是最优的.
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.
文章编号:     中图分类号:    文献标志码:
基金项目:国家教育部博士点基金资助项目(9703825) 国家教育部博士点基金资助项目(9703825)
Foundation items:
Reference text:

许胤龙,万颖瑜,顾晓东,陈国良.虫孔路由Mesh上的连通分量算法及其应用.软件学报,2001,12(2):233-240

XU Yin-long,WAN Ying-yu,GU Xiao-dong,CHEN Guo-liang.Connected Component Algorithm on Wormhole Routed Mesh and Its Applications.Journal of Software,2001,12(2):233-240