Handbook of Algorithms for Physical Design Automation part 6 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. | 32 Handbook of Algorithms for Physical Design Automation FIGURE Elmore delay approximating the median with the mean. Another important characteristic is the median which is defined as the halfway point on a PDF curve M 1 f h t dt - 2 0 The similarity between the impulse response of an RC tree and a statistical PDF is quite clear. Observe that the commonly used 50 percent delay point in circuit analysis actually corresponds to the median of the underlying distribution. This is the keen observation of Elmore in 1948. Moreover he also made the proposal that as the median was difficult to calculate one could use the mean which is much easier to calculate as an approximation of median M p -mi J th t dt 0 Elmore Delay for RC Trees For an RC tree . an RC network with no direct resistive path to ground the calculation of Elmore delay can be carried out quite efficiently. In such a case the Elmore delay between any two nodes can be expressed as H ERi E Cj downstream where Rt is the traversal of the resistors on the unique path between two nodes Cj permutes all the capacitance seen from resistor Rt Metrics Used in Physical Design 33 C i . . C C 1 j- wv -L 1 i J C2 Zj C6 FIGURE An example of RC tree to illustrate the process of calculating Elmore delay. For the simple example shown in the Elmore delay from root node A and fan-out node Z1 can be calculated by traversing the unique resistive path from Z1 to A El RC R C4 C5 R3 C3 C4 C5 R2 C2 C3 C4 C5 C6 R1 C1 C2 C3 C4 C5 C6 The Elmore delay has a nice property it is additive. In other words for two nodes A and C on a branch if node B lies between A and C we can write El - - EDa .b in. For the example shown in Figure we can easily verify that R3C3 C4 C5 R2C2 C3 C4 C5 O R1 C1 C2 C3 C4 C5 C6 EDy .z1 R5C5 R4 C4 C5 Thus 1 ED. . The Elmore delay of an RC tree has another important property it can be proven to be the upper bound of the true 50 percent circuit delay under .
