Synthesis for high-density and high-performance fpgas
Songjie Xu, Jason Cong · 2000
With the rapid development of the programmable logic architectures and with the system performance increasingly dominated by the interconnect delay, the early work on logic synthesis for field programmable gate arrays (FPGAs) targeted at a simple array of homogeneous LUTs can no longer effectively support the rapidly evolving high-density and high-performance FPGAs. Contributions of this dissertation include the following four related aspects for FPGA synthesis: (i) technology mapping for FPGAs with embedded memory blocks (EMBs), (ii) technology mapping for heterogeneous FPGAs, (iii) timing-driven logic resynthesis, and (iv) layout-driven logic synthesis. For technology mapping for FPGAs with EMBs, we explore the possibility of using EMBs to implement logic functions when they are not used as on-chip memory. For technology mapping for heterogeneous FPGAs, we formulate and solve the following two problems: (1) The mapping problem for heterogeneous FPGAs without bounded resources. We present the first polynomial-time delay optimal mapping algorithm that takes different delays of heterogeneous LUTs into consideration. (2) The mapping problem 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 pseudo-polynomial time for trees. For timing-driven logic resynthesis, we propose a general methodology for iterative refinement based approaches for delay minimization. For layout-driven logic synthesis, we formulate and study the following three synthesis problems that take certain degree of layout information into consideration: (1) The mapping problem for FPGAs with nonuniform pin delays. We propose an algorithm to simultaneously perform the delay optimal LUT pin assignment and the delay optimal mapping for FPGAs with K -LUT of nonuniform pin delays in polynomial time. (2) The mapping problem for FPGAs with fast interconnections. We first show that this problem can be solved optimally in polynomial time for trees. (3) The layout-driven timing optimization problem. Targeting FPGAs with hierarchical interconnection structures, we propose a layout-driven synthesis flow to consider the effect of technology mapping and performance-driven clustering during timing-driven logic optimization. (Abstract shortened by UMI.)