Dynamic circuit generation for solving specific problem instances of Boolean satisfiability
- 27 November 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 196-204
- https://doi.org/10.1109/fpga.1998.707897
Abstract
Optimization and query problems provide the best clear opportunity for configurable computing systems to achieve a significant performance advantage over ASICs. Programmable hardware can be optimized to solve a specific problem instance that only needs to be solved once, and the circuit can be thrown away after its single execution. This paper investigates the applicability of this technology to solving a specific query problem, known as Boolean Satisfiability. We provide a system for capturing the complete execution cost of this approach, by accounting for CAD tool execution time. The key to this approach is to circumvent the standard CAD tools and directly generate circuits at runtime. A set of example circuits is presented as part of the system evaluation, and a complete implementation on the Xilinx XC6216 FPGA is presented.Keywords
This publication has 14 references indexed in Scilit:
- Improving functional density through run-time constant propagationPublished by Association for Computing Machinery (ACM) ,1997
- Satisfiability on reconfigurable hardwarePublished by Springer Nature ,1997
- A case study of partially evaluated hardware circuits: Key-specific DESPublished by Springer Nature ,1997
- Configurable computing solutions for automatic target recognitionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1996
- Expressing dynamic reconfiguration by partial evaluationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1996
- An assessment of the suitability of FPGA-based systems for use in digital signal processingPublished by Springer Nature ,1995
- Performance-driven constructive placementPublished by Association for Computing Machinery (ACM) ,1990
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970
- A Computing Procedure for Quantification TheoryJournal of the ACM, 1960