首页 | 本学科首页   官方微博 | 高级检索  
     检索      

分裂合并算法的优化及并行化方案
引用本文:龚雪晶,慈林林,姚康泽.分裂合并算法的优化及并行化方案[J].北京理工大学学报,2007,27(9):801-806.
作者姓名:龚雪晶  慈林林  姚康泽
作者单位:1. 北京理工大学,计算机科学技术学院,北京,100081;装备指挥技术学院,北京,101416
2. 北京理工大学,计算机科学技术学院,北京,100081
3. 第二炮兵装备研究院,北京,100085
摘    要:研究了分裂合并算法的优化方法,并提出相应的并行化方案.修改了图像在区域合并阶段中原有的最佳合并原则,增加了满足合并条件的相邻区域的匹配率,减少算法迭代次数.为解决合并阶段的负载不平衡提出了一种新方法;同时针对分裂阶段的负载不平衡,提出了一种新的分裂合并算法并行方案,并分析了两种并行方案在负载平衡,通信复杂度及可扩展性的差异.实验结果表明,对分裂合并算法的优化能有效提高算法的效率,其并行化方案切实可行.

关 键 词:分裂合并算法  合并原则  负载平衡  加速比  分裂合并算法  优化方法  并行化  并行方案  Algorithm  Split  and  Merge  Strategies  Parallel  Criterion  效率  结果  实验  差异  可扩展性  通信复杂度  负载平衡  分析  负载不平衡  迭代次数  匹配率
文章编号:1001-0645(2007)09-0801-06
收稿时间:2007/1/25 0:00:00
修稿时间:2007-01-25

An Effective Merge Criterion and Two Parallel Strategies for Split and Merge Algorithm
GONG Xue-jing,CI Lin-lin and YAO Kang-ze.An Effective Merge Criterion and Two Parallel Strategies for Split and Merge Algorithm[J].Journal of Beijing Institute of Technology(Natural Science Edition),2007,27(9):801-806.
Authors:GONG Xue-jing  CI Lin-lin and YAO Kang-ze
Institution:School of Computer Science and Technology,Beijing Institute of Technology,Beijing 100081,China; The Academy of Equipment Command and Technology,Beijing 101416,China;School of Computer Science and Technology,Beijing Institute of Technology,Beijing 100081,China;The Equipment Institute of PLA's Second Artillery,Beijing 100085,China
Abstract: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.
Keywords:split and merge algorithm  merge criteria  load balance  speedup
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《北京理工大学学报》浏览原始摘要信息
点击此处可从《北京理工大学学报》下载免费的PDF全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号