Handbook of Algorithms for Physical Design Automation part 67 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. | 642 Handbook of Algorithms for Physical Design Automation chip may be partially or completely blocked and buffers cannot be placed in these areas. As the capacity constraints for the edges in the global routing graph ensure that not too many wires cross the boundaries between two adjacent global routing tiles similar constraints ensure that not too many buffers are placed in one global routing tile. Vygen 26 considers the coupling capacitance and minimizes the total power consumption while ensuring the timing constraints for individual nets and certain paths. A Steiner tree for a net is characterized not only by the edges of the global routing graph but also each edge of the Steiner tree has a continuous parameter specifying the spacing to each side of the final route. It is assumed that the coupling capacitance decreases linearly with the spacing. The timing constraints are ensured by bounding the weighted capacitance for subsets of the nets a constraint similar to the constraint that bounds the total weighted wirelength. While more space decreases the coupling capacitance also more routing resources are used. The problem can be formulated as a fractional packing problem of infinitely many Steiner trees infinitely many because of the continuous spacing parameters. Because the capacitance depends linearly on the spacing every edge of the Steiner tree that minimizes the cost function with respect to the dual variables either has the maximum or minimum spacing. The task of the subroutine is still to find a Steiner minimal tree in the grid graph with respect to a nonuniform length function. Müller 27 describes a parallel multithreaded implementation of the approximation scheme. He shows that it is possible to update the dual variables at the end of each phase for all nets instead of updating them immediately after a Steiner tree is found. The set of nets is split into subsets and each thread computes the minimal Steiner trees for one subset in the global routing .
