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 ...

Get Reconfigurable Computing now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.