###
DOI:
Journal of Software:2000.11(7):889-898

在消息传递并行机上的高效的最小生成树算法
王光荣,顾乃杰
(中国科学技术大学计算机科学技术系,合肥,230027)
An Efficient Parallel Minimum Spanning Tree Algorithm on Message Passing Parallel Machine
WANG Guang-rong,GU Nai-jie
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 2883   Download 2987
Received:January 21, 1999    Revised:July 20, 1999
> 中文摘要: 基于传统的Borǔ vka串行最小生成树算法,提出了一个在消息传递并行机上的高效的最小生成树算法.并且采用3种方法来提高该算法的效率,即通过两趟合并及打包收缩的方法来减少通信开销,通过平衡数据分布的办法使各个处理器的计算量平衡.该算法的计算和通信复杂度分别为O(n2/p)和O((tsp+twn)n/p).在曙光-1000并行机上运行的实际效果是,对于有10 000个顶点的稀疏图,通过16个节点的运行加速比是12.
Abstract:An efficient parallel minimum spanning tree is proposed based on the classical Borüvka's algorithm on message passing parallel machine. Three methods were used to improve its efficiency, including two-phase union and packaged contraction for reducing communication costs, and the balanced data distribution for computation balance in each processor. The computation and communication costs of the algorithm are O(n2/p) and O((tsp+twn)n/p). On Dawning-1000 parallel machine, it gets a speedup of 12 on 16 processors with a sparse graph of 10 000 vertices.
文章编号:     中图分类号:    文献标志码:
基金项目:This research is supported by the Ph.D.Foundation of State Education Commission of China(国家教育部博士点基金No.9703825) This research is supported by the Ph.D.Foundation of State Education Commission of China(国家教育部博士点基金No.9703825)
Foundation items:
Reference text:

王光荣,顾乃杰.在消息传递并行机上的高效的最小生成树算法.软件学报,2000,11(7):889-898

WANG Guang-rong,GU Nai-jie.An Efficient Parallel Minimum Spanning Tree Algorithm on Message Passing Parallel Machine.Journal of Software,2000,11(7):889-898