Handbook of Algorithms for Physical Design Automation part 43 provides a detailed overview of VLSI physical design automation, emphasizing state-of-the-art techniques, trends and improvements that have emerged during the previous decade. After a brief introduction to the modern physical design problem, basic algorithmic techniques, and partitioning, the book discusses significant advances in floorplanning representations and describes recent formulations of the floorplanning problem. The text also addresses issues of placement, net layout and optimization, routing multiple signal nets, manufacturability, physical synthesis, special nets, and designing for specialized technologies. It includes a personal perspective from Ralph Otten as he looks back on. | 402 Handbook of Algorithms for Physical Design Automation For designs that are dense legalization is difficult and more robust methods are necessary if one is to obtain good results. For legalization of designs that contain both macroblocks and standard cells there are two distinct approaches. One method first first fixes the positions of macroblocks and then fills the space between them with standard cells. A second approach is to legalize macroblocks and standard cells simultaneously. Once a placement is legal with all overlaps removed and logic elements properly aligned optimizations that are traditionally classified as detailed placement can be applied. Small groups of standard cells can be shifted or reordered these local optimizations can have a dramatic impact on wirelength. To maximize the size of an optimization window with acceptable runtimes dynamic programming is frequently used. Notation When presenting specific algorithms we utilize the following notation. For an integrated circuit the netlist will contain a set of cells C c1 c2 c3 . cn connected by a set of signal nets N n1 n2 n3 . nm . Each net connects a subset of the cells. A placement P of a netlist consists of precise x and y positionings for each cell ct. We focus on transformations of P to another similar placement P such that the placement has lower overlap becomes legal has better wirelength and so on. For simplicity in most cases we assume that the nets connect to the centers of the cells and we treat macroblocks and standard cells in the same way. Extending the methods described to use exact pin positions is trivial. Routing Models Over the years the increasing numbers of interconnect layers has driven changes in routing models. This has impacted detail placement in interesting ways. In earlier variable-die designs routing success could almost always be assured given sufficient space . In standard cell designs the spacing between rows can be adjusted as needed. In earlier .
