Method and apparatus for performing buffer insertion with accurate gate and interconnect delay computation

[0002] 1. Technical Field

[0003] The present invention relates in general to integrated circuit design methods and in particular to a design method for buffer insertion within integrated circuits. Still more particularly, the present invention relates to a method for optimizing buffer selection using downstream π-models.

[0004] 2. Description of Related Art

[0005] Scaling process technology into the deep submicron regime has made interconnect performance more dominant than transistor and logic performance. With the continued scaling of process technology, resistance per unit length of the interconnect continues to increase, capacitance per unit length remains roughly constant, and transistor or logic delay continues to decrease. This trend has led to the increasing dominance of interconnect delay over logic delay. Process technology options, such as use of copper wires, can only provide temporary relief. The trend of increasing interconnect dominance is expected to continue. Timing optimization techniques, such as wiresizing, buffer insertion, and sizing have gained widespread acceptance in deep submicron design (see Cong et al. J. Cong, L. He, C.-K. Koh, and P. H. Madden, “Performance Optimization of VLSI Interconnect Layout”, Integration: the VLSI Journal,21, 1996, pp. 1-94. In particular, buffer insertion techniques can significantly reduce interconnect delay. To the first order, interconnect delay is proportional to the square of the length of the wire. Inserting buffers effectively divides the wire into smaller segments, which makes the interconnect delay almost linear in terms of its length, though buffer delays must now be considered. Buffers can also be used to fix slew, capacitance, and noise violations while reducing power, resulting in automated buffer insertion becoming increasingly pervasive as the ratio of device to interconnect delay continues to decrease.

[0006] Buffer insertion has been an active area of study in recent years. Closed formed solutions have been proposed by Adler and Friedman, “Repeater Design to Reduce Delay and Power in Resistive Interconnect”, IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing,Vol. CAS II-45, No. 5, pp. 607-616, May 1998; Alpert and Devgan, “Wire Segmenting For Improved Buffer Insertion”, 34th IEEE/ACM Design Automation Conference,1997, pp. 588-593; and Dhar and Franklin, “Optimum Buffer Circuits for Driving Long Uniform Lines”, IEEE Journal of Solid-State Circuits,26(1), 1991, pp. 32-40, all of which consider inserting buffers on a 2-pin net. Chu and Wong, “Closed Form Solution to Simultaneous Buffer Insertion/Sizing and Wire Sizing”, International Symposium on Physical Design,1997, pp. 192-197, proposed a closed form solution to simultaneous wiresizing and buffer insertion. The works of Culetu et al., “A Practical Repeater Insertion Method in High Speed VLSI Circuits”, 35th IEEE/ACM Design Automation Conference,1998, pp. 392-395, Kannan et al., “A Methodology and Algorithms for Post-Placement Delay Optimization”, 31st IEEE/ACM Design Automation Conference,1994, pp. 327-332; and Lin and Marek-Sadowska, “A Fast and Efficient Algorithm for Determining Fanout Trees in Large Net-works”, Proc. of the European Conference on Design Automation,1991, pp. 539-544, teach inserting buffers on a tree by iteratively finding the best location for a single buffer. Approaches which simultaneously construct a routing tree and insert buffers have been proposed by Kang et al., “Delay Bounded Buffered Tree Construction for Timing Driven Floorplanning”, IEEE/ACM Intl. Conf. Computer-Aided Design,1997, pp. 707-712; Lillis et al., “Simultaneous Routing and Buffer Insertion for High Performance Interconnect”, Proc. 6^thGreat Lakes Symposium on Physical Design,1996, pp 7-12; and Okamoto and Cong, “Interconnect Layout Optimization by Simultaneous Steiner Tree Construction and Buffer Insertion”, Fifth ACM/SIGDA Physical Design Workshop,1996, pp. 1-6. Chu and Wong, “A New Approach to Simultaneous Buffer Insertion and Wire Sizing”, IEEE/ ACM International Conference on Computer-Aided Design,1997, pp. 614-621, present an iterative optimization which simultaneously performs wiresizing and buffer insertion on a 2-pin net.

[0007] In 1990, Van Ginneken, “Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay”, Proc. International Symposium on Circuits and Systems,1990, pp. 865-868, proposed a dynamic programming algorithm which finds the optimal solution using the Elmore wire delay model and a linear gate delay model. The algorithm only permits a single, non-inverting buffer type to be considered. Several extensions and variants have been proposed to this fundamental approach, Alpert and Devgan, “Wire Segmenting For Improved Buffer Insertion”, 34th IEEE/ACM Design Automation Conference,1997, pp. 588-593; Alpert, Devgan and Quay, “Buffer Insertion for Noise and Delay Optimization”, 35th IEEE/ACM Design Automation Conference,1998, pp. 362-367; Lillis, “Timing Optimization for Multi-Source Nets: Characterization and Optimal Repeater Insertion”, 34th IEEE/ACM Design Automation Conference,1997, pp. 214-219; Lillis et al., “Optimal Wire Sizing and Buffer Insertion for Low Power and a Generalized Delay Model”, IEEE Journal of Solid-State Circuits,31(3), 1996, pp. 437-447; Lillis et al., “Simultaneous Routing and Buffer Insertion for High Performance Interconnect”, Proc.6^thGreat Lakes Symposium on Physical Design,1996, pp 7-12; and Okamoto and Cong, “Interconnect Layout Optimization by Simultaneous Steiner Tree Construction and Buffer Insertion”, Fifth ACM/SIGDA Physical Design Workshop,1996, pp. 1-6. Lillis et al., “Optimal Wire Sizing and Buffer Insertion for Low Power and a Generalized Delay Model”, IEEE Journal of Solid-State Circuits,31(3), 1996, pp. 437-447, extended Van Ginneken's algorithm to simultaneously perform wiresizing and buffer insertion with a buffer library that contains both inverting and non-inverting buffers. In addition, Lillis et al. show, in “Optimal Wire Sizing and Buffer Insertion for Low Power and a Generalized Delay Model”, how to control the total number of buffers inserted and how to integrate input slew into the gate delay function. Later, Lillis showed in “Timing Optimization for Multi-Source Nets: Characterization and Optimal Repeater Insertion”, how to modify Van Ginneken's algorithm to handle nets with multiple sources. Alpert and Devgan proposed in “Wire Segmenting For Improved Buffer Insertion” a wire segmenting pre-processing algorithm to handle the one-buffer-per-wire limitation of Van Ginneken's algorithm, which results in a smooth trade-off between solution quality and run time. Alpert et al. showed in “Buffer Insertion for Noise and Delay Optimization”, how to simultaneously modify the algorithm to avoid coupling noise while only suffering a slight delay penalty.

[0008] All of the variants to Van Ginneken's algorithm and most other works in buffer insertion (with the exceptions of V. Adler and E. G. Friedman, “Repeater Design to Reduce Delay and Power in Resistive Interconnect”, and S. Dhar and M. A. Franklin, “Optimum Buffer Circuits for Driving Long Uniform Lines”), use both simplified gate and wire delay models. The Elmore delay model can significantly overestimate interconnect delay, as it incorporates only the first moment of the impulse response. Similarly, using lumped capacitance instead of effective capacitance can overestimate delay by ignoring resistive shielding, as described in Qian, Pullela, and Pillage, “Modeling the “Effective Capacitance” for the RC Interconnect of CMOS Gates”, IEEE Trans. Computer-Aided Design,13(12), 1994, pp. 1526-1535. As the driver resistance becomes comparable to the resistance of the interconnect it drives, some of the downstream capacitance becomes shielded from the gate. In effect, the driver is not driving the entire downstream lumped capacitance but rather an effective capacitance that is less than the total lumped capacitance. It has been empirically shown that using an effective capacitance with k-factor equations is within 10% of SPICE simulation.

[0009] FIG. 1 illustrates the magnitude of the errors that can be obtained from simple delay models in a simple RC network. The RC network consists of resistor R1 having a value of 0.1 kΩ between nodes N1 and N2 and resistor R2 with a value of 1.0 kΩ between nodes N2 and N3. Capacitor C1, having a value of 100ff, is displaced between node N2 and ground, while capacitor C2 having a value of 100ff, is displaced between node N3 and ground. Given an input slew of 300 ps at node N1, RICE (a reduced order interconnect analyzer) from Ratzlaff and Pillage, “RICE: Rapid Interconnect Circuit Evaluator using Asymptotic Waveform Evaluation”, predicts a 10 ps delay from N1 to N2 and a 697 ps delay from N1 to N3. The corresponding Elmore delays are 110 ps and 1110 ps, respectively. Hence, the Elmore delay is wrong by more than a factor of ten for the delay from N1 to N2. Liu et al., Disclose in “Design and Implementation of a Global Router Based on a New Layout-Driven Timing Model with Three Poles”, concur that Elmore delay causes over 100% overestimation error when compared to SPICE.

[0010] The total lumped capacitance seen at node N1 is 1100 ff, whereas for a step input, RICE predicts an effective capacitance of 158 ff. Since gate delays are roughly linear with respect to capacitance, using lumped instead of effective capacitance could lead to an error of a factor of seven. Therefore, previous works on buffer insertion utilize a linear delay model.

[0011] Using inaccurate delay models can hurt buffer insertion algorithms in two ways. First, since they only roughly correspond to the true delay, even optimal solutions for these inaccurate models may be inferior when considering the true delay. Second, inaccurate delay modeling can cause a poor evaluation of the trade-off between the total number of buffers and the improvement in delay. For example, one might conclude from inaccurate delay modeling that inserting one buffer reduces the delay by 2 ns, when it actually reduces the delay by only 1.5 ns. If the net's slack is −1.7 ns, then one would conclude from the inaccurate delay models that inserting a single buffer would be sufficient to meet timing constraints. However, the new slack would not be +0.3 ns, but −0.2 ns, i.e., timing constraints are still not satisfied.

[0012] The present invention discloses a new buffer insertion algorithm which improves Van Ginneken's algorithm by using both accurate interconnect and gate delay models. In one embodiment of the present invention, the improvements are general enough to apply to all of the extensions to Van Ginneken's algorithm that have been proposed previously, e.g., noise avoidance, simultaneous tree construction, handling inverting buffers, and wiresizing. For interconnect delay, the present invention computes moments via a bottom-up incremental technique; it performs moment matching to compute two poles and residues; and then it computes delay using Newton-Raphson iterations. For gate delays, the present invention stores the downstream driving point admittances, i.e., π-models, at each node in the tree, then propagates these π-models up the tree in accordance with experimental results on several nets in an industry design which demonstrate that the runtime penalties for using the improved wire and gate delay models are not prohibitive. Furthermore, using the present invention produces buffered nets with significantly better slack along the critical paths than those produced by Van Ginneken's algorithm.

[0013] The novel features believed characteristic of the invention are set forth in the appended claims. The invention itself, however, as well as a preferred mode of use, further objectives and advantages thereof, will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings, wherein:

[0014] FIG. 1 illustrates the magnitude of the errors that can be obtained from simple delay models, consider simple RC network;

[0015] FIG. 2 is block diagram depicting a data processing system in accordance with the present invention;

[0016] FIG. 3 is a block diagram of a data processing system in which the present invention may be implemented is illustrated;

[0017] FIG. 4 depicts the high-level process of the Van Ginneken's buffer insertion algorithm, V(T,B);

[0018] FIG. 5 shows the Find_Candidates procedure;

[0019] FIG. 6A shows an example of a RC network with three sinks;

[0020] FIG. 6B shows the equivalent π-model of the network depicted in FIG. 6A;

[0021] FIG. 6C illustrates the effective capacitance of the π-model;

[0022] FIGS. 7A and 7B illustrate case 1 and case 2, respectively, of the downstream π-model;

[0023] FIG. 8 illustrates a high-level block diagram of the New_π-model procedure;

[0024] FIG. 9 illustrates a high-level block diagram of the transformation from left and right π-models to a single π-model procedure;

[0025] FIG. 10A shows wire e1 connected to a subtree rooted at N2;

[0026] FIG. 10B depicts reducing the entire subtree rooted at N2 using the New_π-model algorithms;

[0027] FIG. 11 illustrates a two-sink network having a resistance;

[0028] FIG. 12 is a high-level block diagram depicting the VGMC_effprocess; and

[0029] FIG. 13 depicts the high-level Find_VGMC_effCands process in accordance with a preferred embodiment of the present invention.

[0030] With reference now to the figures, and in particular with reference to FIG. 2, a block diagram of a data processing system is depicted in accordance with the present invention. Data processing system 200 may be a symmetric multiprocessor (SMP) system including a plurality of processors 202 and 204 connected to system bus 206. Alternatively, a single processor system may be employed. Also connected to system bus 206 is memory controller/cache 208, which provides an interface to local memory 209. I/O bus bridge 210 is connected to system bus 206 and provides an interface to I/O bus 212. Memory controller/cache 208 and I/O bus bridge 210 may be integrated as depicted.

[0031] Peripheral component interconnect (PCI) bus bridge 214 connected to I/O bus 212 provides an interface to PCI local bus 216. Modem 218 and network adapter 220 may be connected to PCI bus 216. Typical PCI bus implementations support four PCI expansion slots or add-in connectors.

[0032] Additional PCI bus bridges 222 and 224 provide interfaces for additional PCI buses 226 and 228, from which additional modems or network adapters may be supported. In this manner, server 200 allows connections to multiple network computers. A memory mapped graphics adapter 230 and hard disk 232 may also be connected to I/O bus 212 as depicted, either directly or indirectly.

[0033] Those of ordinary skill in the art will appreciate that the hardware depicted in FIG. 2 may vary. For example, other peripheral devices, such as optical disk drives and the like, also may be used, in addition to or in place of the hardware depicted. The depicted example is not meant to imply architectural limitations with respect to the present invention.

[0034] The data processing system depicted in FIG. 2 may be, for example, an IBM RISC/System 6000 system, a product of International Business Machines Corporation in Armonk, N.Y., running the Advanced Interactive Executive (AIX) operating system.

[0035] With reference now to FIG. 3, a block diagram of a data processing system in which the present invention may be implemented is illustrated. Data processing system 300 is an example of a client computer. Data processing system 300 employs a peripheral component interconnect (PCI) local bus architecture. Although the depicted example employs a PCI bus, other bus architectures such as Micro Channel and ISA may be used. Processor 302 and main memory 304 are connected to PCI local bus 306 through PCI bridge 308. PCI bridge 308 also may include an integrated memory controller and cache memory for processor 302. Additional connections to PCI local bus 306 may be made through direct component interconnection or through add-in boards. In the depicted example, local area network (LAN) adapter 310, SCSI host bus adapter 312, and expansion bus interface 314 are connected to PCI local bus 306 by direct component connection. In contrast, audio adapter 316, graphics adapter 318, and audio/video adapter (A/V) 319 are connected to PCI local bus 306 by add-in boards inserted into expansion slots. Expansion bus interface 314 provides a connection for a keyboard and mouse adapter 320, modem 322, and additional memory 324. SCSI host bus adapter 312 provides a connection for hard disk drive 326, tape drive 328, and CD-ROM drive 330 in the depicted example. Typical PCI local bus implementations support three or four PCI expansion slots or add-in connectors.

[0036] In the present example, an operating system runs on processor 302 and is used to coordinate and provide control of various components within data processing system 300 in FIG. 3. The operating system may be a commercially available operating system, such as OS/2, which is available from International Business Machines Corporation. “OS/2” is a trademark of International Business Machines Corporation. An object oriented programming system such as Java may run in conjunction with the operating system and provides calls to the operating system from Java™ programs or applications executing on data processing system 300. Instructions for the operating system, the object-oriented operating system, and applications or programs are located on storage devices, such as hard disk drive 326, and may be loaded into main memory 304 for execution by processor 302. Application programs may include processes such as those discussed below with respect to the processes depicted in FIGS. 4, 5, 8, 12 and 13 below.

[0037] Those of ordinary skill in the art will appreciate that the hardware in FIG. 3 may vary depending on the implementation. For example, other peripheral devices, such as optical disk drives and the like, may be used in addition to or in place of the hardware depicted in FIG. 2. The depicted example is not meant to imply architectural limitations with respect to the present invention. For example, the processes of the present invention may be applied to multiprocessor data processing systems.

[0038] In stating a buffer insertion problem in accordance with the present invention, the problem assumes that the routing tree topology has already been determined via either estimation or actual routing. A routing tree T=(V,E) contains a set of n−1 wires E and a set of n nodes V={{so}∪SI∪IN} where so is the unique source node, SI is the set of sink nodes, and IN is the set of internal nodes. A wire eεE is an ordered pair of nodes e=(u,v) for which the signal propagates from u to v. The lumped capacitance and resistance for wire e are denoted by C_eand R_e, respectively. Each node vε=SI∪IN has a unique parent wire (u,v)εE. The tree is assumed to be binary, i.e., each node can have at most two children. A non-binary tree can be converted into an equivalent binary tree by inserting wires with zero resistance and capacitance where appropriate. Let the left and right children of v be denoted by T.left(v) and T.right(v), respectively. Assuming that if v has only one child, then it is T.left(v) . Also given is a buffer library {B=b₁, b₂, . . . , b_m}.

[0039] A solution to the buffer insertion problem is a mapping M: IN→B∪{{overscore (b)}} which either assigns a buffer or no buffer, denoted by {overscore (b)}, to each internal node of T. A buffer placed on an internal node with degree d is interpreted as having one input, one output, and d−1 fanouts. Let |M|=|{vεIN:M(V)εB}| denote the number of buffers inserted by the mapping. Wires may be segmented as in, “Repeater Design to Reduce Delay and Power in Resistive Interconnect”, proposed by Adler and Friedman, or on the fly to create as many internal nodes as necessary to form a reasonable set of potential locations for buffer insertion. The assignment of k buffers to T induces k+1 nets and, hence k+1 subtrees, each with no internally placed buffers. For each v εV, let T(v)=({v}∪SI_T(v)∪IN_T(v), E_T(v)), the subtree rooted at v, be the maximal subtree of T such that v is the source and T(v) contains no internal buffers. Observe that if vεSI, then T(v)=({v},∅)

[0040] Assuming some model for gate and wire delays, the path from node u to v, denoted by p(u,v), is an ordered subset of wires (u,u₁), (u₁,u₂) , . . . , (u_n−1,u_n), (u_n,v) of E. A wire path from node u to v, denoted by wp(u,v), is a path p(u,v) such that there are no buffers assigned to nodes u₁, u₂, . . . , u_n, but u and v are both gates, i.e., either u=so or M(u)εB and also vεSI or M(v)εB. Thus, a path with k buffers assigned to its internal nodes can be decomposed into k+1 distinct wire paths. Let Delay(v) and Delay(wp(u,v)) denote the gate delay through v (in which M(v)εB and wire delay through wp(u,v), respectively). The total delay from the source so to a sink siεSI is given by: $\begin{array}{cc}\begin{array}{c}\mathrm{Delay}\left(p\left(\mathrm{so},\mathrm{si}\right)\right)=\sum _{\mathrm{wp}\left(u,v\right)\in p\left(\mathrm{so},\mathrm{si}\right)}\mathrm{Delay}\left(u\right)+\\ \mathrm{Delay}\left(\mathrm{wp}\left(u,v\right)\right)\end{array}& \mathrm{Equation}\left(1\right)\end{array}$

[0041] The timing constraints for the buffer insertion problem can be obtained by first performing a timing analysis on the design. For a given net, the required arrival RAT(si) time for each sink si is the actual arrival time at si, minus the actual arrival time at so, plus the slack at si. The condition:

[0042] ∀siεSI,Delay(p(so,si))≦RAT(si)  Equation (2)

[0043] must hold for the net to meet its timing requirements. The buffer insertion algorithm of the present invention seeks to satisfy timing constraints while minimizing the total number of inserted buffers.

[0044] Buffer Insertion Problem: Given a tree T=({so}∪SI∪IN,E), a buffer library B, find a solution M:IN→(B∪{{overscore (b)}}) which minimizes |M|, such that Equation (2) holds.

[0045] Note that the gate delay (Delay(v)) and the wire (Delay(wp(u,v))) have not yet been defined so that the problem formulation can be as general as possible. A common alternative formulation is to minimize the delay on the most critical path, i.e., max_siεSI(RAT(si)−Delay(p(so,si))). One problem with this formulation is that many more buffers may be inserted than are necessary, which can be wasteful in terms of area and power. Experience has shown, that the biggest improvement in the critical path delay occurs when inserting the first few buffers. Hence, a constraint driven formulation is more useful in practice.

[0046] A review of Van Ginneken's algorithm is presented since it forms the basis for this new approach in accordance with the present invention. Van Ginneken's algorithm does not have a mechanism to control the number of buffers inserted; however, Lillis et al. in “Optimal Wire Sizing and Buffer Insertion for Low Power and a Generalized Delay Model”, presented an extension that allows the user to control the number of buffers inserted and thus addresses the problem formulation of the present invention.

[0047] The prior art teaches adopting the Elmore delay model as disclosed in “The Transient Response of Damped Linear Network with Particular Regard to Wideband Amplifiers” for interconnect delays. Let C_vdenote the input capacitance of each v. The total lumped capacitance C_T(v)at node v is given by: $\begin{array}{cc}{C}_{\tau \left(v\right)}=\sum _{w\in {\mathrm{SI}}_{T\left(v\right)}}{C}_w+\sum _{e\in E_{T\left(v\right)}}{C}_e& \mathrm{Equation}\left(3\right)\end{array}$

[0048] The Elmore delay for a wire path is given by: $\begin{array}{cc}\mathrm{Delay}\left(\mathrm{wp}\left(u,u\right)\right)=\sum _{\left(e=\left(w,x\right)\right)\in \mathrm{wp}\left(u,v\right)}{R}_e\left(\frac{C_e}{2}+C_{T\left(w\right)}\right)& \mathrm{Equation}\left(4\right)\end{array}$

[0049] For gate delays, a variety of different models can be used, but a linear model is typical. Let R_vbe the intrinsic resistance and K_vthe intrinsic delay of a gate v. Van Ginneken (as well as Alpert and Devgan; Alpert and Devgan; Lillis, Cheng and Lin; and Okamoto and Cong) uses a linear gate delay model:

[0050] Delay(v)=K_v+R_vC_T(v)  Equation (5)

[0051] In an extension, Lillis et al., in “Optimal Wire Sizing and Buffer Insertion for Low Power and a Generalized Delay Model”, also propose adding a term to this expression for accommodating input slew to the buffer.

[0052] Van Ginneken's algorithm (VG) proceeds in bottom-up fashion starting at the sinks and ending at the source. The main idea is to store candidate solutions at each node in the tree and propagate candidates up the tree while also generating new candidates. A candidate α is defined as a 3-tuple (C_T(v),q,M) where C_T(v)is the lumped capacitance seen at v, q is the slack at v, and M is the current solution for the subtree T(v). Slack is the time required for the input signal to reach node v in order to meet the required arrival times at the sinks downstream from v. When a node with two children is encountered, letting M=M₁∪M_rdenote the new solution that results from merging solutions M₁and M_rfor the left and right branches of v, i.e., M(w)=b if either M₁(w)=b or M_r(w)=b and M(w)={overscore (b)} otherwise. The complete description of the algorithm is given in Table 1 and Table 2 and the process of the algorithm is illustrated in FIG. 4 and FIG. 5. Table 1 illustrated the Van Ginneken's buffer insertion algorithm, VG(T,B).

[0053] FIG. 4 depicts the high-level process of the Van Ginneken's buffer insertion algorithm, VG(T,B). VG takes a routing tree, where T=({so}∪SI∪IN,E), and buffer library B (step 202) and returns a complete solution M. The process then calls the Find_Candidates procedure, which returns a list of candidate solutions S without incorporating driver delay (step 204). Next, driver delay is added (step 206) for each α=(C_T(so),q,M)εS do, Set q=q-K_so-R_soC_t(so), where α Best candidate solution for source. The candidate M with best slack is returned in step 208, M such that (C_T(so),q,M) εS has maximum q.

[0054] Table 2 shows the Find_Candidates algorithm and the procedure is depicted in FIG. 5. The Find_Candidates procedure takes node v to be processed as input, recursively computes the lists of possible candidates for all nodes in T(v), and then returns the candidate list for node v. The procedure can be broken into four main parts:

[0055] (1) Steps 302-316 examine the candidates for the children of v and merges them together to form S, the set of candidates for v. First, it is determined if node v is a sink (step 302). If that is so, step 304 handles the base case in which v is a sink. If node v is not a sink, the process moves to step 306, where it is determined if node v is a single child case. If it is so, step 308 handles the single child case. If node v is neither a sink or single child case the process flows to step 310 and assumes the two child case. The step 312 handles the left child and step 314 handles the right child in the two children case. For the two children case, the child candidate lists S₁and S₂are traversed, and candidates α₁and α₂are merged together by summing their downstream capacitances and taking the minimums of their slacks (step 316). Observe that the number of candidates resulting from merging the two lists is only |S₁|+|S_r| as opposed to |S₁|·|S_r|.

[0056] (2) Step 318 determines if node v is a feasible location for a buffer. If it is a feasible location, buffers are inserted for feasible candidates, thereby creating new candidates to add to S (step 320). Since it may be physically impossible to place a buffer at the current node, only nodes which are “feasible” are considered. Each buffer type b in the library is considered for insertion at v, and the candidate in S which produces the largest resulting slack from the insertion of b is added to the set of candidates.

[0057] (3) Step 322 computes the new load and slack (via Elmore delay) for each candidate induced by the parent wire of v.

[0058] (4) Finally, step 324 prunes inferior candidates from S. The candidates are stored in non-decreasing order by lumped capacitance, and inferior solutions are pruned in a linear pass of the current candidate list. Given two candidates α₁=(C₁, q₁,M₁) and α₂=(C₂, q₂, M₂) for node v, α₁is inferior to α₂if and only if C₁>C₂and q₁≦q₂.

[0059] The complexity of the algorithm is O(n²|B|²).

[0060] The linear gate delay model is inaccurate in two ways. First, if there is significant resistive shielding, the lumped capacitance will be much higher than the effective capacitance (Techniques for computing the effective capacitance are elaborate computations which are well known to those of ordinary skill in the art, thus these techniques will not be discussed in detail other than to note that Qian, Pullela, et al. disclose a useful technique in “Modeling the “Effective Capacitance”). In practice, we observe lumped capacitance to typically be 10% to 40% higher. Second, delay as a function of capacitance is complex, and a linear approximation can be highly inaccurate. Instead, it is more useful to pre-characterize each gate over a large range of loads, then perform curve-fitting to an equation with k coefficients. The resulting equations are referred to as k-factor equations. The error due to curve fitting will generally be significantly less than for a linear delay model. To compute the gate delay, we take the following three-step approach as disclosed by Qian, Pullela, et al., “Modeling the “Effective Capacitance”.

[0061] 1. Compute a π-model of the driving point admittance for the RC interconnect.

[0062] 2. Given the π-model and the characteristics of the driver, compute an effective capacitance C_eff.

[0063] 3. Use C_effinstead of C_T(v)when computing Delay (v) .

[0064] Also use curve-fitted k-factor equations instead of a linear model.

[0065] FIG. 6A shows an example RC network with three sinks, consisting of resistors R1-R4, and capacitors C1, C2 and C3 driven by inverter I1. The network can be transformed into an equivalent π-model shown in FIG. 6B, for the driving point admittance. A π-model is a 3-tuple (C_n, R_π, C_f) where C_nis the capacitance near the driver, R_π is the resistance, and C_fis the capacitance on the far side of the resistor. The effective capacitance of the π-model can then be computed as shown in FIG. 6C, again using the technique disclosed by Qian et al., “Modeling the “Effective Capacitance”.

[0066] In the present enhancement of Van Ginneken's algorithm, instead storing the downstream lumped capacitance for each candidate solution, the present invention stores the π-model for the downstream RC-interconnect. If the downstream network consists of a given sink si, then the corresponding π-model is simply (C_sl,O,O) . To propagate π-models up the tree, the present invention must handle two cases shown in FIGS. 7A-7D.

[0067] Case 1, depicted by FIGS. 7A and 7B, shows wire e1 with a downstream π-model π^d=(C_n^d,R_π^d,C_f^d) represented by resistor R_π^d, near capacitor C_n^dand far capacitor C_f^d. Wire e1 is modeled as a uniformly distributed RC line. Note that a uniform model implies that the same π-model will be computed regardless of whether or not wires have been segmented into smaller wires. Computing the new π-model π=(C_n, R_π, C_f) resulting from merging π^dwith wire e1 is performed by applying the New_π-model procedure shown in Table 3.

[0068] FIG. 8 illustrates a high-level flow chart of the New_π-model procedure depicted in Table 3. Initially, the first three coefficients (y₁^d, y₂^d, y₃^d) of the Taylor series expansion are computed for the exact driving-point admittance of the downstream π-model (step 602). Next, three new coefficients (y₁,y₂,y₃) are computed, which incorporate the uniformly distributed wire (step 604). Finally, the inverse of step 602 is performed, by transforming the coefficients back into a π-model (step 606) which is returned in step 608. The New_π-model procedure has O(1) time complexity.

[0069] Case 2, depicted as FIGS. 7C and 7D, shows the transformation of left and right π-models π¹=(C_n¹,R_π¹,C_f¹) and π^r=(C_n^r,R_π^r,C_f^r) into a single π-model π=(C_n,R_π,C_f) with equivalent driving point admittance. A second New_π-model procedure for Case 2 is shown in Table 4.

[0070] FIG. 9 illustrates a high-level flow chart of the transformation from left and right π-models to a single π-model procedure, depicted in Table 4. This procedure takes two π-models as input and returns a single equivalent, the π-model, which is accomplished by adding the coefficients of their Taylor series expansion of the exact driving-point admittance. The process begins by computing the coefficients (y₁¹,y₂¹,y₃¹) and (y₁^r,y₂^r,y₃^r) for the left and right π-models (step 702). The coefficients are next added together to get three new coefficients (y₁,y₂,y₃), which correspond to the merged π-model (step 704). The new coefficients are then transformed into the resulting π-model (step 706), which is then returned (step 708). The time complexity of this procedure is also O(1).

[0071] Using the New_π-model procedure is shown in Table 3 for case 1 and Table 4 for case 2, it is possible to propagate π-models up any tree topology by iteratively applying whichever of the New_π-model procedures is appropriate. Observe that for any node ν with corresponding π-model π=(C_n,R_π,C_f), there is always a C_T(v)=C_n+C_f, i.e., the total lumped capacitance is preserved in the π-model but R_π can now be used to illustrate the magnitude of resistive shielding.

[0072] Given a π-model and the characteristics of the gate which it drives, the effective capacitance can be computed by using well know methods such as disclosed by Qian et al. In a preferred embodiment of the preset invention, subroutines within the IBM static timing analyzer (EinsTimer) are used to compute effective capacitance. Given the effective capacitance C_eff, the linear gate delay may now be computed as K_v+R_vC_eff. However, the present invention uses empirically derived k-factor equations (k₁+k₂C_eff)t₁+k₃C_eff³+k₄C_eff+k₅, where t₁is the input slew to the driver. If the first three terms of this the k-factor delay model are omitted, the linear model results. The same set of equations are also used, albeit with different numerical values for coefficients, to compute the slew at the output of the driver.

[0073] A preferred embodiment of the present invention discloses to accurately compute the delay for a wire path wp(u,v) as opposed to using the simple Elmore delay model (Equation (4)). Let k be the number of moments to be used in the computation.

[0074] Van Ginneken's algorithm is bottom-up, which implies that bottom-up moment computations are needed to utilize the Van Ginneken paradigm. FIG. 10A shows wire e1 connected to a subtree rooted at N2. Assume that the moments m_BC⁽¹⁾, m_BC⁽²⁾, . . . , m_BC^(k)(subscript A referring to node N1, B to node have already been computed for the path from N2 to N3. New moments m_AC⁽¹⁾, m_AC⁽²⁾, . . . , m_AC^(k)must be computed so that the delay from N1 to N3 can be computed. To do this efficiently, moment multiplication is performed. The ability to compute moments in this manner follows that the fact that the normalized transfer function H(s) for the path from N1 to N3 is equal to the product of the transfer functions for the paths from N1 to N2 and from N2 to N3.

[0075] Using the New_π-model algorithms shown in Table 3 for Case 1 and Table 4 for Case 2, the entire subtree rooted at N2 can be reduced to the π-model (Ĉ_n,R_π,C_f) as shown in FIG. 10B. Further, wire e1 can also represented as a π-model, (C_e/2,R_e,C_e/2), as depicted in FIG. 10B. Here, node N4 just represents the point on the far side of the resistor connected to node N2 and not an actual physical location. The RC network in FIG. 10B can then be simplified to the RC network shown in FIG. 10C. The two capacitances Ĉ_nand C_e/2 at node N2 are merged to form a single capacitor with value C_n. The moments from node N1 to node N2 can be recursively computed by the equation:

[0076] m_AB⁽ⁱ⁾=−R_e(m_AB⁽ⁱ⁻¹⁾C_n+m_AD⁽ⁱ⁻¹⁾C_f)  Equation (6)

[0077] where the moments from node N1 to node N4 are given by:

[0078] m_AD⁽ⁱ⁾=m_AB⁽¹⁾−m_AD⁽ⁱ⁻¹⁾RπC_f  Equation (7)

[0079] and m_AB⁽⁰⁾=m_AD⁽⁰⁾=1. The moments from node N1 to node N4 are not needed directly (since node N1 is a fictitious node), but they are needed to compute the moments from node N1 to node N2.

[0080] Now the moments from node N1 to node N3 can be computed via moment multiplication as follows: $\begin{array}{cc}{m}_{\mathrm{AC}}^{\left(1\right)}=\sum _{J-0}^1(m_{\mathrm{AB}}^{\left(i\right)}·m_{\mathrm{BC}}^{\left(i-j\right)}& \mathrm{Equation}\left(8\right)\end{array}$

[0081] The first three moments of the impulse response can be used to predict delay in an RC interconnect tree with reasonable accuracy, so an implementation of a preferred embodiment of the present invention uses k=3. Given the first three moments for a path, the following method is used to map them to a two-pole approximation. Let m₁, m₂and m₃be shorthand for the first three moments m_AC⁽¹⁾, m_AC⁽²⁾, and m_AC⁽³⁾, respectively. For a second order Padé approximation, the poles p₁and p₂are obtained by finding the roots to the polynomial D(s)=1+d₁s+D₂s², where: $\begin{array}{cc}{d}_2=\frac{m_1{m}_3-m_2^2}{m_2-m_1^2}\mathrm{and}{d}_1=\frac{m_3-m_1{m}_2}{m_1^2-m_2}& \mathrm{Equation}\left(9\right)\end{array}$

[0082] If both p₁and p₂are negative, then stability is assured; however, if either pole is non-negative, the following is used instead: $\begin{array}{cc}{p}_1=\frac{m_2}{m_3}\mathrm{and}{p}_2=p_1\left|\frac{m_3\left(m_2-m_1\right)}{m_1\left(m_1{m}_3-m_2^2\right)}\right|& \mathrm{Equation}\left(10\right)\end{array}$

[0083] The residues can be computed from the poles via $\begin{array}{cc}{k}_1=\frac{p_1^2\left(1+m_1{p}_2\right)}{p_1-p_2}\mathrm{and}{k}_2=\frac{p_2^2\left(1+m_1{p}_1\right)}{p_1-p_2}& \mathrm{Equation}\left(11\right)\end{array}$

[0084] The path delay can now be computed via a Newton-Raphson iteration, with or without a saturated ramp transition time. Convergence generally occurs within a few iterations.

[0085] One property of the Elmore delay model that makes it attractive for timing optimization is that the delays are additive, i.e., the Elmore delay along a path from node N1 to node N3 through node N2 is equal to the Elmore delay from node N1 to node N2 plus the Elmore delay from node N2 to node N3. Unfortunately, this property does not hold for more accurate delay models, which makes a bottom-up approach to buffer insertion more difficult. For example, consider the two-sink RC network shown in FIG. 11.

[0086] FIG. 11 illustrates a two sink network having a resistor, R1, which is an unknown resistance value located between nodes N1 and N2, 0.5 kΩ resistance R2, located between nodes N2 and N3, and resistance R3 of 1.0 kΩ between nodes N2 And N4, also having two sinks, capacitance C1 of 500 ff at sink N3 and at sink N4, capacatance C2 of 500 ff. The required arrival times at sinks N3 and N4 are 500 and 740 ps, respectively. The Elmore delays from node N2 to sink N3 and from node N2 to sink N4 are 250 and 500 ps, respectively. Hence, under the Elmore delay model, the slack at node N2 is min(500−250, 740−500)=240, and sink N4 is the more critical sink. Observe that the critical path can be deduced without knowing anything about the topology upstream from node N2, i.e., sink N4, is the critical sink regardless of the value of the resistance Ri between nodes N1 and N2.

[0087] If moment matching is used to compute higher-order delays, then one cannot deduce whether node N3 or sink N4 is the critical sink without first knowing the value of R1. Assuming a step response at node N1, if R1=0.25, then RICE reports that the higher-order delays from node N1 to sink N3 and node N1 to sink N4 are 317 and 547 ps, respectively. The slack at node N1 is thus min(500−317, 740−547)=183, and sink N3 is the most critical sink. However, if R1=1.0, then the higher-order delays from node N1 to sink N3 and from node N1 to sink N4 are 801 and 1090 ps, respectively. The slack at node N1 becomes min(500−801, 740−1090)=−350, and sink N4 is now the more critical sink. Thus, different scenarios for the upstream resistance can lead to different critical sinks, a situation which cannot occur under the Elmore delay model. Interestingly, for the case when R1=0.25, the higher-order delay from node N1 to node N2 is 24 ps, which implies that the higher-order delay from node N2 to sink N3 is 317−24=293 ps. However, the Elmore delay from node N2 to sink N3 is 250 ps, which implies that the Elmore delay is not actually an upper bound for a given wire (or series of wires). Rather, it is an upper bound for the delay for an entire wire path.

[0088] At a particular node N2, the moments for the most critical path downstream from node N2 cannot be maintained because the most critical path is not known. Instead, one must store the moments for all the paths to sinks that are downstream from node N3 so that the delay to each sink can be computed and the critical path deduced. In a tree with n nodes and p sinks, the total number of moments that would have to be stored at internal nodes in the tree is O(np) (since no node can have downstream paths to more than p sinks). The runtime penalty for this extra computation is not prohibitive.

[0089] In accordance with a preferred embodiment of the present invention, a new algorithm VGMC_eff(VG plus Moment matching plus effective capacitance) is defined. This new algorithm incorporates accurate gate and interconnect delay computations into Van Ginneken's algorithm. Recall that a candidate α was defined as a 3-tuple (C_T(v),q,M). In the new algorithm, a candidate is now a 4-tuple (π_T(v),q,m,M). Here, π_T(v), replaces C_T(v)as the model for downstream capacitance, and m is the set of the first three moments for every gate in SI_T(v). Recall that SI_T(v)denotes the set of gates directly downstream from v.

[0090] Table 5 and Table 6 show the description of the VGMC_effalgorithm and its corresponding Find_VGMC_effCands procedure. The differences between this algorithm and Van Ginneken's original algorithm (Table 1 and Table 2) are discussed below.

[0091] FIG. 12 is a high-level flow chart depicting the VGMC_effprocess. VGMC_efftakes a routing tree, where T=({so}∪SI∪IN,E), and buffer library B (step 1002)and returns a complete solution M. The process then calls the Find_VGMC_effCands(so) procedure, which returns a list of candidate solutions S without incorporating driver delay (step 1004). Next, effective capacitance C_effis used to compute the driver delay at so using the downstream π-model π_T(v), and moment matching is used for the interconnect delay. Slack q_wis computed to each wε SI_T(v)using moments m and Delay(so) (step 1006),for each best candidate where α=(π_T(v),q,m,M)εS. The candidate M with maximum slack is returned in (step 1008), M such that (C_T(v),{tilde over (q)},m,M)εS has maximum {tilde over (q)}.

[0092] In the main algorithm (Table 5), the differences are that effective capacitance is used to compute the driver delay, and moment matching is used for the interconnect delay. The moments have already been computed by the Find_VGMC_effCands procedure.

[0093] Now referring to Table 6, in steps 1102 and 1120, a π-model is constructed to represent a single capacitance value (corresponding to either a sink or an inserted buffer). For these two cases, C_nis set to be the input capacitance of the gate, and both R_π and C_fare set to zero. In steps 1116 and 1122, the New_π-model procedures discussed above are invoked to compute the π-models resulting from either merging two π-models together or adding a uniform wire. These procedures replace the summing lumped capacitances in Table 2.

[0094] In order to compute interconnect delays, every candidate solution for a node v also stores the first three moments to every gate downstream from v. Each moment is initialized to zero when no interconnect is present (steps 1102 and 1120). To update the set of moments when two branches merge (step 1116), the union of the set of moments for both the left and right subtrees is constructed. When taking into account interconnect delay (step 1122), equations (6), (7), and (8) are used to compute the new set of moments {tilde over (m)}.

[0095] Briefly, the high-level Find_VGMC_effCands process is depicted in FIG. 13 and flows as follows. Steps 1102-1116 examine the candidates for the children of v and merges them together to form S, the set of candidates for v. First, it is determined if node v is a sink (step 1102). If node v is a sink, step 1104 handles the base case in which v is a sink using a π-model which is constructed to represent a single capacitance value. If node v is not a sink, the process moves to step 1106 where it is determined if node v is a single child case. If so, step 1108 handles the single child case. If node v is neither a sink nor a single child case, the process flows to step 1110 and assumes the two children case. Step 1112 handles the left child and step 1114 the right child of the two children case. For the two children case, the child candidate lists S₁and S₂are traversed, the set of moments are updated, and candidates α₁and α₂are merged using the New π-model procedure (step 1116).

[0096] At step 1118 it is determined if node v is a feasible location for a buffer. If node v is a feasible location, buffers b are inserted for feasible candidates' and C_effis calculated from the inserted buffer b and using the π-model downstream from v, π_T(v). The delay Delay(b) from the buffer insertion, is calculated using C_effand k equations (k₁+k₂C_eff)t₁+k₃C_eff³+k₄C_eff+k₅. If node v is a feasible location, buffers are inserted for feasible candidates using a π-model which is constructed to represent a single capacitance value, thereby creating new candidates to add to S (step 1120). Next, compute new slack and moments while taking into account interconnect delay, using Equations (6), (7), and (8) for computing the new set of moments m (step 1122). Finally, prune inferior candidates from S (step 1124).

[0097] Slack is now updated differently when a buffer is added to the current candidate. In step 1120, instead of subtracting the linear gate delay from the current slack, the slack to all sinks downstream from v is recomputed. First, the effective capacitance for the gate is computed from the π-model. Then the delay and the output slew of the buffer are computed via k-factor equations. We use an input slew of 400 ps to the buffer. The output slew of the buffer is as the input transition time to the Newton-Raphson iteration for computing the interconnect delay (and slack) to all sinks. Finally, the minimum slack {overscore (q)} over all sinks downstream is computed. Updating slack due to interconnect is similar (step 1122).

[0098] The use of a fixed, 400 ps input slew when computing the buffer delay was made arbitrarily. In general, when inserting a buffer, the topology of the tree upstream from the buffer is still unknown. Hence, it is impossible to know what the input slew will be for the buffer, therefore, for simplicity a fixed slew so for simplicity. Tight user slew constraints on the buffers would help in that the slew constraint would give a suitable upper bound for the real slew that eventually would be seen at the buffer's input pin.

[0099] One step that did not change in VGMC_effis the solution pruning scheme, step 1124. In both VGMC_effand VG, pruning is based on total lumped capacitance and slack. In the Find_VGMC_effCands, C_n+C_fis used as the capacitance for this pruning step. This pruning scheme will cause non-inferior solutions to be pruned. For example, if candidate α₁has π-model π₁,=(100,0,0,), α₂has π-model π₂=(0,100,101), and both α₁and α₂have the same slack, then α₂will get pruned in favor of α₁because the total capacitance for π₁(100) is less than r₂(101). However, for most drivers, the effective capacitance of π₂will be much less than π₁, because all of the capacitance for π₂is strongly shielded, while none of the capacitance for π₁is shielded. For this case, α₁is the inferior solution, yet α₂gets pruned.

[0100] The algorithm could probably be improved by utilizing a more sophisticated pruning scheme to prevent this type of behavior. For example, one could try calculating an effective capacitance for each π-model and prune based on that, as opposed to total lumped capacitance. However, effective capacitance is typically computed in the presence of a driver, and repeated expense of this calculation might prove prohibitive. Another alternative might be to prune on the three values (C_n,R_π,C_f) in each π-model, as opposed to just one (lumped capacitance). This may lead to too few solutions being pruned, and it is not clear that an efficient pruning scheme can be found.

[0101] For an experimental testbed, a small subset of nets was chosen from an IBM ASIC part with over one million transistors, which was designed in a quarter-micron technology. The nets with high total capacitance were selected, since these are likely to be good candidates for buffer insertion. Nets were divided into three groups.

[0102] Small: 20 nets with between 2 and 6 sinks were randomly chosen from the set of high capacitance nets.

[0103] Medium: 25 nets with between 7 and 15 sinks were randomly chosen from the set of high capacitance nets.

[0104] Large: 10 nets with between 18 and 186 sinks that were noted by designers as particularly troublesome for manual buffer insertion.

[0105] The aim is to measure the impact of (1) improved gate delay computation; and (2) improved interconnect delay computation. Described below are the results of using four different algorithms on each group of nets using a buffer library consisting of 3 inverting and 13 non-inverting buffers:

[0106] VG is Van Ginneken's original algorithm (Elmore delays and simple gate delay modeling);

[0107] VGM is VG with moment matching interconnect delay computation;

[0108] VGC_effis VG with effective capacitance computations for gate delays; and

[0109] VGMC_effis VG with both moment matching and effective capacitance delay modeling.

[0110] Each algorithm has the capability to trade off solution quality with the total number of buffers. As additional buffers are inserted, the marginal improvement is reduced until the critical number of buffers is reached, at which point adding additional buffers actually leads to worse solutions. For each net and for up to the critical number of buffers, the improvement in critical path delay versus the zero-buffer solution was recorded.

[0111] Tables 7, 8 and 9 present the average delay improvement as a function of the number of buffers inserted for each of the four algorithms. The total runtimes are reported for an IBM RS6000/S595 with 1 Gb of RAM in the last line of each table.

[0112] Using moment matching (VGM) for the interconnect delay computations yields improvement over VG ranging from 22 to 53 ps for small nets, −2 to 44 ps for medium nets, and −18 to 43 ps for large nets. VGM generally has the most utility for 1 or 2 buffers, with performance declining as the total number of buffers increases. As the number of buffers increases, the interconnect is divided into smaller nets, which reduces the chances of the Elmore delay model being highly inaccurate. The fact VGM sometimes obtains worse results (e.g., the 3 buffer solutions for the large nets group) may be explained by the use of a fixed input transition time of 400 ps for delay computation (when the driver is unknown). A more sophisticated scheme for choosing input slew may be able to improve VGM's performance further.

[0113] Using effective capacitance (VGC_eff) and k-factor equations for the gate delay computations yields improvements over VG of up to 275, 312 and 510 ps for small, medium and large nets, respectively. VGC_effclearly performs better as the number of buffers increases; however, it actually performs worse than VG when 1 buffer is inserted on the set of small and large nets. This may be attributed to two factors. First, a default slew of 400 ps may be too low as an input to the buffer since the load seen at the driver will still be high. Second, the buffer itself will generally be driving a large load, and the k-factor equations may not accurately characterize the buffer for very high capacitances.

[0114] Using both moment matching and effective capacitance (VGMC_eff) outperforms VG for each set of buffers in each group. Improvements range from 43 to 310 ps for small nets, 26 to 464 ps for medium nets, and 16 to 541 ps for large nets. Further, VGMC_effyields the best result of all four algorithms in every case, except for the one buffer solution in each of the three groups. In these cases, VGM yields larger improvements in delay, which is likely caused by the shortcomings described above of using effective capacitance with one buffer.

[0115] The runtime penalties for using improved delay modeling are not prohibitive. For the small and medium nets, VGMC_effuses 9 and 24 percent more CPU time than VG, respectively. For the large nets, VGMC_efftakes 3.4 times longer than VG. The increase appears to be fairly evenly distributed between the improved interconnect and gate delay computations.

[0116] It is important to note that while the present invention has been described in the context of a fully functioning data processing system, those of ordinary skill in the art will appreciate that the processes of the present invention are capable of being distributed in the form of a computer readable medium of instructions and a variety of forms and that the present invention applies equally regardless of the particular type of signal bearing media actually used to carry out the distribution. Examples of computer readable media include recordable-type media such a floppy disc, a hard disk drive, a RAM, and CD-ROMs and transmission-type media such as digital and analog communications links.

[0117] The description of the present invention has been presented for purposes of illustration and description, but is not intended to be exhaustive or limited to the invention in the form disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art. The embodiment was chosen and described in order to best explain the principles of the invention, the practical application, and to enable others of ordinary skill in the art to understand the invention for various embodiments with various modifications as are suited to the particular use contemplated.