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

发布时间：2018-04-13 21:41

本文选题：人工智能 + 约束满足问题　；参考：《计算机研究与发展》2017年03期

【摘要】：弧相容算法是约束满足问题的基本压缩求解空间算法之一,很多优秀的高级算法都以高性能的弧相容算法作为核心.近年来,以GPU为计算工具加速并行计算被用来尝试解决许多问题.基于GPU和基本的并行算法,提出一种适合GPU运算的约束网络表示模型N-E,给出其生成算法BuildNE.结合细粒度的弧相容算法——AC4,基于N-E模型提出AC4的并行化算法AC4~(GPU)与改进算法AC4~(GPU)+,使弧相容算法得以扩展到GPU上执行.实验结果验证了该算法的可行性,与AC4算法的比较,其在一些规模较小的问题上取得了10%~50%的加速,在一些规模较大的问题上则加速1~2个数量级.为今后进一步在GPU上以并行形式解决其他约束满足问题提供了一种核心算法方案.
[Abstract]:Arc compatibility algorithm is one of the basic space compression algorithms for constrained satisfaction problems. Many excellent high-level algorithms have high performance arc compatibility algorithm as the core.In recent years, GPU as a computing tool to accelerate parallel computing has been used to try to solve many problems.Based on GPU and basic parallel algorithm, a constrained network representation model N-Ewhich is suitable for GPU operation is proposed, and its build algorithm is given.Combined with fine-grained arc compatibility algorithm AC4, based on N-E model, the parallel algorithm AC4 / GPU of AC4 and the improved algorithm AC4 / GPU) are proposed, so that the arc compatibility algorithm can be extended to execute on GPU.The experimental results show that the algorithm is feasible. Compared with the AC4 algorithm, it has achieved 10% acceleration on some smaller problems and 1 ~ 2 orders of magnitude on some larger problems.This paper provides a core algorithm for solving other constraint satisfaction problems on GPU in parallel.
【作者单位】：吉林大学计算机科学与技术学院;符号计算与知识工程教育部重点实验室(吉林大学);
【基金】：国家自然科学基金项目(61272208,61373052) 吉林省自然科学基金项目(20140101200JC)~~
【分类号】：TP18

【相似文献】