0 0 9 views

**Unformatted text preview:**

On Area Depth Trade off in LUT Based FPGA Technology Mapping Jason Cong and Yuzheng Ding Department of Computer Science University of California Los Angeles CA 90024 Abstract In this paper we study the area and depth trade off in LUT based FPGA technology mapping Starting from a depth optimal mapping solution we perform a number of depth relaxation operations to obtain a new network with bounded increase in depth and advantageous to subsequent re mapping for area minimization We then re map the resulting network to obtain an area minimized mapping solution By gradually increasing the depth bound for each design we are able to produce a set of mapping solutions with smooth area and depth trade off For the area minimization step we have developed an optimal algorithm for computing an area minimum mapping solution without node duplication Experimental results show that our solution sets outperform the solutions produced by many existing mapping algorithms in terms of both area and depth minimization 1 Introduction The Field programmable gate array FPGA has become a very popular technology in VLSI ASIC design and system prototyping The lookup table LUT based FPGAs are produced by several FPGA manufacturers 16 8 in which the basic programmable logic block is a K input lookup table that can implement any Boolean function of up to K variables The technology mapping problem for LUT based FPGA designs is to convert a general Boolean network into a functionally equivalent K LUT network Previous technology mapping algorithms for LUT based FPGA designs can be roughly divided into three categories according to their optimization objectives the area minimization algorithms 6 10 12 9 15 13 the depth minimization algorithms 7 11 13 2 3 and the algorithms that maximize routability 14 1 Most of these mapping algorithms are based on heuristic techniques except FlowMap 3 which guarantees to produce depth optimal mapping solutions It remains open if the area optimal mapping problem for LUTbased FPGAs can be solved efficiently The common limitation of the existing algorithms is that for a given design each algorithm produces only a single mapping solution optimized under a fixed objective while other good mapping solutions under different optimization objectives are ignored Figure 1 compares the 5 LUT mapping results by some existing algorithms on an MCNC benchmark circuit named rot The depths and the numbers of LUTs of the solutions by different algorithms vary significantly In general the area minimized solutions have much larger depth while the depth minimized solutions use much more LUTs However in practice the best design may not come from either one of these two extremes It is important to let the system designer have the flexibility to choose from a set of mapping solutions with smooth trade off between area and depth In this paper we study the trade off between area and depth in LUT based FPGA technology mapping Specifically we are interested in obtaining a set of mapping solutions for each design which can meet various area and depth requirements In practice the designer usually has to produce the most compact design satisfying certain depth bound determined by the performance specification To satisfy such a need our algorithm produces a set of area minimized mapping solutions under various depth bounds The basic approach of our algorithm is as follows Starting from a depth optimal mapping solution computed by the FlowMap algorithm 3 we perform a number of depth relaxation operations to obtain a new network with bounded increase in depth so that it is advantageous to subsequent remapping for area minimization We then re map the resulting network to obtain an area minimized mapping solution with bounded depth By gradually increasing the depth bounds for each design we are able to produce a set of mapping solutions with smooth area and depth trade off As the core of the area minimization step we have developed a polynomial time algorithm for computing an area optimal mapping solution without node duplication for a general Boolean network which makes a significant step towards complete understanding of the general area optimization problem in FPGA technology mapping Due to page limitation detailed algorithm descriptions and the proofs of the theorems are not included in this paper They can be found in 4 2 Problem Formulation A general Boolean network is represented as a DAG where a 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 primary input PI node has no incoming edge and a primary output PO node has no outgoing edge We use input v to denote the 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 supply inputs to the gates in H The level or depth of a node v is the number of edges on the longest path from any PI node to v The depth of a network is the largest node level in the Depth 12 11 MIS pga 10 Chortle crf 6 10 9 MIS pga delay 11 8 7 6 FlowMap 3 0 200 250 DAG Map 2 Chortle d 7 300 of 5 LUTs Figure 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 we only consider K bounded networks 1 For a node v in the network a cone of v denoted Cv is a subgraph of logic gates excluding PIs consisting of v and its predecessors such that any path connecting a node in Cv and v lies entirely in Cv We call v the root of Cv A fanout free cone FFC at v denoted FFCv is a cone of v such that for any node u v in FFCv output u FFCv A K feasible cone of v is a cone Cv such that input Cv K If a K LUT LUTv implements covers a K feasible FFC of v we say that LUTv implements node v and that v is the root of LUTv If the K feasible cone Cv is not fanout free we have to duplicate the non root nodes in Cv that have fanouts outside of Cv in order to cover Cv by a K LUT Given a Kbounded network the technology mapping problem for KLUT based FPGA designs is to cover the network with Kfeasible FFCs possibly with node duplications A technology mapping solution S is a DAG where each node is a Kfeasible FFC equivalently a K LUT and the edge Cu Cv exists if u is in input Cv Figure 2 shows a Boolean network and two mapping solutions one with node duplication and the other without node duplication We say an LUT