Title :
Performance-driven technology mapping for heterogeneous FPGAs
Author :
Cong, Jingsheng Jason ; Xu, Songjie
Author_Institution :
Dept. of Comput. Sci., California Univ., Los Angeles, CA, USA
fDate :
11/1/2000 12:00:00 AM
Abstract :
In order to maximize performance and device utilization, the recent generation of field programmable gate arrays (FPGAs) take advantage of speed and density benefits resulting from heterogeneous FPGAs, which can be classified into heterogeneous FPGAs without bounded resources or heterogeneous FPGAs with bounded resources. In this paper, we study the technology mapping problem for heterogeneous FPGAs with or without bounded resources under the objective of delay optimization. We present the first polynomial-time delay optimal technology mapping algorithm, named HeteroMap, for heterogeneous FPGAs without bounded resources. Taking different delays of heterogeneous lookup tables (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. We then study the technology mapping problem for delay minimization for heterogeneous FPGAs with bounded resources. We show that this problem is NP-hard for general networks, in contrast to the delay minimization mapping problem for heterogeneous FPGAs without bounded resources, but can be solved optimally in pseudopolynomial time for trees. We then present two heuristic algorithms to solve this problem for general networks. We have successfully applied these algorithms on MCNC benchmarks on commercial FPGAs. Encouraging results on delay and area reduction are reported
Keywords :
circuit CAD; circuit optimisation; delays; field programmable gate arrays; integrated circuit design; logic CAD; minimisation; table lookup; HeteroMap; NP-hard problem; VLSI; area reduction; bounded resources; delay minimization; delays; field programmable gate arrays; heterogeneous FPGA; heuristic algorithms; mapping algorithm; minimum mapping delay; polynomial-time delay optimal technology; pseudopolynomial time; technology mapping; trees; Circuits; Delay; Field programmable gate arrays; Logic arrays; Logic devices; Minimization; Polynomials; Programmable logic arrays; Table lookup; Very large scale integration;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on