基于GPU的约束网络模型和并行弧相容算法

A Constraint Network Model and Parallel Arc Consistency Algorithms Based on GPU

弧相容算法是约束满足问题的基本压缩求解空间算法之一,很多优秀的高级算法都以高性能的弧相容算法作为核心.近年来,以GPU为计算工具加速并行计算被用来尝试解决许多问题.基于GPU和基本的并行算法,提出一种适合GPU运算的约束网络表示模型N-E,给出其生成算法BuildNE.结合细粒度的弧相容算法——AC4,基于N-E模型提出AC4的并行化算法AC4^(GPU)与改进算法AC4^(GPU)+,使弧相容算法得以扩展到GPU上执行.实验结果验证了该算法的可行性,与AC4算法的比较,其在一些规模较小的问题上取得了10%~50%的加速,在一些规模较大的问题上则加速1~2个数量级.为今后进一步在GPU上以并行形式解决其他约束满足问题提供了一种核心算法方案.

Constraint satisfaction problem is a popular paradigm to deal with combinatorial problems in artificial intelligence.Arc consistency（AC）is one of basic solution compression algorithms of constraint satisfaction problem,which is also a core algorithm of many excellent advanced algorithms.When constraints are considered independently,AC corresponds to the strongest form of local reasoning.An effective underlying AC can improve the efficiency of reducing the search space.Recent years,GPU has been used for constituting many super computers,which solve many problems in parallel.Based on GPU’s computation,this paper proposes a constraint networks presentation model N-E and its parallel generation algorithm BuildNE.According to fine-grained arc consistency AC4,a parallel edition AC4 GPU and its improved algorithm—AC4GPU＋,are proposed.The two parallel algorithms extend arc consistency to GPU.Experimental results verify the feasibility of these new algorithms.Compared with AC4,the parallel versions have made the 10% to 50% acceleration in some smaller instances,and obtained 1to 2orders of magnitude in some bigger instances.They provide a core algorithm to other constraint satisfaction problem solving in parallel for further study.