Research On GPU To Parallel Constraint Satisfaction Problem

Constraint satisfaction problem is a important aspect in the field of artificial intelligence,the purpose is to find a(group)solution for combination problem,this process is called constraint solving.To explore the efficient algorithm is the main topics of the current study.Today,backtrack search is the most popular algorithm of constraint solving.One of the most efficient complement algorithm for constraint solving is using some kinds of consistency to reduce the search space.Consistency technology has always been a core issue in the field of constraint solving.The common consistency techniques are: AC(Arc Consistency),PC(Path Consistency),max RPC(max-Restricted Path Consistency)and SAC(Singleton Arc Consistency).Different consistency has different ability of reducing value.Solving program instantiates variables constantly during the backtracking search.The criteria for selection of variables and values called heuristic.Some researches shows that variable and value ordering heuristics have a major impact on the efficiency of constraint solving.Common variable heuristics include: dom,dom/deg,dom/wdeg etc.Due to the limitation of processor,many hardware manufacturers have given up Moore's Law and pivot to push out more efficient computing devices such as multi-processor and GPU.It promotes the development of parallel programs.PU has been widely used in high-performance computing as an efficient processor.Its range of applications including graphic images,scientific research,industrial design and other fields.Currently,many classic algorithms can be achieved through parallelization of a big increase in efficiency.In this paper,we optimize the existing algorithms based on GPU and some basic parallel algorithms,the specific tasks are as follows: 1.Propose a constraint networks presentation model N-E.2.Propose a parallel edition AC4 GPU and its improved algorithm — AC4GPU+ according tofine-grained arc consistency AC4.3.Propose a AC framework algorithm — ACGPU,it can expand multiple constraintchecking methods,and a bit check method based on bitwise presentation.4.Propose SACGPU+bit,which check whether each value satisfy SAC concurrently,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 1 to 2 orders of magnitude in some bigger instances.SACGPU+bit also generally superior to the current mainstream SAC algorithm.Finally,we discussed the topic of acceleration of solving CSP problems based on GPU,and summarizes several domestic and foreign research.