虫孔路由Mesh上的连通分量算法及其应用
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家教育部博士点基金资助项目(9703825)


Connected Component Algorithm on Wormhole Routed Mesh and Its Applications
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    用倍增技术在带有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.

    参考文献
    相似文献
    引证文献
引用本文

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

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:1999-08-04
  • 最后修改日期:1999-11-12
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号