Using reconfigurable computing techniques to accelerate problems in the CAD domain: A case study with Boolean satisfiability

Peixin Zhong, Pranav Ashar, Sharad Malik, Margaret Rose Martonosi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

37 Scopus citations

Abstract

The Boolean satisfiability problem lies at the core of several CAD applications, including automatic test pattern generation and logic synthesis. This paper describes and evaluates an approach for accelerating Boolean satisfiability using configurable hardware. Our approach harnesses the increasing speed and capacity of field-programmable gate arrays by tailoring the SAT-solver circuit to the particular formula being solved. This input-specific technique gets high performance due both to (i) a direct mapping of Boolean operations to logic gates, and (ii) large amounts of fine grain parallelism in the implication processing. Overall, these strategies yields impressive speedups (>200× in many cases) compared to current software approaches, and they require only modest amounts of hardware. In a broader sense, this paper alerts the hardware design community to the increasing importance of input-specific designs, and documents their promise via a quantitative study of input-specific SAT solving.

Original languageEnglish (US)
Title of host publicationProceedings 1998 - Design and Automation Conference, DAC 1998
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages194-199
Number of pages6
ISBN (Print)078034409X
StatePublished - 1998
Event35th Design and Automation Conference, DAC 1998 - San Francisco, United States
Duration: Jun 15 1998Jun 19 1998

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X

Other

Other35th Design and Automation Conference, DAC 1998
Country/TerritoryUnited States
CitySan Francisco
Period6/15/986/19/98

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Control and Systems Engineering
  • Electrical and Electronic Engineering
  • Modeling and Simulation
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Using reconfigurable computing techniques to accelerate problems in the CAD domain: A case study with Boolean satisfiability'. Together they form a unique fingerprint.

Cite this