主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
许胤龙,万颖瑜,顾晓东,陈国良.虫孔路由Mesh上的连通分量算法及其应用.软件学报,2001,12(2):233-240
虫孔路由Mesh上的连通分量算法及其应用
Connected Component Algorithm on Wormhole Routed Mesh and Its Applications
投稿时间:1999-08-04  修订日期:1999-11-12
DOI:
中文关键词:  连通分量  图论算法  并行算法  虫孔路由  网孔机器
英文关键词:connected component  graph algorithm  parallel algorithm  wormhole routing  mesh
基金项目:国家教育部博士点基金资助项目(9703825)
作者单位
许胤龙 中国科学技术大学 计算机科学技术系,安徽 合肥 230027 国家高性能计算中心,安徽 合肥 230027 
万颖瑜 中国科学技术大学 计算机科学技术系,安徽 合肥 230027 国家高性能计算中心,安徽 合肥 230027 
顾晓东 中国科学技术大学 计算机科学技术系,安徽 合肥 230027 国家高性能计算中心,安徽 合肥 230027 
陈国良 中国科学技术大学 计算机科学技术系,安徽 合肥 230027 国家高性能计算中心,安徽 合肥 230027 
摘要点击次数: 3031
全文下载次数: 2988
中文摘要:
      用倍增技术在带有Wormhole路由技术的n×n二维网孔机器上提出了时间复杂度为O(log2n)的连通分量和传递闭包并行算法,并在此基础上提出了一个时间复杂度为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(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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利