Area-Driven Resynthesis Technique for FPGAs
Publication Date: 2005-Dec-07
The IP.com Prior Art Database
In this work, we introduce a resynthesis technique to reduce the area of a synthesized circuit. The technique is based on Boolean satisfiability (SAT) and is general enough to be applied to any FPGA architecture. Our resynthesis algorithm is able to map a small subcircuit into the smallest possible number of logic elements needed to realize its functionality. This can be used to build a cache of optimal resynthesis structures. We prove the validity of this technique by iteratively applying it to small portions of circuits that have already been technology mapped by the best available mapping algorithms for FPGAs. In many cases, the optimal mapping of the subcircuit uses less logic elements than is obtained by the technology mapping algorithm. We show that for some circuits the total area improvement can be up to 67%.
tion 3, we can express the output of the network fnet as a
Boolean formula involving the variables i0 . . . in, the virtual
configuration bits V1 . . . Vm and the truth table configura- tion bits L1 . . . Lo. Given this formula, we ask the question: is there an assignment to V1 . . . Vm and L1 . . . Lo that will cause fnet(i0, i1, . . . , in, V1 . . . Vm, L1 . . . Lo) to be identical
to f(i0, i1, . . . , in) for all values of i0 . . . in? This question can be answered exactly with Boolean satisfiability (SAT): Given a Boolean expression in Conjunctive-Normal-Form (CNF), where the expression consists of a product of clauses and each clause consists of a sum of literals, seek an assign- ment of variables so that each clause has at least one literal set to true. The solution space of this problem grows ex-
Due to the popularity of LUT-based FPGA architectures [1, 18], a large body of existing work has studied area-driven LUT mapping algorithms. We review some of the key liter- ature here.
The area minimization problem was shown to be NP-hard for LUTs of input size four and greater [15, 10]. Thus, heuristics are necessary to solve the area minimization prob- lem in a reasonable amount of computation time. Early work considered the decomposition of circuits into a set of trees which were then mapped for area [13, 11]. The area minimization problem for trees is much simpler and can be solved optimally using dynamic programming. However, real circuits are rarely structured as trees and tree decompo- sition prevents much of the optimization that can take place across tree boundaries.
In a duplication-free mapping, each gate in the initial cir- cuit is covered by a single LUT in the mapped circuit. The area minimization problem in duplication-free mapping can be solved optimally by decomposing the circuit into a set of maximum fanout free cones (MFFCs) which are then mapped for area . Although the area minimal duplication- free mapping is significantly smaller than the area minimal tree mapping, the controlled use of duplication can lead to further area savings. In , heuristics are used to mark a set of gates as duplicable. Area optimization is then con- sidered within an extended fanout free cone (EFFC) where an EFFC is an MFFC that has been extended to include duplicable gates.
There is also a new class of algorithms that attempt to re- duce the area of a circuit that has already been technology mapped using Sets of Pairs of Functions to be Di[ff]erentiated SPFDs ([12, 19]). SPFDs involve using "don't care" infor- mation to express alternative functional permissibilities for the truth table of each LUT in a particular design. In many cases, it allows us to explore alternate and equivalent func- tional representations of the circuit which may reduce area.
Virtual Configuration Bit
Figure 3: Configurable Virtual Network