tailieunhanh - Handbook of algorithms for physical design automation part 39

Handbook of Algorithms for Physical Design Automation part 39 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. | 362 Handbook of Algorithms for Physical Design Automation I III I a 6 -4 5 3 1 2 3 4 5 6 I III I b FIGURE Illustration of median calculation for a cell C connected to three nets. In a the original placement of cells is shown. In b the median or optimal range of x y values for cell C is shown. Six x- and y-positions are used for the median computation because three nets are involved. Note that two-pin nets degenerate to a single point. A larger set of position for cell C can be computed and is best done by expanding the median rectangle outward according to the points used in the median computation and corresponds to the concept of e -neighborhoods described by Goto in Ref. 23 . Median improvement was implemented within the force-directed placer FDP. Specifically multiple passes of median improvement are performed as cell overlap is reduced. Because median improvement attempts to reposition each cell within its median rectangle the use of median improvement can reintroduce cell overlap into the placement. To alleviate the cell overlap FDP attempts to carefully monitor the distribution of cell area when placing a cell inside its median rectangle it is positioned such that a minimum of overlap is reintroduced. Further if at any point during the algorithm too much cell overlap is reintroduced the algorithm is terminated. In Ref. 16 it was empirically observed that the use of median improvement is most effective near the beginning of placement when a large amount of cell overlap is prevalent and less effective toward the end of placement. To this end the median rectangle used in FDP is enlarged when it is discovered Force-Directed and Other Continuous Placement Methods 363 a b Median rectangle 6 -4 5 3 2 1 5 6 Median rectangle 6 4 5 3 2 1 Extended rectangle for HPWL and overlap minimization 5 6 FIGURE Rectangles used in FDP based on Goto s idea to improve wirelength. In a the median or optimal range for replacing a cell. In b the extended range for replacing .