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

来源：计算机研究与发展杂志2017年第3期北京时间：

作者：李哲,李占山,李颖,

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

关键词：人工智能, 约束满足问题, 弧相容, 图形处理器, 计算统一设备架构,