GPU Acceleration of BCP Procedure for SAT Algorithms

The satisfiability problem (SAT) is widely applicable and one of the most basic NP-complete problems. This problem has been required to be solved as fast as possible because of its significance, but it takes exponential time in the worst case to solve. Therefore, we aim to save the computation time by parallel computing on a GPU. We propose parallelization of BCP (Boolean Constraint Propagation) procedure, one of the most effective techniques for SAT, on a GPU. For a 2.93GHz Intel Core i3 CPU and an NVIDIA GeForce GTX480, our experiment shows that the GPU accelerates our SAT solver based on our BCPembedded divide and conquer algorithm 6.7 times faster than the CPU counterpart

可满足性问题（SAT）应用广泛，是最基本的NP完全问题之一。由于其重要性，人们要求尽可能快地解决该问题，但在最坏情况下，解决它需要指数级的时间。因此，我们的目标是通过在图形处理器（GPU）上进行并行计算来节省计算时间。我们提出在GPU上对布尔约束传播（BCP）过程进行并行化，这是解决SAT问题最有效的技术之一。对于2.93GHz的英特尔酷睿i3 CPU和英伟达精视GTX480，我们的实验表明，GPU使我们基于嵌入BCP的分治算法的SAT求解器比对应的CPU求解器快6.7倍。