人工智能：基于GPU的约束网络模型和并行弧相容算法

《人工智能：基于GPU的约束网络模型和并行弧相容算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、计算机研究与发展DOI：１０．７５４４桙issn１０００‐１２３９．２０１７．２０１５０９１２JournalofComputerResearchandDevelopment５４（３）：５１４５２８，２０１７基于GPU的约束网络模型和并行弧相容算法李哲李占山李颖（吉林大学计算机科学与技术学院长春１３００１２）（符号计算与知识工程教育部重点实验室（吉林大学）长春１３００１２）（zslizsli＠１６３．com）AConstraintNetworkModelandParallelArcConsistencyAlgorithmsBased

2、onGPULiZhe，LiZhanshan，andLiYing（CollegeofComputerScienceandTechnology，JilinUniversity，Changchun１３００１２）（KeyLaboratoryofSymbolicComputationandKnowledgeEngineering（JilinUniversity），MinistryofEducation，Changchun１３００１２）AbstractConstraintsatisfactionproblemisapopularparadig

3、mtodealwithcombinatorialproblemsinartificialintelligence．Arcconsistency（AC）isoneofbasicsolutioncompressionalgorithmsofconstraintsatisfactionproblem，whichisalsoacorealgorithmofmanyexcellentadvancedalgorithms．Whenconstraintsareconsideredindependently，ACcorrespondstothes

4、trongestformoflocalreasoning．AneffectiveunderlyingACcanimprovetheefficiencyofreducingthesearchspace．Recentyears，GPUhasbeenusedforconstitutingmanysupercomputers，whichsolvemanyproblemsinparallel．BasedonGPU摧scomputation，thispaperproposesaconstraintnetworkspresentationmod

5、elN‐EanditsparallelgenerationalgorithmBuildNE．Accordingtofine‐grainedarcconsistencyAC４，aGPUGPUparalleleditionAC４anditsimprovedalgorithm—AC４＋，areproposed．ThetwoparallelalgorithmsextendarcconsistencytoGPU．Experimentalresultsverifythefeasibilityofthesenewalgorithms．Compa

6、redwithAC４，theparallelversionshavemadethe１０％to５０％accelerationinsomesmallerinstances，andobtained１to２ordersofmagnitudeinsomebiggerinstances．Theyprovideacorealgorithmtootherconstraintsatisfactionproblemsolvinginparallelforfurtherstudy．Keywordsartificialintelligence；const

7、raintsatisfactionproblem（CSP）；arcconsistency（AC）；GPU；computeunifieddevicearchitecture（CUDA）摘要弧相容算法是约束满足问题的基本压缩求解空间算法之一，很多优秀的高级算法都以高性能的弧相容算法作为核心．近年来，以GPU为计算工具加速并行计算被用来尝试解决许多问题．基于GPU和基本的并行算法，提出一种适合GPU运算的约束网络表示模型N‐E，给出其生成算法BuildNE．结合GPUGPU细粒度的弧相容算法———AC４，基于N‐E模型提出AC４的并行化

8、算法AC４与改进算法AC４＋，使弧相容算法得以扩展到GPU上执行．实验结果验证了该算法的可行性，与AC４算法的比较，其在一些规模较小的问题上取得了１０％～５０％的加速，在一些规模较大的问题上则加速１～２个数量级．为今后进一步在GPU上以并行形式解决