IEEE Transactions on Very Large Scale Integration (VLSI) Systems · 2001 · 27 citations · 8 references
EngineeringComputer EngineeringComputer ScienceComputer ArchitectureField-programmable Gate ArraysReconfigurable ComputingEmbedded Reconfigurable SystemsField-programmable Gate Array ArchitectureFpga ArchitectureProgrammable Logic DevicesReconfigurable Embedded SystemsReconfigurable System ArchitectureBoolean SatisfiabilityBoolean Satisfiability ProblemConstraintsField-programmable Gate Array-based Embedded SystemsField-programmable Gate Arrays (Fpgas)Reconfigurable Computing ArchitecturesResponse TimeSatisfiability
A field programmable gate array (FPGA) implementation of a coprocessor which uses the WSAT algorithm to solve Boolean satisfiability problems is presented. The input is a SAT problem description file from which a software program directly generates a problem-specific circuit design which can be downloaded to a Xilinx Virtex FPGA device and executed to find a solution. On an XCV300, problems of 50 variables and 170 clauses can be solved. Compared with previous approaches, it avoids the need for resynthesis, placement, and routing for different constraints. Our coprocessor is eminently suitable for embedded applications where energy, weight and real-time response are of concern.
8
A new method for solving hard satisfiability problems
Bart Selman, Hector J. Levesque, David G. M. Mitchell · 1992 · 1.2K citations
Where the really hard problems are
Peter Cheeseman, Bob Kanefsky, William M. Taylor · 1991 · 1K citations
Noise strategies for improving local search
Bart Selman, Henry Kautz, Brain Cohen · 1994 · 761 citations
Accelerating Boolean satisfiability with configurable hardware
Peixin Zhong, Margaret Martonosi, Pranav Ashar et al. · 2002 · 78 citations
Using reconfigurable computing techniques to accelerate problems in the CAD domain
Peixin Zhong, Pranav Ashar, Sharad Malik et al. · 1998 · 46 citations · Full text