Handbook of Algorithms for Physical Design Automation part 16 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. | 132 Handbook of Algorithms for Physical Design Automation New Innovations in Multilevel Partitioning With increasing design sizes it is becoming increasingly difficult to place an entire design flat using one processor. A novel partitioning approach Ma07 is applied to placement such that the computing effort is spread across several processors. The approach consists of a rough initial flat placement a partitioning step followed by detailed placement within the partition blocks where each block is assigned to its own processor. The novelty of this technique lies in the way the blocks are determined. Normally an engineering change in one block will affect all other blocks. However this is not the case if the block boundary is determined by elements such as latches flip-flops or fixed objects. Once these objects are identified block boundaries that minimize the number of nets running between blocks are determined. Finally detailed placement is applied to blocks each block assigned to its own processor. CONCLUSION This chapter has presented a historical survey of partitioning and clustering techniques ranging from move-based methods to multilevel techniques to mathematical formulations including quadratic linear and integer programming approaches. Multilevel methods have proven to be the partitioning technique of choice in the VLSI community owing to the quality of results they produce with very small runtimes. A consequence of which is that partitioning is currently viewed as a solved problem. However as problem sizes continue to increase multilevel partitions may no longer be near optimal. Recent works Ma07 revisit the partitioning problem and offer new solutions for very large-scale netlists. ACKNOWLEDGMENTS I would like to thank my colleagues especially Ulrich Finkler and Chuck Alpert for giving their comments and suggestions and James Ma for helpful discussions regarding new innovations in multilevel partitioning. REFERENCES ACKM00 C. J. Alpert A. E. .
