From Wikipedia, the free encyclopedia

Look up Placement in Wiktionary, the free dictionary.

Placement is an essential step in electronic design automation - the portion of the physical design flow that assigns exact locations for various circuit components within the chip’s core area. An inferior placement assignment will not only affect the chip's performance but might also make it nonmanufacturable by producing excessive wirelength, which is beyond available routing resources. Consequently, a placer must perform the assignment while optimizing a number of objectives to ensure that a circuit meets its performance demands. Typical placement objectives include

• Total wirelength: Minimizing the total wirelength, or the sum of the length of all the wires in the design, is the primary objective of most existing placers. This not only helps minimize chip size, and hence cost, but also minimizes power and delay, which are proportional to the wirelength and wirelength squared, respectively.
• Timing: The clock cycle of a chip is determined by the delay of its longest path, usually referred to as the critical path. Given a performance specification, a placer must ensure that no path exists with delay exceeding the maximum specified delay.
• Congestion: While it is necessary to minimize the total wirelength to meet the total routing resources, it is also necessary to meet the routing resources within various local regions of the chip’s core area. A congested region might lead to excessive routing detours, or make it impossible to complete all routes.
• Power: Power minimization typically involves distributing the locations of cell components so as to reduce the overall power consumption, alleviate hot spots, and smooth temperature gradients.
• A secondary objective is placement runtime minimization.

A placer takes a given synthesized circuit netlist together with a technology library and produces a valid placement layout. The layout is optimized according to the aforementioned objectives and ready for cell resizing and buffering — a step essential for timing and signal integrity satisfaction. Clock-tree synthesis and routing follow, completing the physical design process. In many cases, parts of, or the entire, physical design flow are iterated a number of times until design closure is achieved.

In the case of application-specific integrated circuits, or ASICs, the chip’s core layout area comprises a number of fixed height rows, with either some or no space between them. Each row consists of a number of sites which can be occupied by the circuit components. A free site is a site that is not occupied by any component. Circuit components are either standard cells, macro blocks, or I/O pads. Standard cells have a fixed height equal to a row’s height, but have variable widths. The width of a cell is an integral number of sites. On the other hand, blocks are typically larger than cells and have variable heights that can stretch a multiple number of rows. Some blocks can have preassigned locations — say from a previous floorplanning process — which limit the placer’s task to assigning locations for just the cells. In this case, the blocks are typically referred to by fixed blocks. Alternatively, some or all of the blocks may not have preassigned locations. In this case, they have to be placed with the cells in what is commonly referred to as mixed-mode placement.

In addition to ASICs, placement retains its prime importance in gate array structures such as field-programmable gate arrays (FPGAs). In FPGAs, placement maps the circuit’s subcircuits into programmable FPGA logic blocks in a manner that guarantees the completion of the subsequent stage of routing.

• Analytical techniques approximate the wirelength objective using quadratic^[1] or nonlinear^[2]formulations.
• The advent of min-cut partitioners paved the way to the introduction of min-cut placers^[3].
• Another thread of placement techniques^[4] started with the proposal of simulated annealing as a general combinatorial optimization technique^[5].

• Electronic design automation
• Design flow (EDA)
• Integrated circuit design

This article or section is written like an advertisement. Please help rewrite this article from a neutral point of view. Mark blatant advertising for speedy deletion, using {{db-spam}}.

This section may contain spam. Wikipedia spam consists of external links mainly intended to promote a website. Wikipedia spam also consists of external links to websites which primarily exist to sell goods or services, use objectionable amounts of advertising, or require payment to view the relevant content. If you are familiar with the content of the external links, please help by removing promotional links in accordance with Wikipedia:External links. (You can help!)

One major source of additional detail on this subject (Placement (EDA)) is the technical literature. The journals IEEE Transactions On Computer-Aided Design Of Integrated Circuits And Systems (Web page here) and ACM Transactions on Design Automation focus explicitly on Design Automation. In addition, many other journals carry EDA specific articles, and there are also many EDA-centric conferences.

Most of these articles and proceedings are published by either the IEEE or the ACM. Desired articles can be found through the IEEE on-line library or the ACM digital library, which show abstracts, or [Google scholar], which shows snippets. The articles themselves are sometimes available for free on-line (both the IEEE and ACM allow authors to keep copies on their personal web sites.) If you are not so lucky, you can visit a technical library or download the article from the IEEE or ACM. Although almost all articles are available, on-line access to the full text is not free - it requires purchase, society membership, or a site license. Many schools and companies have site licenses already. As a last resort, a polite email to the author will sometimes yield a copy.

• Electronic Design Automation For Integrated Circuits Handbook, by Lavagno, Martin, and Scheffer, ISBN 0-8493-3096-3 A survey of the field of Electronic Design Automation. The above summary was derived, with permission, from Volume II, Chapter 5, Digital Layout -- Placement by Andrew Kahng and Sherief Reda.

1. ^ Kleinhans, J.M.; Sigl, G.; Johannes, F.M.; Antreich, K.J.; (March 1991). "GORDIAN: VLSI placement by quadratic programming and slicing optimization". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 10 (3): 356 - 365. 
2. ^ Kahng, A.B.; Qinke Wang; (May 2005). "Implementation and extensibility of an analytic placer". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 24 (5): 734 - 747. 
3. ^ Caldwell, A.E.; Kahng, A.B.; Markov, I.L.; (June 2000). "Can recursive bisection alone produce routable placements? ". Proceedings of the 37th Design Automation Conference: 477 - 482. 
4. ^ Sechen, C. and Sangiovanni-Vincentelli, A. (1985). "The TimberWolf placement and routing package,". Solid-State Circuits, IEEE Journal of 20,: 510--522. 
5. ^ Kirkpatrick, S. and Gelatt Jr, CD and Vecchi, MP, (1983). "Optimization by Simulated Annealing". Science, 220,: 671,.