Handbook of Algorithms for Physical Design Automation part 81 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. | 782 Handbook of Algorithms for Physical Design Automation Critical Area Integration Let us assume that the appropriate Voronoi subdivision of a layer for a fault type is available. Each Voronoi region can be partitioned into simple subregions such as rectangles and triangles assuming the L1 or octagon metric where the critical area integral can be computed analytically given the defect size distribution D r . Once analytic formulas are established for each type of simple region the total critical area integral can be derived as a simple summation of those formulas. As formulas are analytic there is no integration error. In Refs. 45 48 analytic formulas were derived for the widely used defect size distribution D r 1 r3 assuming the L -_ metric and were shown to simplify into terms derived directly from Voronoi edges. As a result critical area extraction becomes trivial once the appropriate Voronoi diagram is computed. In case A r the critical area for a given specific defect size r is also needed it can be easily derived in linear time from the same Voronoi subdivision of the layout. Scanline Construction of the Voronoi Diagram The Voronoi diagram of a layout can be constructed by a scanline approach as described in Refs. 45 48 for the L -_ metric. The main advantage of the scanline construction is the low memory requirement for critical area computation. For critical area extraction there is never any need to keep the Voronoi diagram of the entire layout in memory. Instead only a portion of the Voronoi diagram near the scanline is maintained. As soon as the Voronoi cell of a polygon or a net is computed second-order computation and critical area computation within that cell can be performed and the Voronoi cell can be immediately discarded. As a result the layout can remain in a compact hierarchical form while the scanline incrementally flattens keeping only a small neighborhood of the design flat at a time near the scanline. The time
