Packing is a critical step in the CAD flow for cluster-based FPGA architectures, and has a significant impact on the quality of the final placement and routing results. One basic quality metric is routability. Traditionally, minimizing cut (the number of external signals) has been used as the main criterion in packing for routability optimization. This paper shows that minimizing cut is a sub-optimal criterion, and argues to use the Rent characteristic as the new criterion for FPGA packing. We further propose using a recursive bipartitioning-based k-way partitioner to optimize the Rent characteristic during packing. We developed a new packer, PPack2, based on this approach. Compared to T-VPack, PPack2 achieves 35.4%, 35.6%, and 11.2% reduction in wire length, minimal channel width, and critical path delay, respectively. These improvements show that PPack2 outperforms all previous leading packing tools (including iRAC, HDPack, and the original PPack) by a wide margin.

This paper describes a non-volatile reprogrammable FPGA fabric, whose configuration data are provided directly by flash memory. The fabric is optimized for low-cost, low-power applications, leveraging the density of flash and the elimination of conventional configuration SRAM and its attendant static power. After surveying the necessary background on flash and its application to FPGAs, the 1T flash cell is described along with relevant novel aspects of the fabric architecture. The addition of a third level of switching between inter-cluster signals and logic inputs helps to reduce area and raise typical utilization above 95%. Despite the longer signal path, performance is maintained by synergism between the improved routing flexibility and extreme minimization of the fastest LUT input delay. Test cost is reduced by built-in circuits that can test all switches without reprogramming the flash memory. The fabric has been implemented in a 65nm CMOS embedded flash process.

Technology mapping is an important step in the FPGA CAD flow in which a network of simple gates is converted into a network of logic blocks. This article considers enhancements to a traditional LUT-based mapping algorithm for an FPGA comprised of logic blocks which implement only a subset of functions of up to k variables; specifically, the logic block is a partial LUT, but it possesses more inputs than a typical LUT. An analysis of the logic block is presented, and techniques for postmapping area recovery and timing-driven buffer insertion are also described. Numerical results are put forth which substantiate the efficacy of the proposed methods using real circuits mapped to a commercial FPGA architecture.

The ability to efficiently match logic functions to structures of K-input look-up tables (K-LUTs) is a central problem in FPGA resynthesis algorithms. This paper addresses the problem of matching logic functions of ~ 9 to 12 inputs to K-LUT structures. Our method is based on the off-line generation of libraries of LUT structures. During resynthesis, matching is accomplished efficiently using NPN encoding and hash table look-ups. Generating an effective library of LUT structures may seem prohibitive due to the overwhelming number of logic functions which must be considered and represented in the library. We show that, by careful consideration of which logic functions and LUT structures to keep, it is possible to generate useful, compact libraries. We present numerical results demonstrating the effectiveness of our ideas when used during area-oriented resynthesis after FPGA technology mapping.

Technology mapping is an important step in the FPGA CAD flow in which a network of simple gates is converted into a network of logic blocks. We consider enhancements to a traditional LUT-based mapping algorithm for an FPGA comprised of logic blocks which implement only a subset of functions of up to k variables--specifically, the logic block is a partial LUT, but it possesses more inputs than typical LUTs. Numerical results are presented to demonstrate the efficacy of our proposed techniques using real circuits mapped to a commercial FPGA architecture.

Due to poor correlations between pre- and post-placement timing analysis, many post-placement optimization strategies have been proposed for the FPGA CAD flow to improve circuit performance. Typically, these methods depend on logic duplication or decomposition methods combine together with incremental placement.