CUD@SAT: SAT Solving on GPUs.
A. Dal Palù, A. Dovier, A. Formisano, and E. Pontelli.
Journal of Experimental & Theoretical Artificial Intelligence (JETAI),
Volume 27(3), July 2015, pp. 293-316.
(draft) DOI: 10.1080/0952813X.2014.954274
Abstract
The parallel computing power offered by Graphical Processing Units (GPUs) has been recently exploited to support general purpose applications—by exploiting the availability of general API and the SIMT-style parallelism present in several classes of problems (e.g., numerical simulations, matrix manipulations)— where relatively simple computations need to be applied to all items in large sets of data.
This paper investigates the use of GPUs in parallelizing a class of search problems, where the combinatorial nature leads to large parallel tasks and relatively less natural symmetries. Specifically, the investigation focuses on the well-known Satisfiability Testing (SAT) problem and on the use of the NVIDIA CUDA architecture, one of the most popular platforms for GPU computing. The paper explores ways to identify strong sources of GPU-style parallelism from SAT solving. The paper describes experiments with different design choices and evaluates the results. The outcomes demonstrate the potential for this approach, leading to one order of magnitude of speedup using a simple NVIDIA platform