Reduction of Power Consumption in FPGAs - An Overview <s> c) Placement <s> There is a deep and useful connection between statistical mechanics (the behavior of systems with many degrees of freedom in thermal equilibrium at a finite temperature) and multivariate or combinatorial optimization (finding the minimum of a given function depending on many parameters). A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems. This connection to statistical mechanics exposes new information and provides an unfamiliar perspective on traditional optimization problems and methods. <s> BIB001 </s> Reduction of Power Consumption in FPGAs - An Overview <s> c) Placement <s> This paper describes a method of automatic placement for standard cells (polycells) that yields areas within 10-20 percent of careful hand placements. The method is based on graph partitioning to identify groups of modules that ought to be close to each other, and a technique for properly accounting for external connections at each level of partitioning. The placement procedure is in production use as part of an automated design system; it has been used in the design of more than 40 chips, in CMOS, NMOS, and bipolar technologies. <s> BIB002 </s> Reduction of Power Consumption in FPGAs - An Overview <s> c) Placement <s> Timing Verification consists of validating the path delays (primary input or storage element to primary output or storage element) to be sure they are not too long or too short and checking the clock pulses to be sure they are not too wide or too narrow. The programs addressing these problems neither produce input patterns like test pattern generators nor require input patterns like traditional simulators. Several programs (described here) operate by tracing paths [P173, WO78, SA81, KA81]. One program [MC80] extends simulation into a pessimistic analyzer not dependent on test patterns. Timing Analysis, a program described recently in [H182a], is designed to analyze the timing of large digital computers and is based, in part, on the concepts disclosed in a patented method [DO81] for determining the extreme characteristics of logic block diagrams. The output of Timing Analysis includes “slack” at each block to provide a measure of the severity of the timing problem. The program also generates standard deviations for the times so that a statistical timing design can be produced rather than a worst case approach. <s> BIB003 </s> Reduction of Power Consumption in FPGAs - An Overview <s> c) Placement <s> An efficient algorithm, RITUAL (residual iterative technique for updating all Lagrange multipliers), for obtaining a placement of cell-based ICs subject to performance constraints is described. Using sophisticated mathematical techniques, one is able to solve large problems quickly and effectively. The algorithm is very simple and elegant, making it easy to implement. In addition, it yields very good results, as is shown on a set of real examples. The algorithm was tested on the ISCAS set of logic benchmark examples using parameters for 1 mu m CMOS technology. On average , there is a 25% improvement in the wire delay for these examples compared to TimberWolf-5.6 with a small impact on the chip area. > <s> BIB004 </s> Reduction of Power Consumption in FPGAs - An Overview <s> c) Placement <s> From the Publisher: ::: Architecture and CAD for Deep-Submicron FPGAs addresses several key issues in the design of high-performance FPGA architectures and CAD tools, with particular emphasis on issues that are important for FPGAs implemented in deep-submicron processes. Three factors combine to determine the performance of an FPGA: the quality of the CAD tools used to map circuits into the FPGA, the quality of the FPGA architecture, and the electrical (i.e. transistor-level) design of the FPGA. Architecture and CAD for Deep-Submicron FPGAs examines all three of these issues in concert. <s> BIB005 </s> Reduction of Power Consumption in FPGAs - An Overview <s> c) Placement <s> In this paper we introduce a new Simulated Annealing-based timing-driven placement algorithm for FPGAs. This paper has three main contributions. First, our algorithm employs a novel method of determining source-sink connection delays during placement. Second, we introduce a new cost function that trades off between wire-use and critical path delay, resulting in significant reductions in critical path delay without significant increases in wire-use. Finally, we combine connection-based and path-based timing-analysis to obtain an algorithm that has the low time-complexity of connection-based timing-driven placement, while obtaining the quality of path-based timing-driven placement. A comparison of our new algorithm to a well known non-timing-driven placement algorithm demonstrates that our algorithm is able to increase the post-place-and-route speed (using a full path-based timing-driven router and a realistic routing architecture) of 20 MCNC benchmark circuits by an average of 42%, while only increasing the minimum wiring requirements by an average of 5%. <s> BIB006
In the placement phase, the packed logic blocks are distributed among the physical logic blocks in the FPGA fabric. Placement algorithms try to minimize the delay along the critical path and enhance the resulting circuit routability. Available placement algorithms can be classified into three categories; min-cut [ BIB002  , analytic  BIB004 , and simulated annealing BIB006 BIB005  based algorithms. Most of the commercial placement tools for FPGAs employ simulated annealing-based algorithms because of their flexibility to adapt to a wide variety of optimization goals. Simulated annealing (SA) placement tools depend on the SA algorithm, which is derived from the annealing process used to cool molten metals BIB001 . d) Timing Analysis Timing analysis BIB003 is used to guide placement and routing CAD tools in FPGAs to: (1) determine the speed of the placed and routed circuit and (2) estimate the slack of each source-sink connection during routing to identify the critical paths. Timing analysis is usually performed on a directed graph representing the circuit, where the nodes represent LUTs or registers and the edges represent connections.