并行图切割马尔可夫随机场算法设计

• 作 者: 王文涛 陈聪 李子茂
• 机 构: 中南民族大学计算机科学学院,湖北,武汉,430074
• 出 处: 武汉大学学报(工学版)
• 发表日期: 2010年01期
• 关键词: parallel Markov random field graph cut OpenMP irregular problem

图切割(Graph-Cut)算法被广泛应用于马尔可夫随机场,使得原NP问题转变为多项式时间近似求解问题.讨论了Yuri Boykov的图切割算法的并行能力,设计并实现了其增长(Grow)和收养(Adopt)步骤的并行算法.在增长函数中使用分支界限法的广度优先搜索,并使用扩展终止线程函数,提升算法的执行效率,并在上述2个函数中调用OpenMP3.0新加入的任务(Task)功能,解决其不规则(Irregular)算法.对p个处理器,最坏情况的运行时间从原来的O(bd/2+a+nr)缩短到O(bd/2/p