Layout-conscious logic optimization techniques for power and delay reduction in FPGAs

Advances in CMOS silicon processing has allowed millions of transistors to be fabricated and interconnected on a single die, enabling complex designs to be integrated in a single chip. Device feature sizes have continued to shrink. Current VLSI fabrication processes have feature sizes well below 0.25μm, and have entered the deep sub-micron (DSM) regime. To make the best of the to deal with system level complexity, while accurately predicting the DSM effects at the physical design level.; In conventional design style, higher-level synthesis tools produce a netlist. Various analysis (e.g., timing and power) tools are built into a feedback loop to detect violations between post-synthesis and post-layout analysis results, which are then used to update synthesis specifications. In earlier technologies, the logical gates determined the performance, since interconnection delays were minimal. In the DSM regime, the contribution of the interconnections to the total circuit delay has increased substantially, and now is an important factor in determining circuit performance. The synthesis tools' inability to optimize the design for interconnection, causes a design that seems to work at the logic level to fail to meet timing specifications.; FPGAs have become a popular implementation technology today. The need to provide ease of programmability via programmable interconnections, however, results in larger die size and lower attainable circuit speeds. The effects of longer interconnections is predominant in FPGAs even in non-DSM processes. Moreover, as the process geometries continue to shrink, the problems are bound to increase. In this thesis we present two layout-conscious logic optimization techniques for circuits mapped to FPGAs. The goal of the techniques presented is to improve circuit speed and reduce power dissipation.; The first technique that we present tightly links the logic and physical domains—we combine logic and placement optimization in a single step. The combined algorithm, based on simulated annealing, considers two types of moves: (1) logic optimization steps consisting of removing or replacing redundant wires in a circuit using functional flexibilities derived from SPFDs (Sets of pairs of functions to be distinguished), and (2) the placement optimization steps consisting of swapping a pair of logic blocks in the FPGA. Feedback from placement is shown to be very valuable in making an informed choice during logic optimization steps. The algorithm produces circuits which are faster and dissipate less power than those produced by optimization methods which are not layout-aware.; The second technique performs a post-layout re-configuration of a circuit implemented using LUT-based FPGAs, with the goal of minimizing power. The technique performs in-place reprogramming of a cluster of LUTs (using functional flexibility derived from Boolean relations), such that the output switching activity of the LUTs is reduced. The algorithm reprograms the combinational component of the CLBs after layout, and does not require any re-wiring or re-placement. A further advantage of the post-layout, power-conscious re-configuration procedure is that accurate power estimation can be performed because full information on wiring capacitance is available. Our technique results in circuits that dissipate less power than the original circuits.