A fast SPFD-based rewiring technique
- 1 January 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 55-60
Abstract
Circuit rewiring can be used to explore a larger solution space by modifying circuit structure to suit a given optimization problem. Among several rewiring techniques that have been proposed, SPFD-based rewiring has been shown to be more effective in terms of solution space coverage. However, its adoption in practice has been limited due to its long runtime. We propose a novel SAT-based algorithm that is much faster than the traditional BDD-based methods. Unlike BDD-based methods that completely specify all pairs of SPFD using BDDs, our algorithm uses a few SAT instances to perform rewiring for a given wire without explicitly enumerating all SPFDs. Experimental results show that our algorithm's runtime is only 13% of that of a conventional one when each wire has at most 25 candidate wires and the runtime scales well with the number of candidate wires considered. Our approach evaluates each rewiring instance independently in the order of milliseconds, rendering deployment of an SPFD-based rewiring inside the optimization loop of synthesis tools a possibility.Keywords
This publication has 5 references indexed in Scilit:
- Using simulation and satisfiability to compute flexibilities in Boolean networksIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006
- SPFD-Based Flexible Transformation of LUT-Based FPGA CircuitsIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2005
- A new method to express functional permissibilities for LUT based FPGAs and its applications2002
- SPFD-based global rewiring2002
- SPFD: A new method to express functional flexibilityIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2000