tailieunhanh - Handbook of algorithms for physical design automation part 55

Handbook of Algorithms for Physical Design Automation part 55 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. | 522 Handbook of Algorithms for Physical Design Automation SERT-C algorithm Input A signal netSwith source s0 eSand critical sink sc e S Output A critical-sink routing tree ToverS 1. T V E so sc so sc 2. While V S do 3. Find sj e S-V and v v e E such that connecting sj to a point x on v v minimizes the Elmore delay to sc in the tree V U sj x E U v x v x x sj v v 4. V V U Sj x 5. E E U v x v x x Sj v v 6. Output resulting Steiner tree T V E FIGURE The SERT-C algorithm directly incorporates the Elmore delay formula into a greedy critical-sink routing tree construction. From Boese K. D. Kahng A. B. and Robins G. Proceedings of the ACM IEEE Design Automation Conference Dallas 1993. NON-HANAN INTERCONNECT SYNTHESIS In older pre-1990s VLSI regimes where interconnect delay was mostly capacitive resistance-related delay components were negligible and the objective of delay optimization therefore coincided with minimizing the total interconnect length. However as discussed above in more modern VLSI technologies interconnect resistance began to dominate circuit performance causing optimized performance-driven interconnect to resemble minimum wirelength topologies less and less. Another modern deviation from classical constructions involves the Hanan grid which is obtained by drawing horizontal and vertical lines through all the pins of a given net 86 Figure . Hanan s theorem states that there always exists a rectilinear minimum Steiner tree embedded in the Hanan grid 86 87 . Boese et al. 12 proved that only points from the Hanan grid need be considered in minimizing the weighted sum of critical-sink delays. On the other hand for the minmax objective of minimizing the maximum sink delay better routing solutions are possible when considering points that lie off the Hanan grid 12 . For example in Figure a non-Hanan point is required to minimize the maximum source-sink delay during tree construction. Such examples illustrate that the timing requirements at