Delay-oriented technology mapping for heterogeneous FPGAs with bounded resources

In order to maximize performance and device utilization, 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 LUTs of different sizes, or an array of physically heterogeneous LUTs. Some heterogeneous FPGAs do not have limitations on the availability of LUTs of specific sizes within chip capacity due to the configuration flexibility of their PLBs, while others, such as Altera FLEX10K devices [1] and Vantis VF1 FPGAs [12], have limited number of LUTs of certain types (such as embedded memory blocks), which Ne call heterogeneous FPGAs with bounded resources. LUTs of different sizes usually have different delays. In this paper, we study the technology mapping problem for delay minimization for heterogeneous FPGAs with bounded resources. We show that it is NP-Hard for general networks, but can be solved optimally in pseudo-polynomial time for trees. We then present two heuristic algorithms, named BinaryHM and CN-HM, for delay minimization of general networks for heterogeneous FPGA designs with bounded resources. We have tested BinaryHM and CN-HM on MCNC benchmarks on Altera FLEX10K device family, which can be taken as the heterogeneous FPGAs with 4-LUTs and a limited number of 11-LUTs. The experimental results show that compared with FlowMap using only 4-LUTs, both BinaryHM and CN-HM can reduce more than 20% of the circuit mapping delays, 27% of the 4-LUT area and 10% of the circuit layout delays by making efficient use of the available heterogeneous LUTs.