Boolean satisfiability on a graphics processor Conference Paper uri icon

abstract

  • 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. 2010 ACM.

name of conference

  • Proceedings of the 20th symposium on Great lakes symposium on VLSI

published proceedings

  • Proceedings of the 20th symposium on Great lakes symposium on VLSI

author list (cited authors)

  • Gulati, K., & Khatri, S. P.

citation count

  • 7

complete list of authors

  • Gulati, Kanupriya||Khatri, Sunil P

publication date

  • January 2010