在消息传递并行机上的高效的最小生成树算法

• 作者: 王光荣 顾乃杰
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: MPP (message passing parallel) MST (minimum spanning tree) 并行算法 通信 非关联图
• 年，卷（期）: 2000,（7）
• 页码范围: 889-898
• 页数: 10页
• 分类号: TP301
• 字数: 1661字
• 语种: 中文

摘要

基于传统的Borǔ vka串行最小生成树算法,提出了一个在消息传递并行机上的高效的最小生成树算法.并且采用3种方法来提高该算法的效率,即通过两趟合并及打包收缩的方法来减少通信开销,通过平衡数据分布的办法使各个处理器的计算量平衡.该算法的计算和通信复杂度分别为O(n2/p)和O((tsp+twn)n/p.在曙光-1000并行机上运行的实际效果是,对于有10 000个顶点的稀疏图,通过16个节点的运行加速比是12.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	顾乃杰	中国科学技术大学计算机科学技术系	83	347	9.0	12.0
2	王光荣	中国科学技术大学计算机科学技术系	2	13	2.0	2.0