Placement (EDA)

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

Placement within the EDA design flow

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.

Basic techniques

Currently, placement is usually separated into global and detailed placement.

State of the art global placement algorithms include analytic techniques, which approximate the wirelength objective using quadratic[1] or nonlinear[2] formulations, and min-cut placers which use graph partitioning algorithms.[3]

A modern placement framework called SimPL combines analytic techniques with fast computational geometry [4]

Detailed placement uses various kinds of local optimizations, including simulated annealing. Simulated annealing has also been used for the complete placement flow[5] since its proposal as a general combinatorial optimization technique[6] before being replaced by analytical and min-cut placers.

See also

Further reading/External links

The following academic journals provide further information on EDA

Following article explains the use of meta-heuristics for optimizing multiple objectives (power, delay, area, and wire-length) in cell placement.

References

  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. doi:10.1109/43.67789.
  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. doi:10.1109/TCAD.2005.846366.
  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. pp. 477–482.
  4. Kim, M.-C.; Lee D.-J.; Markov I.L.; (January 2011). "SimPL: An Effective Placement Algorithm". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 31 (1): 50–60. doi:10.1109/TCAD.2011.2170567.
  5. Sechen, C. and Sangiovanni-Vincentelli, A. (1985). "The TimberWolf placement and routing package]". Solid-State Circuits, IEEE Journal of 20 (2): 510–522. doi:10.1109/JSSC.1985.1052337. Archived May 21, 2008 at the Wayback Machine
  6. Kirkpatrick, S. and Gelatt Jr, CD and Vecchi, MP (1983). "Optimization by Simulated Annealing". Science 220 (4598): 671–80. doi:10.1126/science.220.4598.671. PMID 17813860.
This article is issued from Wikipedia - version of the Monday, February 15, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.