分裂合并算法的优化及并行化方案  

An Effective Merge Criterion and Two Parallel Strategies for Split and Merge Algorithm

作　　者：龚雪晶[1] 慈林林[1] 姚康泽[2] 

机构地区：[1]北京理工大学计算机科学技术学院 [2]第二炮兵装备研究院,北京100085

出　　处：《北京理工大学学报》2007年第9期801-806,共6页Transactions of Beijing Institute of Technology

基　　金：国家部委预研项目(403050203)

摘　　要：研究了分裂合并算法的优化方法,并提出相应的并行化方案。修改了图像在区域合并阶段中原有的最佳合并原则,增加了满足合并条件的相邻区域的匹配率,减少算法迭代次数。为解决合并阶段的负载不平衡提出了一种新方法;同时针对分裂阶段的负载不平衡,提出了一种新的分裂合并算法并行方案,并分析了两种并行方案在负载平衡,通信复杂度及可扩展性的差异。实验结果表明,对分裂合并算法的优化能有效提高算法的效率,其并行化方案切实可行。To improve the split and merge algorithm and propose its parallel strategies, a modified criterion based on the best merge criterion （BMC） is proposed at the merge stage. It can increase the number of matching for neighboring regions that satisfy the merge criterion and decrease the number of iterations. A new method is put forward to solve the load imbalance at the merge stage by using the available parallel strategy. A new parallel strategy is given based on master-slave programming model to settle the load imbalance caused by the split stage. These two parallel strategies are discussed by analyzing their difference in load balance, communication complexity and scalability. Experimental results showed that the methods improved the efficiency of the split and merge algorithm, and the parallel strategies to be applicable.

关 键 词：分裂合并算法 合并原则 负载平衡 加速比 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术] TP301.6[自动化与计算机技术—计算机科学与技术]