Abstract:
Methods and systems improve mapping of LUT based FPGAs. In some embodiments, a topological sort is performed on a network to be mapped, whereby the network is represented as a Directed Acyclic Graph. The system locates feasible reconvergent paths existing from transitive fan-ins of individual nodes using a Reconvergent Path Locator for replicating fan-outs of the nodes in the DAG, and therefore improves the number of LUTs and the time consumed in the mapping process.

Description:
RELATED APPLICATION 
       [0001]    This application is a divisional of and claims priority to U.S. patent application Ser. No. 11/025,785, filed on Dec. 29, 2004, which in turn claims priority to Indian Patent Application No. 1639/DEL/2003, filed on Dec. 29, 2003, the disclosures of which are incorporated by reference herein. 
     
    
     BACKGROUND 
       [0002]    A programmable logic array device has a plurality of logic elements and an interconnect structure for conveying signals between logic elements. In LUT (Look Up Table) based FPGA&#39;s (Field Programmable Gate Arrays), mapping is done prior to the placement and routing of the design in an FPGA. The objective of LUT mapping is to reduce the area/depth of the mapped solution. 
         [0003]    In LUT based FPGA&#39;s, optimal mapping of gates into LUT&#39;s is done while ensuring that the number of transitive fan-ins to sink is always less than or equal to the number of LUT inputs.  FIG. 1  illustrates the mapping process as a part of the FPGA development flow.  1 . 1  in the figure indicates the Gate Level Netlist as an input to the Optimizer Block that outputs Optimized Gate Level Netlist  1 . 2 . The optimized netlist is then Mapped into LUT as shown in the  1 . 3  that is followed by Packing LUT&#39;s in to Programmable Logic Blocks (PLB&#39;s)  1 . 4 . Then the design is simulated for Placement and Routing  1 . 5 ,  1 . 6 . The bit stream is generated as in the Configuration Bits of the Design block  1 . 7 . The bit stream is then downloaded in the FPGA to configure the FPGA as shown in the block  1 . 8 . 
         [0004]      FIG. 2  illustrates a legacy Mapping process in LUT based FPGA&#39;s.  2 . 1  is Directed Acyclic Graph (DAG) that represents the mapping data as nodes, wherein the nodes in the DAG simulate the LUT&#39;s in the FPGA.  2 . 1  also illustrates initialization of the inputs to the LUT&#39;s (k) and the initialization of the fan-out factor. Block  2 . 2  illustrates performing a topological sort on the DAG. Block  2 . 3  illustrates the Computation of the Dependency variable for each node in the graph, whereby the dependency is computed keeping in view that the nodes are analyzed for their respective inputs and outputs. Block  2 . 4  performs check on the Dependency Variable till it is greater than the variable k. Block  2 . 5  shows the computation of the Priority Variable (Fc) for all the children of the node under consideration, and performing the same function for all other nodes in the Directed Acyclic Graph. Priority Variable (Fc) is a function of the following: 
         [0005]    Contribution Variable (Zc), where c in the suffix denotes the children of the node; 
         [0006]    Number of fan-outs (Oc) for the children of the node under consideration; and 
         [0007]    Fan-out Factor (FF) variable. 
         [0008]    Block  2 . 6  sorts the list of the children of the node under consideration in the descending order of their priority values followed by block  2 . 7  that assigns LUT&#39;s to the children of the node under consideration until the dependency variable is less than k plus one. 
         [0009]    Block  2 . 8  assigns a LUT to each output of a given node that has been left unassigned. 
         [0010]    The computations for the Contribution Variable, Dependency variable, and the Priority Function is as shown below: 
         [0011]    Let a given design be represented by a directed acyclic graph (DAG) G(V, E) where each vertex v in V represents a Boolean function and each directed edge (v, u) represents a connection between the output of v and the input of u. 
         [0012]    Let VI denote the set of nodes for which LUT is assigned. 
         [0013]    That is, VI={vεV:a LUT is assigned to v}. 
         [0014]    Contribution Zv: 
         [0015]    For each PI v, Zv=1, 
         [0016]    For each vεVI, Zv=1, 
         [0017]    For all the other vertices vεV, Z v =Z u1 +Z u2 + . . . +Z 1    
         [0018]    where u1, u2, . . . , u1 are all the children of v. 
         [0019]    Dependency dv: 
         [0020]    a) For each PI v, dv=1 
         [0021]    For all other vertices vεV, dv=Z u1 +Z u2 + . . . +Z 1  where u1, u2, . . . , u1 are all the children of v. 
         [0022]    Priority Function Fv: 
         [0000]        Fv=F ( Zv,Ov,FF )= Zv+FF*Ov    
         [0023]    Where Ov is the number fan outs of v and FF is a suitable fan out factor. 
         [0024]    The legacy Level Map method does not take into account of reconvergent paths and fan-out replication effectively, therefore it is essential to provide a system for optimizing design area in FPGA by exploring reconvergent paths in conjunction with fan-out replication in LUT mapping. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0025]      FIG. 1  illustrates an FPGA development flow and a process of mapping in it. 
           [0026]      FIG. 2  illustrates a flow diagram of a legacy mapping process. 
           [0027]      FIG. 3  illustrates a flow diagram of a system according to one or more embodiments. 
       
    
    
     DETAILED DESCRIPTION 
       [0028]    In one embodiment, a system for improved optimal mapping of LUT based FPGAs is provided that comprises: 
         [0029]    a Directed Acyclic Graph (DAG) representation of the network to be mapped, 
         [0030]    a sorter that operates on said DAG to reduce its complexity, 
         [0031]    a Dependency Definer that determines the dependency of each node in the DAG, 
         [0032]    a Reconvergent Path Locator (RPL) that determines feasible reconvergent paths from transitive fan-ins of each said node, 
         [0033]    a Priority Determiner (PD) that determines the priority of all the child nodes of each said node, 
         [0034]    a Node Sorter (NS) that sorts the list of child nodes in descending order of priority, 
         [0035]    a Mapper (M) that assigns LUT&#39;s to the child nodes from the beginning of said sorted list until the node dependency is less than one plus the number of LUTs, 
         [0036]    an Assignor (A) that assigns an LUT to each output of a particular node. 
         [0037]    In some embodiments, said sorter is a topological sorter. 
         [0038]    In some embodiments, said Node Sorter is a Child node sorter. 
         [0039]    In some embodiments, said Mapper is a LUT Mapper. 
         [0040]    In some embodiments, said Assignor is a LUT assignor. 
         [0041]    A method is discussed for optimal mapping of LUT based FPGA&#39;s, the method comprising: 
         [0042]    generating a Directed Acyclic Graph (DAG) representation of the network to be mapped, 
         [0043]    sorting the network in the DAG to reduce the complexity of the network, 
         [0044]    determining dependency of each node in the DAG, 
         [0045]    cating feasible reconvergent paths existing from transitive fan-ins of each node, 
         [0046]    determining the priority of all the child nodes of each node, 
         [0047]    sorting the child nodes in the descending order of their priority, 
         [0048]    assigning LUTs to the child nodes until the node dependency is less than one plus the number of LUTs, and 
         [0049]    assigning an LUT to each output of the nodes in the DAG representation. 
         [0050]    In some embodiments, said sorting is topologically sorting the network in the DAG. 
         [0051]    In some embodiments, said dependency is determined by considering the inputs and outputs of each node. 
         [0052]    In some embodiments, said feasible reconvergent paths are selected to be equal to said number of inputs to one LUT. 
         [0053]    In some embodiments, said determining the priority is generating the priority for the child nodes based on the fan-outs of the nodes in said DAG. 
         [0054]    In some embodiments, said assigning an LUT is forming LUT for a node after performing a check on the number of fan-outs for said node and dependency of the node. 
         [0055]    In some embodiments, said forming LUT is assigning LUTs to all unassigned nodes. 
         [0056]    Some embodiments include a computer program product that comprises computer readable program code stored on a computer readable storage medium embodied therein for providing a system for optimal mapping of LUT based FPGA&#39;s, the system comprising: 
         [0057]    a Directed Acyclic Graph (DAG) representation of the network to be mapped, 
         [0058]    a sorter that operates on said DAG to reduce its complexity, 
         [0059]    a Dependency Definer that determines the dependency of each node in the DAG, 
         [0060]    a Reconvergent Path Locator (RPL) that determines feasible reconvergent paths from transitive fan-ins of each said node, 
         [0061]    a Priority Determiner (PD) that determines the priority of all the child nodes of each said node, 
         [0062]    a Node Sorter (NS) that sorts the list of child nodes in descending order of priority, 
         [0063]    a Mapper (M) that assigns LUT&#39;s to the child nodes from the beginning of said sorted list until the node dependency is less than one plus the number of LUTs, 
         [0064]    an Assignor (A) that assigns an LUT to each output of a particular node. 
         [0065]    In some embodiments, the sorter is a topological sorter. 
         [0066]    In some embodiments, the Node Sorter is a Child node sorter. 
         [0067]    In some embodiments, the Mapper is a LUT Mapper. 
         [0068]    In some embodiments, the assignor is a LUT assignor. 
         [0069]    Some embodiments provide optimized mapping for LUT based FPGA&#39;s and reduce the design area, with optimized mapping speed. 
         [0070]      FIG. 1  and  FIG. 2  depicting the FPGA development flow and legacy mapping process respectively have been described in the background section, above. 
         [0071]      FIG. 3  shows a flow diagram of one embodiment that incorporates exploration of the reconvergent paths in conjunction with fan-out replication. Block  3 . 1  initiates the Directed Acyclic Graph (DAG) representation of the data to be mapped and the number of inputs to the LUT is initialized (k). Block  3 . 2  illustrates performing a topological sort on the given DAG. Block  3 . 3  illustrates the Computation of the Dependency variable (dv) for each node (v) in the graph, whereby the dependency is computed keeping in view that the nodes are analyzed for their respective inputs and outputs. Block  3 . 4  searches for feasible reconvergent paths from transitive fan-ins of a particular node under consideration. The reconvergent paths are desirable to be equal to k. The Dependency of the node under consideration is updated until the dependency variable is greater than k in Blocks  3 . 5 ,  3 . 6  and  3 . 7 . Block  3 . 8  shows the computation of the Priority Variable (Fc) for the children of the node under consideration, and performing the same function for all other nodes in the Directed Acyclic Graph. Priority Variable (Fc) is a function of the following: 
         [0072]    Contribution Variable (Zc), where c in the suffix denotes the children of the node. 
         [0073]    Number of fan-outs (Oc) for the children of the node under consideration. 
         [0074]    Fan-out Factor (FF) variable. 
         [0075]    Block  3 . 9  sorts the list of the children of the node under consideration in the descending order of their priority values followed by block  3 . 10  that assigns LUT&#39;s to the children of the node under consideration until the dependency variable is less than k plus one. Block  3 . 11  checks whether the number of fan-outs of node is greater than one and the Dependency variable dv of the node is greater than 2, then form a LUT for the given node under consideration followed by formation of LUT if the number of fan-outs is greater than three as in Block  3 . 12 . Here an LUT is formed, if it has not been formed in the Block  3 . 11 . Block  3 . 13  assigns a LUT to each output of a given node that has been left unassigned. 
         [0076]    It can be observed from the following table that the reduction in the number of LUTs by the proposed method is substantial as compared to any increase in the execution time for the mapping process. 
         [0077]    Results of few benchmark circuits for LUTs formation are tabulated. 
         [0000]    
       
         
               
               
               
               
               
               
             
               
               
               
               
               
               
             
           
               
                   
               
               
                   
                 No. of LUTs by 
                   
                   
                 Execution Time 
                 Execution Time 
               
               
                   
                 Proposed 
                 No. of LUTs by 
                 No. of LUTs 
                 for Proposed 
                 for LevelMap 
               
               
                 Design 
                 Technique 
                 LevelMap 
                 by FlowMap 
                 Tech. (seconds) 
                 (seconds) 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 alu2 
                 265 
                 272 
                 421 
                 0.46 
                 0.4 
               
               
                 alu4 
                 1646 
                 1756 
                 2080 
                 3.5 
                 3.4 
               
               
                 apex2 
                 2117 
                 2274 
                 2511 
                 4.5 
                 4.2 
               
               
                 apex3 
                 818 
                 867 
                 1010 
                 1.2 
                 1.1 
               
               
                 duke2 
                 263 
                 270 
                 327 
                 .42 
                 0.4 
               
               
                 Misex3 
                 2265 
                 2393 
                 2661 
                 6.9 
                 6.7 
               
               
                 Rd73 
                 170 
                 184 
                 263 
                 0.4 
                 0.3 
               
               
                 Rd84 
                 391 
                 402 
                 481 
                 1.6 
                 1.5 
               
               
                 clma_mod 
                 7452 
                 9344 
                 9248 
                 47.5 
                 46.35 
               
               
                 fft16_mod 
                 15947 
                 19334 
                 18215 
                 78.1 
                 77 
               
               
                 Cordic 
                 800 
                 1117 
                 907 
                 2.1 
                 1.9 
               
               
                 Dalu 
                 603 
                 875 
                 824 
                 3 
                 2.9 
               
               
                 Total 
                 32737 
                 39088 
                 38948 
                 149.68 
                 146.15 
               
               
                   
               
             
          
         
       
     
         [0078]    Reductions in LUTs count (w.r.t. LevelMap) is 16.25%. 
         [0079]    Increase in Execution time is 2%. 
         [0080]    By exploring the reconvergent paths in conjunction with fan-out replication, the certain embodiments map a design with a substantially reduced number of LUTs with minimal increment in execution time.