A bitstream reconfigurable FPGA implementation of the WSAT algorithm
- 1 February 2001
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Very Large Scale Integration (VLSI) Systems
- Vol. 9 (1) , 197-201
- https://doi.org/10.1109/92.920833
Abstract
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.Keywords
This publication has 7 references indexed in Scilit:
- A massively-parallel easily-scalable satisfiability solver using reconfigurable hardwarePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Solving satisfiability problems using logic synthesis and reconfigurable hardwarePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Accelerating Boolean satisfiability with configurable hardwarePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- An FPGA implementation of GENET for solving graph coloring problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- FPGA based runtime configurable clause evaluatorfor SAT problemsElectronics Letters, 1999
- Reconfigurable architectures: A new vision for optimization problemsPublished by Springer Nature ,1997
- Solving satisfiability problems using field programmable gate arrays: First resultsPublished by Springer Nature ,1996