Handbook of Algorithms for Physical Design Automation part 88 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. | 852 Handbook of Algorithms for Physical Design Automation a Illegal wire-to-via connections b Legal wire-to-via connections Violates minimum edge length rules c Illegal transition from wide diagonal wire to thin diagonal wire d Legal transition from wide diagonal wire to thin diagonal wire FIGURE a Illegal and b legal access of wires to vias c illegal and d legal pattern for a transition between a wide diagonal and a narrow diagonal wire. are typically cleaned up after routing by a postprocessing search-and-repair pass that performs small local routing modifications. By contrast X typically includes constraints that are sufficiently complex that they must be addressed in core layout steps such as path search. Manufacturers typically require diagonal geometry edges to have a significant minimum length which leads to a menagerie of illegal patterns that must be avoided during the layout process Figure . Vias can be accessed only at specific angles transitions between wires of different widths must follow certain patterns and jogging structures must obey length constraints depending on the shapes that are adjacent to both sides of the jog. Figures and illustrate legal and illegal geometries. Minimum area requirements present additional challenges. Even a track-based approach such as the one described here permits via positions at arbitrary small separations because of the misalignment a Length requirement for middle segment FIGURE a Diagonal U-turn structure requiring a minimum length for the middle segment and b via-jog-bend structure requiring a minimum length for the jog. b Length requirement for segment from via to diagonal wire X Architecture Place and Route Physical Design for the X Interconnect Architecture 853 If these vias are too close the metal segment between them can violate minimum area rules FIGURE Via positions between can be too close together thus triggering a minimum area violation. of Manhattan and diagonal tracks. .
