On Area/Depth Trade-off in LUT-Based FPGA Technology MappingJason Cong and Yuzheng DingDepartment of Computer ScienceUniversity of California, Los Angeles, CA 90024AbstractIn this paper we study the area and depth trade-off in LUT basedFPGA technology mapping. Starting from a depth-optimal mappingsolution, we perform a number of depth relaxation operations toobtain a new network with bounded increase in depth and advanta-geous to subsequent re-mapping for area minimization. We thenre-map the resulting network to obtain an area-minimized mappingsolution. By gradually increasing the depth bound, for each designwe are able to produce a set of mapping solutions with smooth areaand depth trade-off. For the area minimization step, we havedeveloped an optimal algorithm for computing an area-minimummapping solution without node duplication. Experimental resultsshow that our solution sets outperform the solutions produced bymany existing mapping algorithms in terms of both area and depthminimization.1. IntroductionThe Field programmable gate array (FPGA) has become avery popular technology in VLSI ASIC design and systemprototyping. The lookup table (LUT) based FPGAs are pro-duced by several FPGA manufacturers [16,8], in which thebasic programmable logic block is a K-input lookup table thatcan implement any Boolean function of up to K variables.The technology mapping problem for LUT-based FPGAdesigns is to convert a general Boolean network into a func-tionally equivalent K-LUT network.Previous technology mapping algorithms for LUT-basedFPGA designs can be roughly divided into three categoriesaccording to their optimization objectives: the area minimiza-tion algorithms [6, 10,12, 9, 15, 13], the depth minimizationalgorithms [7, 11, 13,2,3], and the algorithms that maximizeroutability [14, 1]. Most of these mapping algorithms arebased on heuristic techniques, except FlowMap [3] whichguarantees to produce depth-optimal mapping solutions. Itremains open if the area-optimal mapping problem for LUT-based FPGAs can be solved efficiently.The common limitation of the existing algorithms is thatfor a given design, each algorithm produces only a singlemapping solution optimized under a fixed objective, whileother good mapping solutions under different optimizationobjectives are ignored. Figure 1 compares the 5-LUT map-ping results by some existing algorithms on an MCNC bench-mark circuit named rot. The depths and the numbers ofLUTs of the solutions by different algorithms varysignificantly. In general, the area-minimized solutions havemuch larger depth, while the depth-minimized solutions usemuch more LUTs. However, in practice the best design maynot come from either one of these two extremes. It is impor-tant to let the system designer have the flexibility to choosefrom a set of mapping solutions with smooth trade-offbetween area and depth.In this paper we study the trade-off between area and depthin LUT-based FPGA technology mapping. Specifically, weare interested in obtaining a set of mapping solutions for eachdesign, which can meet various area and depth requirements.In practice, the designer usually has to produce the mostcompact design satisfying certain depth bound determined bythe performance specification. To satisfy such a need, ouralgorithm produces a set of area-minimized mapping solu-tions under various depth bounds.The basic approach of our algorithm is as follows. Startingfrom a depth-optimal mapping solution (computed by theFlowMap algorithm [3]), we perform a number of depthrelaxation operations to obtain a new network with boundedincrease in depth so that it is advantageous to subsequent re-mapping for area minimization. We then re-map the result-ing network to obtain an area-minimized mapping solutionwith bounded depth. By gradually increasing the depthbounds, for each design we are able to produce a set of map-ping solutions with smooth area and depth trade-off. As thecore of the area minimization step, we have developed apolynomial-time algorithm for computing an area-optimalmapping solution without node duplication for a generalBoolean network, which makes a significant step towardscomplete understanding of the general area optimizationproblem in FPGA technology mapping.Due to page limitation, detailed algorithm descriptions andthe proofs of the theorems are not included in this paper.They can be found in [4].2. Problem FormulationA general Boolean network is represented as a DAG wherea node represents a logic gate and a directed edge <i, j >exists if the output of gate i is an input of gate j. A primaryinput (PI) node has no incoming edge and a primary output(PO) node has no outgoing edge. We use input (v) to denotethe set of nodes which are the fanins of node v, and output (v)to denote the set of nodes which are the fanouts of node v.Given a subgraph H of the Boolean network, input(H)denotes the set of distinct nodes outside H which supplyinputs to the gates in H. The level (or depth) of a node v isthe number of edges on the longest path from any PI node tov. The depth of a network is the largest node level in theDepth# of 5-LUTs200 300250681012MIS-pga [10]Chortle-crf [6]FlowMap [3]DAG-Map [2]MIS-pga(delay) [11]Chortle-d [7]07911Figure 1 Mapping solutions of various algorithms for rot (K=5).network. A Boolean network is K-bounded if| input(v)| ≤ K for each node v. In the rest of this paper, weonly consider K-bounded networks.1For a node v in the network, a cone of v, denoted Cv, is asubgraph of logic gates (excluding PIs) consisting of v and itspredecessors such that any path connecting a node in Cvandv lies entirely in Cv. We call v the root of Cv. A fanout-freecone (FFC) at v, denoted FFCv, is a cone of v such that forany node u≠v in FFCv, output (u) ⊆ FFCv. A K-feasiblecone of v is a cone Cvsuch thatinput(Cv)≤ K.If a K-LUT LUTvimplements (covers) a K-feasible FFC ofv, we say that LUTvimplements node v and that v is the rootof LUTv. If the K-feasible cone Cvis not fanout free, wehave to duplicate the non-root nodes in Cvthat have fanoutsoutside of Cvin order to cover Cvby a K-LUT. Given a K-bounded network, the technology mapping problem for K-LUT based FPGA designs is to cover the network with K-feasible FFCs (possibly with node duplications). A