Chapter 29. Boolean Satisfiability: Creating Solvers Optimized for Specific Problem Instances
Peixin ZhongDepartment of Electrical and Computer EngineeringMichigan State University
Margaret Martonosi, Sharad MalikDepartment of Electrical EngineeringPrinceton University
Boolean satisfiability (SAT) is a classic NP-complete problem with a broad range of applications. There have been many projects that use reconfigurable computing to solve it. This chapter presents a review of the subject with emphasis on a particular approach that employs a backtrack search algorithm and generates solver hardware according to the problem instance. This approach utilizes the reconfigurability and fine-grained parallelism provided by FPGAs.
The chapter is organized as ...