Handbook of Algorithms for Physical Design Automation part 50 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. | 472 Handbook of Algorithms for Physical Design Automation FIGURE a Three-dimensional grid model for a three-layer circuit and b its corresponding grid graph where solid lines represent intralayer connections and dashed lines represent interlayer connections. in G between vertices that correspond to neighboring ties. Here each terminal is assumed to lie at the center of the grid cell that contains the terminal. In this model edge capacities are set based on the number of routing tracks available passing through the tile boundaries as will be discussed with more detail in Section . If a two-dimensional grid model is used as in Figure the routing tracks on every layer are lumped together to compute edge capacities. On the other hand a three-dimensional grid graph can capture the characteristics of different layers more accurately. For example there can be routing blockages on specific layers and different layers can have different wire width and spacing requirements based on the technology being used. Although the three-dimensional grid model can capture the capacity differences in different layers it requires layer assignment to be performed during global routing. Figure illustrates a three-dimensional grid graph where each layer has either horizontal or vertical preferred orientation. Observe here that there are only horizontal edges on a horizontal layer and only vertical edges on a vertical layer. The global routing algorithms using tile-based graph model include Refs. 18-25 . CAPACITY COMPUTATION As discussed earlier a graph model G is used for global routing to capture the adjacencies and the capacities of the routing regions. Let u and v represent two vertices in G corresponding to two adjacent routing regions. The capacity of the edge e e G between u and v is set so as to reflect the available routing resources between the corresponding routing regions. A common capacity metric for edge e is the number of available routing tracks .
