TY - GEN
T1 - Using reconfigurable computing techniques to accelerate problems in the CAD domain
T2 - 35th Design and Automation Conference, DAC 1998
AU - Zhong, Peixin
AU - Ashar, Pranav
AU - Malik, Sharad
AU - Martonosi, Margaret Rose
N1 - Publisher Copyright:
© 1998 ACM.
PY - 1998
Y1 - 1998
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0031624029&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0031624029&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0031624029
SN - 078034409X
T3 - Proceedings - Design Automation Conference
SP - 194
EP - 199
BT - Proceedings 1998 - Design and Automation Conference, DAC 1998
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 15 June 1998 through 19 June 1998
ER -