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

作     者：李哲 李占山 李颖 Li Zhe;Li Zhanshan;Li Ying

作者机构：吉林大学计算机科学与技术学院长春130012 符号计算与知识工程教育部重点实验室(吉林大学)长春130012 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2017年第54卷第3期

页      面：514-528页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金项目(61272208 61373052) 吉林省自然科学基金项目(20140101200JC)~~ 

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

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