Boolean satisfiability on a graphics processor
Kanupriya Gulati, Sunil P. Khatri · 2010
Boolean Satisfiability (SAT) is a core NP-complete problem. Several heuristic software and hardware approaches have been proposed to solve this problem. In this paper we present a Boolean satisfiablity approach with a new GPU-enhanced variable ordering heuristic. Our results demonstrate that over several satisfiable and unsatisfiable benchmarks, our technique (MESP) performs better than MiniSAT. We show a 2.35× speedup on average, over 68 from the SAT Race (2008) competition.