tailieunhanh - Handbook of algorithms for physical design automation part 32

Handbook of Algorithms for Physical Design Automation part 32 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. | 292 Handbook of Algorithms for Physical Design Automation were detrimental to performance 40 . The authors of Ref. 43 not only developed a dynamic programming technique to choose optimal cut sequences for partitioning-based placement but also found that nearly optimal cut sequences could be determined from the aspect ratio of the bin to be split. This technique has been independently used in the Capo placer 30-35 . After the cutline direction is chosen partitioning-based placers generally choose the cut-line that best splits a placement bin in half in the desired direction. Usually cutlines are aligned to placement row and site boundaries to ease the assignment of standard-cells to rows near the end of global placement 9 . After a bin is partitioned the initial cutline may be shifted to satisfy objectives such as whitespace allocation or congestion reduction. Whitespace Allocation Management of whitespace also known as free space is a key issue in physical design as it has a profound effect on the quality of a placement. The amount of whitespace in a design is the difference between the total placeable area in a design and the total movable cell area in the design. A natural scheme for managing whitespace in top-down placement uniform whitespace allocation was introduced and analyzed in Ref. 12 . Let a placement bin to be partitioned have site area S cell area C absolute whitespace W max S - C 0 and relative whitespace w W S. A bipartitioning divides the bin into two child bins with site areas S0 and S1 such that S0 S1 S and cell areas C0 and C1 such that C0 C1 C. A partitioner is given cell area targets T0 and T1 as well as a tolerance t for a bipartitioning instance. t defines the maximum percentage by which C0 and C1 are allowed to differ from T0 and T1 respectively. In many cases of bipartitioning T0 T1 2 but this is not always true 5 . The work in Ref. 12 bases its whitespace allocation techniques on whitespace deterioration the phenomenon that .