Modern analytic placement tools are commonly built around the idea of iterative Lower Bound (LB) and Upper Bound (UB) placement. The LB step optimizes wirelength and timing while ignoring overlap and cell-type constraints, whereas the UB step attempts to spread cells and satisfy constraints without harming design quality. Top-down geometric partitioning techniques have traditionally been used to spread cells during UB placement. We propose a new, network flow-based approach for UB placement which does a better job of preserving quality by optimizing the displacement of cells from their LB positions. Our approach not only addresses cell overlap, but also accommodates complex region constraints and simultaneously spreads unit-sized logic, carry chains, and blocks like RAMs and DSPs. Our technique is scalable, does not require geometric partitioning, and is suitable for both flat and clustered placement flows.We deployed our algorithm in a commercial FPGA CAD flow, and show that it reduces HPWL by 6.4% on average (up to 22.8% in the best case) while improving worst-slack timing in over 90% of designs, compared to a state-of-the-art alternative.

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.

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.

This paper considers the implementation of an annealing technique for dynamic power reduction in FPGAs. The proposed method comprises a power-aware objective function for placement and is implemented in a commercial tool. In particular, a capacitance model based on multi-dimensional nonlinear regression is described, as well as a new capacitance model for global nets. The importance and advantages of these models are highlighted in terms of the overall attainable reduction in power in a real, commercially-available architecture and tool flow. The results are quantified across a range of industrial benchmarks targeting the ActelregIGLOOtradeFPGA architecture. Power measurements show that, across a suite of 120 industrial designs, the technique described in this paper reduces dynamic power by 13% on average, with only a 1% degradation in timing performance.

A new reprogrammable FPGA architecture is described which is specifically designed to be of very low cost.It covers a range of 35K to a million usable gates.In addition, it delivers high performance and it is synthesis efficient.This architecture is loosely based on an earlier reprogrammable Actel architecture named ES.By changing the structure of the interconnect and by making other improvements, we achieved an average cost reduction by a factor of three per usable gate.The first member of the family based on this architecture is fabricated on a 2.54 standard 0.25~ CMOS technology with a gate count of up to 130K which also includes 36K bits of two port RAM.The gate count of this part is verified in a fully automatic design flow starting from a high level description followed by synthesis, technology mapping, place and route, and timing extraction.