|
|
软件学报 2000
在消息传递并行机上的高效的最小生成树算法, PP. 889-898 Keywords: mpp,(message,passing,parallel),mst,(minimum,spanning,tree),并行算法,通信,非关联图. Abstract: 基于传统的borǔvka串行最小生成树算法，提出了一个在消息传递并行机上的高效的最小生成树算法.并且采用3种方法来提高该算法的效率，即通过两趟合并及打包收缩的方法来减少通信开销，通过平衡数据分布的办法使各个处理器的计算量平衡.该算法的计算和通信复杂度分别为o(n2/p)和o((tsp+twn)n/p).在曙光-1000并行机上运行的实际效果是，对于有10000个顶点的稀疏图，通过16个节点的运行加速比是12.
|
