基于GPU的并行约束满足问题的研究

发布时间：2018-05-19 11:26

本文选题：约束满足问题 + 单值弧相容　；参考：《吉林大学》2017年硕士论文

【摘要】：约束满足问题是人工智能领域的重要方面,目的是为组合问题找到一个(组)解,这个过程称作约束求解。探索高效的求解算法是当前研究的主要课题。目前最为流行的求解算法是回溯搜索算法,在回溯搜索的过程中使用相容性进行缩减搜索空间是最高效的完备求解算法之一。相容性技术一直是约束求解领域的核心问题。常见的相容性技术有:弧相容(Arc Consistency,AC),路径相容(Path Consistency,PC),最大限定路径相容(max-Restricted Path Consistency,max RPC)和单值弧相容(Singleton Arc Consistency,SAC)等,不同的相容性其删值能力各有不同。回溯搜索的过程不断进行着变量的实例化,挑选变量和值的标准称为启发式,研究表明,变量排序启发式和值排序启发式对于约束求解效率有着重大影响。常见的变量启发式有dom启发式、dom/deg启发式、dom/wdeg启发式等。由于处理器条件的限制,摩尔定律被放弃,诸多硬件厂商相继放弃了单核方案转而推出多核心及GPU等更高效的计算设备,这促进了并行程序的发展。GPU做为一种高效的处理器已被广泛使用于高性能计算之中,其应用范围包括图形图像、科学研究、工业设计等领域。当前很多经典串行算法,都可以经由并行化取得很大的效能提升。本文基于GPU及一些基本并行算法将现有的算法进行优化,具体工作如下:1.提出一种约束网络(constraint network)在GPU上表示的模型——N-E模型。2.提出在N-E模型上基于GPU的细粒度弧相容算法AC4GPU及其改进算法AC4GPU+。3.提出以并行的方式对约束进行检查的AC框架ACGPU,该框架可能扩展多种约束检查方法,本文给出一种基于二元表示的检查方法。4.提出基于GPU的单值弧相容算法SACGPU+bit,该算法将ACGPU算法作为底层算法并以二元表示作为底层数据结构。实验结果说明AC4GPU及AC4GPU+对比原算法在一些规模较小的问题上取得了10%~50%的加速,在一些规模较大的问题上则加速1~2个数量级。SACGPU+bit的算法效率也普遍优于当前主流SAC算法。最后本文对采用GPU加速CSP问题这个课题进行了展望,总结多个国内外的研究方向。
[Abstract]:Constraint satisfaction problem (CSP) is an important aspect of artificial intelligence, which aims to find a solution for combinatorial problem, which is called constraint solution. Exploring efficient algorithms is the main research topic. At present, the most popular algorithm is the backtracking search algorithm. It is one of the most efficient and complete algorithms to reduce the search space by using compatibility in the process of backtracking search. Compatibility technology has always been the core problem in the field of constraint solving. The common compatibility techniques are: Arc compatibility, path compatibility, max-Restricted Path contiguity max RPCs and single value arc compatible Singleton Arc consistencyssac, etc. Their erasure ability varies with each other. In the process of backtracking search variables are instantiated and the criteria for selecting variables and values are called heuristics. The research shows that the heuristics of variable ordering and value sorting have great influence on the efficiency of constraint solving. Common variable heuristics include dom heuristics / dom-deg heuristics and dom-wdeg heuristics. Due to processor constraints, Moore's Law has been abandoned, and many hardware manufacturers have abandoned single-core solutions and introduced more efficient computing devices such as multi-cores and GPU. This has promoted the development of parallel programs. GPU as an efficient processor has been widely used in high-performance computing. Its applications include graphics and images, scientific research, industrial design and other fields. At present, many classical serial algorithms can achieve great performance improvement by parallelization. This paper optimizes the existing algorithms based on GPU and some basic parallel algorithms. The specific work is as follows: 1. A constrained network constraint network model, N-E model. 2. 2, which is represented on GPU, is presented in this paper. A fine-grained arc compatibility algorithm (AC4GPU) based on GPU and its improved algorithm AC4GPU. 3 on N-E model are proposed. An AC framework, ACGPU, which checks constraints in a parallel manner, is proposed, which may extend a variety of constraint checking methods. In this paper, a binary representation based checking method .4. A single value arc compatible algorithm based on GPU, SACGPU bit. is proposed, which takes the ACGPU algorithm as the underlying algorithm and binary representation as the underlying data structure. The experimental results show that the AC4GPU and AC4GPU comparison algorithms have achieved 1050% acceleration on some small scale problems, and the algorithm efficiency of 1 ~ 2 orders of magnitude. SACGPU bit is generally superior to the current mainstream SAC algorithm. Finally, this paper looks forward to the problem of accelerating CSP with GPU, and summarizes many research directions at home and abroad.
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【相似文献】