tailieunhanh - Handbook of algorithms for physical design automation part 58

Handbook of Algorithms for Physical Design Automation part 58 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. | 552 Handbook of Algorithms for Physical Design Automation v2 v3 . vk FIGURE If 1 and a2 satisfy the condition in Definition 1 at v1 a2 is redundant. From Shi W. and Li Z. IEEE Trans Computer-Aided Design 24 879 2005. With permission. node being processed. However all candidates at this node must be propagated further upstream toward the source. This means the load seen at this node must be driven by some minimal amount of upstream wire or gate resistance. By anticipating the upstream resistance ahead of time one can prune out more potentially inferior candidates earlier rather than later which reduces the total number of candidates generated. More specifically assume that each candidate must be driven by an upstream resistance of at least Rmin. The pruning based on anticipated upstream resistance is called predictive pruning. Definition 1 Predictive Pruning. Let a1 and a2 be two nonredundant candidates of T v such that C ai C a2 and Q af Q a2 . IfQ a2 - R C a2 Q ai - R C i then a2 is pruned. Predictive pruning preserves optimality. The general situation is shown in Figure . Let a1 and a2 be candidates of T v1 that satisfy the condition in Definition 1. Using a1 instead of a2 will not increase delay from v to sinks in v2 . vk. It is easy to see C v a1 C v a2 . If Q at v is determined by T v1 we have Q v 1 - Q v a2 Q V1 a1 - Q V1 a2 - Rmin C V1 1 - C V1 2 0 Therefore a2 is redundant. Predictive pruning technique prunes more redundant solutions while guarantees optimality. It is one of four key techniques of fast algorithms proposed in Ref. 39 . In Ref. 42 significant speedup is achieved by simply extending predictive pruning technique to buffer cost. Aggressive predictive pruning technique which uses a resistance larger than Rmin to prune candidates is proposed in Ref. 43 to achieve further speedup with a little degradation of solution quality. Convex Pruning The basic data structure of van Ginneken s algorithms is a sorted list of nondominated .