摘要
基于传统的 Borǔ vka串行最小生成树算法 ,提出了一个在消息传递并行机上的高效的最小生成树算法 .并且采用 3种方法来提高该算法的效率 ,即通过两趟合并及打包收缩的方法来减少通信开销 ,通过平衡数据分布的办法使各个处理器的计算量平衡 .该算法的计算和通信复杂度分别为 O( n2 / p)和 O( ( tsp+twn) n/ p.在曙光- 10 0 0并行机上运行的实际效果是 ,对于有 10 0 0 0个顶点的稀疏图 ,通过 16个节点的运行加速比是
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(n 2/p) and O((t sp+t wn)n/p) . On Dawning 1000 parallel machine, it gets a speedup of 12 on 16 processors with a sparse graph of 10 000 vertices.
出处
《软件学报》
EI
CSCD
北大核心
2000年第7期889-898,共10页
Journal of Software
基金
This research is supported by the Ph.D.Foundation of State Education Commission of China (国家教育部博士点基金
No.970 382 5
关键词
消息传递
并行计算机
最小生成树算法
MPP (message passing parallel), MST (minimum spanning tree), parallel algorithm, communication, disjoint set.