Handbook of Algorithms for Physical Design Automation part 36 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. | 332 Handbook of Algorithms for Physical Design Automation The star and the clique model and any other linear model with fixed topology in the sense of Theorem 2 can be reduced to the bounding box model by adding a cell with a single pin for each auxiliary point and replacing each net equivalently by an appropriate set of two-terminal nets. Of course this may increase the number of nets substantially. The converse is also true optimizing the bounding box netlength as above is equivalent to minimizing netlength in a certain netlist containing two-terminal nets only computable as follows. Introduce fixed pins at the leftmost possible position L and at the rightmost possible position R. Moreover introduce cells lN and rN each with a single pin for each net N and replace the net N by 2 P 2 two-terminal nets one connecting L and lN with weight w N N - 1 another one connecting rN and R with weight w N N - 1 and for each pinp e N a net connecting lN andp and a net connectingp and rN each of weight w N . For any placement of the pins the weighted netlength of the new netlist is Ynn w N dN - 1 R - x rN MIn - L Y p ndx p - x In x rN - x p .Forasolutionminimizingthis expression we have x lN minpeNx p and x rN maxpeNx p and the above expression reduces to XNeN w N N - 1 R - L x rN - x lN . Except for a constant additive term this is the weighted bounding box netlength. For netlists with two-terminal nets only and zero pin offsets an instance is essentially an undirected graph G with edge weights w a subset C c V G of movable vertices and coordinates x v for v e V G C. Minimizing bounding box netlength then means finding coordinates x c for c e C such that Xe v w eE G w e x v - x w is minimized. For this special case Picard and Ratliff 1978 and later also Cheung 1980 proposed an alternative solution which may be faster than the minimum cost flow approach described above. Their algorithms solve V G C - 1 minimum s-t-cut problems in an auxiliary digraph with at most C 2 vertices .
