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 PLBs, each configured
to implement circuits with LUTs of different sizes, or an array of physically
heterogeneous LUTs. LUTs with different sizes usually have different delays.
We presents the first polynomial-time optimal technology mapping algorithm,
named HeteroMap, for delay minimization in heterogeneous FPGA designs.
Taking different delays of heterogeneous LUTs into consideration, the HeteroMap
algorithm computes the minimum mapping delay of a circuit based on a series
of minimum height $K$-feasible cut computations at each node in the circuit.
HeteroMap also effectively minimizes the area of the mapping solution by
maximizing the volume of each cut and by the post-mapping packing operations.
We have tested HeteroMap on MCNC benchmarks on Xilinx XC4000 series FPGAs
which can implement 4-LUTs and 5-LUTs, and Lucent ORCA2C series FPGAs which
can implement 5-LUTs and 6-LUTs. The experimental results show that for
XC4000 series FPGAs, HeteroMap can reduce 19% of the mapping delays and
7% of the post-layout delays with only 2% increase on the PLB numbers,
compared with the results of FlowMap. For ORCA2C series FPGAs, HeteroMap
reduces 9% of the mapping delays and 8% of the PLB number over FlowMap.
Furthermore, the optimality of the HeteroMap algorithm enables us to quantitatively
evaluate various heterogeneous architectures without the bias of mapping
heuristics. A set of architecture study results of heterogeneous FPGAs
are presented in this paper.
|