Handbook of Algorithms for Physical Design Automation part 57 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. | 542 Handbook of Algorithms for Physical Design Automation After pruning inferior solutions the solution set at v1 is 167 19 207 39 278 59 308 74 VAN GINNEKEN EXTENSIONS Handling Library with Multiple Buffers We extend the standard van Ginneken s algorithm to handle multiple buffers and buffer cost 12 . The buffer library B now contains various types of buffers. Each buffer b in the buffer library has a cost W b which can be measured by area or any other metric depending on the optimization objective. A function f Vn 2B specifies the types of buffers allowed at each internal vertex in T. The cost of a solution y denoted by W y is defined as W y bQ7 Wb. With the above notations our new problem can be formulated as follows. Minimum-cost timing-constrained buffer insertion problem Given a binary routing tree T V E possible buffer positions defined using f and a buffer library B compute a minimal-cost buffer assignment y such that the RAT at driver is smaller than a timing constraint a. In contrast to the single buffer type case W is introduced into the Q C pair to handle buffer cost . each solution is now associated with a Q C W triple. As such during the process of bottom-up computation additional efforts need to be made in updating W if y is generated by inserting a wire into y then W y W y if Y is generated by inserting a buffer b into y then W y W y W b if y is generated by merging Yi with yr then W y W yi W Yr . The definition of inferior solutions needs to be revised as well. For any two solutions y1 and y2 at the same node y1 dominates y2 if C Y1 C Y2 W y1 W y2 and Q y1 Q Y2 . Whenever a solution becomes dominated it is pruned from the solution set. Therefore only solutions that excel in at least one aspect of downstream capacitance buffer cost and RAT can survive. With the above modification van Ginneken s algorithm can easily adapt to the new problem setup. However because the domination is defined on a Q C W triple rather than a Q C pair more .
