GPU Parallelism for SAT Solving Heuristics

Modern SAT solvers employ a number of smart techniques and strategies to achieve maximum efficiency in solving the Boolean Satisfiability problem. Among all components of a solver, the branching heuristics plays a crucial role in affecting the performance of the entire solver. Traditionally, the main branching heuristics that have appeared in the literature have been classified as look-back heuristics or look-ahead heuristics. As SAT technology has evolved, the former have become more and more preferable, for their demand for less computational effort. Graphics Processor Units (GPUs) are massively parallel devices that have spread enormously over the past few decades and offer great computing power at a relatively low cost. We describe how to exploit such computational power to efficiently implement look-ahead heuristics. Our aim is to “rehabilitate” these heuristics, by showing their effectiveness in the contest of a parallel SAT solver.