Article Invited talk: synthesis challenges for next-generation high-performance and high-density PLDs Share on Authors: Jason Cong Department of Computer Science, University of California, Los Angeles, CA Department of Computer Science, University of California, Los Angeles, CAView Profile , Songjie Xu Aplus Design Technologies, Inc., 10850 Wilshre Blvd., Suite 370, Los Angles, CA Aplus Design Technologies, Inc., 10850 Wilshre Blvd., Suite 370, Los Angles, CAView Profile Authors Info & Claims ASP-DAC '00: Proceedings of the 2000 Asia and South Pacific Design Automation ConferenceJanuary 2000 Pages 157–162https://doi.org/10.1145/368434.368596Online:28 January 2000Publication History 3citation108DownloadsMetricsTotal Citations3Total Downloads108Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

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.

In this paper we study the technology mapping problem for FPGAs with nonuniform pin delays and fast interconnections. We develop the PinMap algorithm to compute the delay optimal mapping solution for FPGAs with nonuniform pin delays in polynomial time based on the efficient cut enumeration. Compared with FlowMap [5] without considering the nonuniform pin delays, PinMap is able to reduce the circuit delay by 15% without any area penalty. For mapping with fast interconnections, we present two algorithms, an iterative refinement based algorithm, named ChainMap, and a Boolean matching based algorithm, named HeteroBM, which combines the Boolean matching techniques proposed in [2] and [3] and the heterogeneous technology mapping mechanism presented in [1]. It is shown that both ChainMap and HeteroBM are able to significantly reduce the circuit delay by making efficient use of the FPGA fast interconnections resources. 1 Introduction The LUT-based FPGA can be designed in such a way that the ...

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 K1-LUTs, K2-LUTs, …, and Kc-LUTs, HeteroMap computes the minimum delay mapping solution in O (∑ci=1 Ki·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.

Modern field programmable gate arrays (FPGAs) provide embedded memory blocks (EMBs) to be used as on-chip memories. In this paper, we explore the possibility of using EMBs to implement logic functions when they are not used as on-chip memory. We propose a general technology mapping problem for FPGAs with EMBs for area and delay minimization and develop an efficient algorithm based on the concepts of Maximum Fanout Free Cone (MFFC) [3] and Maximum Fanout Free Subgraph (MFFS) [7], named EMB_Pack, which minimizes the area after or before technology mapping by using EMBs while maintaining the circuit delay. We have tested EMB_Pack on MCNC benchmarks on Altera's FLEX10K device family [1]. The experimental results show that compared with the original mapped circuits generated from CutMap [5] without using EMBs, EMB_Pack as postprocessing can further reduce up to 10% of the area on the mapped circuits while maintaining the layout delay by making efficient use of available EMB resources. Compared with CutMap-e without using EMBs, EMB_Pack as pre-mapping processing followed by CutMap-e can reduce 6% of the area while maintaining the circuit optimal delay.

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 [11], have limited number of LUTs of certain types (such as embedded memory blocks), which we 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.