Handbook of Algorithms for Physical Design Automation part 48 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. | 452 Handbook of Algorithms for Physical Design Automation interconnect regions as a result of clustering. The third approach is to balance the perimeter-degree of the partitions during the partitioning phase of the multilevel placement. One could use a multiconstraint partitioner to solve this problem of balancing area and perimeter-degree simultaneously. Alternatively one could satisfy both the constraints in a sequential manner by first balancing the perimeter-degree and then balancing the areas of the partitions. The authors present extensive empirical data to validate their claims about fidelity of perimeterdegree as a simple and effective metric to homogenize interconnection complexity. GLOBAL-PLACEMENT CONGESTION IMPROVEMENT There have been several studies on incorporating the congestion metric during global-placement stage of the physical implementation flow. Local wiring has a big impact on final congestion characteristics of a design. Hence historically it has been difficult to robustly address congestion during the globalplacement stage. There have been major advances in addressing congestion during global placement over the past decade. In this section we detail some of these approaches. Incorporating Congestion Estimation during Global Placement The placement algorithms need to have a good and fast estimation of wiring requirements if they intend to target congestion as a metric during the placement process. Other chapters in this book detail several of these wiring density estimation approaches 10 19 27 39 . Works 6 29 have proposed to incorporate congestion estimation techniques within partitioning-driven quadratic placers in interesting ways. The authors of Ref. 29 base their work on quadratic placement engine that solves an unconstrained minimization problem the objective function of which is the squared wirelength of the netlist. Because the quadratic solution in general has many overlapping cells the overlap is resolved by partitioning
