IEEE Transactions on Very Large Scale Integration (VLSI) Systems · 2004 · 52 citations · 18 references
EngineeringComputer EngineeringComputer ScienceComputer ArchitectureField-programmable Gate ArraysReconfigurable ComputingEmbedded Reconfigurable SystemsField-programmable Gate Array ArchitectureFpga ArchitectureProgrammable Logic DevicesReconfigurable Embedded SystemsReconfigurable System ArchitectureBoolean SatisfiabilityBoolean Satisfiability ProblemCompilation For Reconfigurable HardwareConfigurable ArchitecturesEmbedded MemoryReconfigurable Computing ArchitecturesReconfigurable Hardware ArchitectureSatisfiability
This paper introduces a novel approach for solving the Boolean satisfiability (SAT) problem by combining software and configurable hardware. The suggested technique avoids instance-specific hardware compilation and, as a result, allows the total problem solving time to be reduced compared to other approaches that have been proposed. Moreover, the technique permits problems that exceed the resources of the available reconfigurable hardware to be solved. The paper presents the results obtained with some of the DIMACS benchmarks and a comparison of our implementation with other available SAT solvers based on reconfigurable hardware. The hardware part of the satisfier was realized on Virtex XCV812E FPGA, which has a large volume of embedded memory blocks that provide direct support for the proposed approach.
18
A machine program for theorem-proving
Martin Davis, George Logemann, Donald Loveland · Communications of the ACM · 1962 · 3.2K citations · Full text
Matthew W. Moskewicz, Conor Madigan, Ying Zhao et al. · 2001 · 2.9K citations
Synthesis and optimization of digital circuits
Choice Reviews Online · 1994 · 2.4K citations
Engineering, Computer Engineering, Electrical Engineering +17
Using CSP look-back techniques to solve real-world SAT instances
Roberto J. Bayardo, Robert Schrag · 1997 · 598 citations