delay-optimal technology mapping for fpgas with heterogeneous luts
Recent generation of FPGAs take advantage of speed and density benefits resulted from heterogeneous FPGAs, which provide either an array of homogeneous programmable logic blocks (PLBs), each configured to implement circuits with lookup tables (LUTs) of different sizes, or an array of physically heterogeneous LUTs. LUTs with different sizes usually have different delays. This paper presents the first polynomial-time optimal technology mapping algorithm, named HeteroMap, for delay minimization in heterogeneous FPGA designs. For a heterogeneous FPGA consisting of K 1 -LUTs, K 2 -LUTs, , and K c -LUTs, HeteroMap computes the minimum delay mapping solution in O (? c i =1 K i  n  m log n ) time for a circuit netlist with n gates and m edges. The HeteroMap algorithm generates favorable results for Xilinx XC4000 series FPGAs and Lucent ORCA2C series FPGAs. Furthermore, the optimality of the HeteroMap algorithm enables us to quantitatively evaluate various heterogeneous architectures without the bias of mapping heuristics.
delay optimality technology mapping map fpgas heterogeneity generation arrays programmable logic circuits tables paper algorithm minimal design timing evaluation architecture bias heuristics polynomial pla-style logic blocks programmable logic devices