US 6,314,546 B1Grant

Interconnect capacitive effects estimation

Issue Date:2001-11-06

•20 Claims

•4 Drawing Sheets

Abstract

An non-iterative approach for estimating interconnect capacitive effects. The non-iterative approach includes a method for estimating the interconnect capacitive effects. The method includes modeling the gate and estimating an effective capacitance for the interconnect capacitive effects. The effective capacitance estimation includes modeling the gate load at an output of the gate. The gate load modeling includes approximating an admittance of the gate load to a single capacitance model in addition to approximating the admittance of the gate load to a Π model. The gate load modeling also includes matching a gate response for the Π model with the gate response for the single capacitance model to determine the effective capacitance. Another aspect of the method for estimating the interconnect capacitive effects includes modeling the gate using an equivalent circuit, and modeling the load at an output of the gate. The gate load modeling includes determining Π model parameters that represent the load at the output of the gate. The parameters are associated with a response at the gate output. The effective capacitance estimation method further includes modeling a single capacitive load at the output of the gate. The single capacitive load modeling includes determining a gate delay for a threshold time at a threshold voltage. This delay determination accounts for the input voltage waveform, the voltage response at the gate output and the Π model parameters. The single capacitance modeling the capacitive load is determined using the threshold time. The effective capacitance is then derived taking into account the single capacitance, a total capacitance of the gate load, an intrinsic gate delay and a gate load delay for the total capacitance as a load.

Metadata

Assignee

Silicon Graphics, Inc.

Inventor

Sudhakar Muddu

Application Information

Application Number:US 09/276,992

Filing Date:1999-03-26

Priority Date:1999-03-08

Art Unit:7

Classifications

IPC:

G06F 1750

Field of Search:

716 1716 2716 4716 5716 6

Patent Drawings (4 sheets)

Description

Claim for Benefit of Earlier Filing Date

[0002] A claim is hereby made for the benefit under 35 U.S.C 119(e) of a U.S. provisional application Ser. No. 60/123,262, filed Mar. 8, 1999, which is incorporated herein by reference.

Field of the Invention

[0003] This application relates to integrated circuit design automation and, specifically, to gate interconnect load estimation.

Background of the Invention

[0004] Integrated circuit design includes selection and layout of gates also known as cells. The interconnections between the multiplicity of gates in an integrated circuit form signal paths. In most cases, the interconnections between gates form an interconnect tree (as shown in FIG. 1). The resistive, capacitive and inductive attributes of interconnect lines form gate loads at the respective gate outputs and contribute to signal time delays.

[0005] With interconnect delays dominating overall path delays for deep-submicron integrated circuits, heuristics for logic synthesis and layout optimization need to accurately model interconnect effects. Accurate estimations of gate delay and slew time are required for a number of signal integrity and reliability checks. In synthesis and floorplanning, pre-layout gate delay estimation capability is needed. In post-layout timing analysis, existing accurate gate delay estimates are not efficient enough to be used in the typical incremental synthesis, layout or in-place optimization loop or during performance-driven area routing. In either context, accurate estimations of gate delay and slew time at the gate output, depend closely on an accurate model for the admittance of an interconnect tree load at the gate output. The present invention addresses these and related issues.

Summary of the Invention

[0006] The present invention provides a new non-iterative approach for estimating interconnect capacitive effects. This approach includes determining an effective capacitance that represents the interconnect capacitive effects at an output of a driving gate (hereafter “gate”). The effective capacitance estimation is preceded by a gate modeling.

[0007] The gate is modeled using, for example, a Thévenin equivalent circuit to solve a closed-form equation for the voltage response at the gate output. A closed-form equation is a single equation requiring only one iteration for deriving a solution.

[0008] Effective capacitance determination in accordance with this non-iterative approach involves modeling of an interconnect tree load at the gate output (i.e., the gate load). The gate load modeling uses an accurate RC Π model or open-ended (heuristic) RC Π model (hereafter collectively referred to as the “RC Π model”). The use of an open-ended RC Π model eliminates the need for moment computations at the gate output. The use of an accurate RC Π model requires a determination of the first three moments of the gate load admittance. The gate load modeling uses, in addition, a single capacitance model. Then the effective capacitance value is closely estimated by matching the RC Π model response with that of the single capacitance model.

[0009] The non-iterative approach includes a method for estimating the interconnect capacitive effects. The method includes modeling the gate and estimating an effective capacitance for the interconnect capacitive effects. The effective capacitance estimation includes modeling the gate load at an output of the gate. The gate load modeling includes approximating an admittance of the gate load to a single capacitance model in addition to approximating the admittance of the gate load to a Π model. The gate load modeling also includes matching a gate response for the Π model with the gate response for the single capacitance model to determine the effective capacitance.

[0010] Another aspect of the method for estimating the interconnect capacitive effects includes modeling the gate using an equivalent circuit, and modeling the load at an output of the gate. The gate load modeling includes determining Π model parameters that represent the load at the output of the gate. The parameters are associated with a response at the gate output. The effective capacitance estimation method further includes modeling a single capacitive load at the output of the gate. The single capacitive load modeling includes determining a gate delay for a threshold time at a threshold voltage. This delay determination accounts for the input voltage waveform, the voltage response at the gate output and the Π model parameters. The single capacitance modeling the capacitive load is determined using the threshold time. The effective capacitance is then derived taking into account the single capacitance, a total capacitance of the gate load, an intrinsic gate delay and a gate load delay for the total capacitance as a load.

[0011] For logic synthesis and layout optimization, this non-iterative approach models interconnect capacitive effects faster and with little or no loss of accuracy. Hence, this non-iterative approach is suitable as a step within the analysis loop for performance driven iterative layout optimization.

[0012] The non-iterative approach can, for example, be suitably implemented in timing analysis tools. Such tools are used for analysis and optimization of critical paths in integrated circuits design, including microprocessors design. Moreover, a computer system can be used in which an embodiment of the present invention is implemented

[0013] Advantages of the invention will be set forth, in part, in the description that follows and, in part, will be understood by those skilled in the art from the description herein. The advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the appended claims and equivalents.

Brief Description of the Drawings

[0014] The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate several embodiments of the invention and, together with the description, serve to explain the principles of the invention.

[0015] FIG. 1 shows an example of interconnections between gates including an interconnect tree.

[0016] FIG. 2aillustrates a Thévenin model of the gate.

[0017] FIG. 2billustrates a total gate delay for a threshold voltage at the gate output.

[0018] FIG. 3 illustrates an RC gate load shielding effect at the output of a gate in an integrated circuit designed in accordance with an embodiment of the invention.

[0019] FIG. 4 illustrates the O'Brien/Savarino Π model.

[0020] FIGS. 5aan 5billustrate the open-ended model of an interconnect tree load at the gate output.

[0021] FIGS. 6aand 6bshow the open-ended Π model extended to an RLC network.

[0022] FIGS. 7aand 7billustrate a capacitance model.

[0023] FIGS. 8(a)-8(e) illustrate the effective capacitance estimation in accordance with a non-iterative approach.

Detailed Description of the Invention

[0024] The present invention provides a new non-iterative approach for estimating interconnect capacitive effects on gate output response. This non-iterative approach is considerably faster than conventional methods for computing effective capacitance, with little or no loss of accuracy. Hence, this non-iterative approach is suitable for logic synthesis and performance-driven layout optimization analysis. Moreover, this approach can be implemented in a computer system as a separate tool or as part of other design automation tools.

[0025] The non-iterative approach for estimating interconnect capacitive effects includes modeling both the gate and an interconnect tree load (also referred to as the “gate load”) at the output of the gate. Modeling the gate load involves estimating an effective capacitance.

[0026] Modeling the gate load can be done by approximating an admittance of the gate load to a single capacitance model, in addition to approximating the admittance of the gate load to a Π model. After the admittance approximations, a gate response for the Π model is matched with the gate response for the single capacitance model to determine the effective capacitance.

[0027] Reference will hereafter be made in detail to embodiments of the invention, examples of which are illustrated in the accompanying drawings. Wherever convenient, the same reference numbers will be used throughout the drawings to refer to the same of like parts. The following discussion describes the issues in modeling the interconnect effects and the approach of the invention to solving them. The discussion first examines both the gate and gate load models. The discussion then describes how, in accordance with this invention, the gate and gate load models are used to estimate the interconnect capacitive effects.

[0028] I. The Gate Model

[0029] As mentioned, the modeling of interconnect capacitance effects on the gate output response includes modeling of the gate itself. The modeling of the gate can be accomplished in one of several ways, including: modeling the gate as a Thévenin equivalent circuit with an effective linear resistor driven by a voltage source; modeling the behavior of the gate using relevant parameters such as input slew time(s) and output load capacitance; and modeling the nonlinear gate characteristics using piece-wise linear device models.

[0030] FIG. 2aillustrates a Thévenin model of the gate. In the Thévenin model, the gate 102 is replaced by a voltage source (V_A) 102ain series with the gate output impedance (Z) 102b(as seen from the load 104). The voltage source 102arepresents the open-circuit voltage between the terminals (A and ground). In the Thévenin model of the gate, the effective gate impedance value is obtained such that the non-linear characteristics of the gate are approximated as a piece-wise linear resistor. A resistor of fixed value (R) can be used to model the gate by selecting an appropriate load capacitance to match, for example, the delay for a 50% threshold voltage (V_thd).

[0031] A more accurate model, called the slope model, uses a one-dimensional table to determine the effective gate impedance based on the ratio of input slew time and output slew time. Alternatively, pre-determined total gate delay for various load values is stored in a table format for each gate in a cell library.

[0032] FIG. 2billustrates a total gate delay for a threshold voltage at the gate output. The total gate delay D_ABis expressed as the sum of an intrinsic gate delay of gate 102 and a gate load delay produced by load 104. The intrinsic gate delay is a delay attributed to the physical devices (e.g., transistors) in the gate. Intrinsic gate delay can be thought of as the total gate delay with an infinite load at the output. The intrinsic gate delay is known for each gate in the cell library. Data such as the cell library and delay tables may be stored in a computer readable medium including a computer memory.

[0033] For each gate in the cell library, at least two gate delay tables exist, one for delays and one for slew rates. To form the delay tables, delay and slew rates may be obtained (e.g., during modeling using a circuit simulator) by loading a given gate with a discrete load capacitor and then varying the load capacitance and input slew time. The format of delay tables is equivalent to the so-called empirical “K-factor” formula for delay and output rise time.

[0034] The delay table approach raises some methodology issues. For example, in actual layouts the gate output is connected via interconnects to other gate inputs. Modeling the load at the gate as a single load capacitor may work well for integrated circuit technologies where the area of interconnect at the gate output is small or the interconnect parameters are not dominant compared to gate parameters. However, with submicron technologies the interconnect resistance, capacitance, and inductance need to be considered in the delay table determination (the effects of inductance are increasingly important as integrated circuits geometry becomes smaller).

[0035] II. The Gate Load Model

[0036] As stated above, estimating the interconnect capacitive effects includes modeling the gate load in addition to modeling the gate. It may be recalled that the gate load is the load at the driving gate output. (The driving gate is hereafter referred to as the “gate.”) An interconnection at a gate output produces the gate load. An interconnection may be an interconnect line or an interconnect tree with a number of interconnect lines. It is noted that the term “interconnect tree” is used as a collective term to describe an interconnect tree with any number of branches, i.e., single or multiple interconnect lines.

[0037] Typically, interconnections are metal lines that carry the signals between gates in the integrated circuit. Interconnect lines can be analyzed in terms of their resistive and capacitive components. More detailed models also include inductive components. In the illustrated models, the gate load produced by interconnections is a function of the resistive and capacitive components of the interconnections.

[0038] With narrower deep-submicron interconnect geometries, the resistive component of the gate load is comparable to or larger than the gate output resistance. The resistance of interconnect lines “shields” some load capacitance in that the load capacitance appears smaller with increases in the resistance.

[0039] FIG. 3 illustrates an RC gate load 104 shielding effect at the output of a gate 102 in an integrated circuit designed in accordance with an embodiment of the invention. The admittance Y(s) of the gate load is expressed as an inverse of the impedance Z(s):

[0040] Y_L(s)=sC(1+RsC)⁻¹

[0041] where Y(s) decreases in inverse proportion to an increase in R. This decrease produces the shielding effect.

[0042] The resistance shielding effect is very significant for deep-submicron technologies because it effects the total gate delay. Namely, the total gate delay at the gate output decreases as a result of the interconnect resistance tending to shield some of the load capacitance. For example, the total gate delay at the output decreases when the gate output resistance is kept constant and the interconnect resistance of the load is increased. However, while the total gate delay decreases, the interconnect propagation delay increases as a result of the increase in interconnect resistance.

[0043] A primary approach to estimating gate delays is the modeling of admittance at the gate output. Gate delays are estimated using these models either through a delay table methodology or through an explicit simulation of the gate with the given load model.

[0044] In accordance with an embodiment of the invention, modeling the gate load can be done by approximating an admittance of the gate load to a single capacitance model, in addition to approximating the admittance of the gate load to a Π model. After the admittance approximations, a gate response for the Π model is matched with the gate response for the single capacitance model to determine the effective capacitance. Accordingly, the Π models and single capacitance model are described in detail below.

[0045] A. The Π Model

[0046] The Π model is an equivalent circuit in the form of a single Π network segment approximating the characteristics of the gate load at the respective gate output. The circuit may include resistive and capacitive or resistive, capacitive and inductive components. Although an interconnect line can be approximated to a distributed network, the following exemplary analysis presents a single network segment.

[0047] The Π models examined here, include the O'Brien/Savarino (accurate RC) Π model and the open-ended (heuristic) RC Π model. As exemplified, the Π models include a resistor and two capacitors. The Π models can also include an inductor. However, to simplify this discussion the inductor is omitted.

[0048] In the O'Brien/Savarino (accurate RC) Π model, the interconnect load tree is approximated by an RC Π model with a resistance and capacitance equaling the total interconnect resistance (R_tot) and capacitance (C_tot), respectively. For deep-submicron technologies, the total interconnect resistance is large and comparable to the gate output resistance. Thus, the actual delay is much smaller than the delay derived from an alternative total capacitance model because the interconnect resistance shields the load capacitance seen by the gate. With this approximation, the total interconnect load tree resistance shields the total capacitance.

[0049] FIG. 4 illustrates the O'Brien/Savarino Π model. The O'Brien/Savarino Π model approximates the interconnect load at the gate output by matching the first three moments of the interconnect load admittance at the gate output (i.e., as seen from the gate output).

[0050] In accordance with O'Brien/Savarino Π model, the admittance, Y_L, of the interconnect tree load 104 at the gate output (B) is represented by:

[0051] Y_L(s)=Σ_i=1^∞A_isⁱ=sA₁+s²A₂+s³A₃+

[0052] The parameters of the equivalent circuit are obtained by matching the first three moments of the admittance with corresponding moments of the interconnect tree load admittance of the Π load model in FIG. 4. That is:

\begin{matrix} R_{1} = \frac{- A_{3}^{2}}{A_{2}^{3}}, C_{1} = A_{1} - \frac{A_{2}^{2}}{A_{3}}, and C_{2} = \frac{A_{2}^{2}}{A_{3}} & (1) \end{matrix}

[0053] In accordance with the O'Brien/Savarino Π model, the delay tables need to be expanded from two-dimensional to space consuming four-dimensional tables. One dimension is the slew time of the input voltage. The other three dimensions are the three Π model parameters R₁, C₁, C₂104a,104band 104c,respectively.

[0054] A second Π model approach, the open-ended RC Π model, offers an alternative to the O'Brien/Savarino Π model for estimating the interconnect tree load admittance. The open-ended H model provides a linear-time estimation.

[0055] FIGS. 5aan 5billustrate the open-ended model of an interconnect tree load 104 at a gate 102 output. The open-ended RC Π model approximates the entire interconnect tree 104 by an equivalent open-ended RC line whose resistance (R_tot) and capacitance (C_tot) 104dare equal to the total interconnect resistance and capacitance, as shown in FIG. 5(a). By using an open-ended RC line to approximate the entire tree, the distributed nature of the interconnect tree load is still considered in determining the model parameters. That is, the resistance of the open-ended RC line shields part of the load capacitance from the gate.

[0056] The one-segment RC Π model is open-ended in the sense that parameter values can be set to any value not exceeding the range determined by the total resistance (R_tot) and capacitance (C_tot) 104. In other words, the open-ended RC Π model is a one-segment RC Π model with predetermined parameter values that depend only on the total resistance (R_tot) and capacitance (C_tot) 104.

[0057] In accordance with this modeling approach, as illustrated in FIG. 5b,the admittance Y(s) of an open-ended RC line is approximated to:

Y (s) = \frac{\tanh (θ)}{Z_{0}} = {sC}_{tot} - s^{2} \frac{R_{tot} C_{tot}^{2}}{3} + s^{3} \frac{2 R_{tot}^{2} C_{tot}^{2}}{15} + \dots

[0058] where the propagation constant θ={square root over (R_tot+L sC_tot+L )} and the characteristic impedance

Z_{0} = \sqrt{\frac{R_{tot}}{{sC}_{tot}}} .

[0059] Therefore, the first three moments of the gate load admittance approximating the open-ended RC line are

A_{1} = C_{tot}, A_{2} = - \frac{R_{tot} C_{tot}^{2}}{3}, A_{3} = - \frac{2 R_{tot}^{2} C_{tot}^{3}}{15} .

[0060] Using these values for A₁, A₂and A₃, in equation (1) above yields Π model parameters as shown in FIG. 5(b):

\begin{matrix} R_{1} = \frac{12 R_{tot}}{25}, C_{1} = \frac{C_{tot}}{6}, and C_{2} = \frac{5 C_{tot}}{6} & (2) \end{matrix}

[0061] The open-ended Π model can be extended to RLC networks as shown in FIGS. 6aand 6b.Using this modeling approach to obtain the moments of the gate load admittance increases modeling efficiency because it avoids recursive interconnect tree traversal. Still, if the designer must account for all the possible combinations of C₁, C₂, R₁in the Π model, a very large look-up table or highly complex K-factor formulas (along with a complex, resource consuming modeling process) would be required.

[0062] It may be recalled that estimating the interconnect capacitive effects can be done by approximating an admittance of the gate load to a single capacitance model, in addition to approximating the admittance of the gate load to a Π model. After the admittance approximations, a gate response for the Π model is matched with the gate response for the single capacitance model to determine the effective capacitance that represents the interconnect capacitive effects. Having first considered the Π model, attention is now turned to approximating the admittance of the gate load to the single capacitance model.

[0063] B. The Single Capacitance Model

[0064] The gate load can be modeled using a delay table lookup approach with a single load capacitance to approximates the gate load. FIGS. 7aand 7billustrate a single capacitance model of the load. Specifically, in response to the gate 102 input being excited with, for example, a step or ramp voltage waveform (V_in(t)), the voltage waveform (V_s(t)) at the gate output rises (or falls) to a particular level within the output voltage range. The time-domain response v_out(t) at the gate output can be obtained as a function of the single capacitance, C, 104e.As the output voltage changes, it passes through voltage threshold points, one being the t=t₀(or 0%) point 190 and the other being the t=t_thd(or 50% or 75%, etc. ) point 192. It is for these endpoints that the capacitance, C, 104eis determined.

[0065] It is noted that the term “single capacitance model” means a model using a single capacitor to represent one capacitor or multiple capacitors arranged in series or parallel. In the case of the multiple capacitors in series or in parallel, the single capacitor is an equivalent of the multiple capacitors as is readily known.

[0066] III. The Effective Capacitance Estimation

[0067] As part of the interconnect capacitive effects estimation a non-iterative effective capacitance estimation technique is provided by the present invention. This approach is very useful with respect to each gate for providing an accurate estimation of gate load delays. This approach is less useful for accurate estimation with respect to downstream gates.

[0068] As stated before, the gate model and the gate load models (the Π model and the single capacitance model) are used in the interconnect capacitive effects estimation. Namely, once the gate and gate load modeling is done, the interconnect capacitive effects can be approximated to an effective capacitance. The effective capacitance can be determined from the gate and gate load models as hereafter described.

[0069] More particularly, in accordance with an embodiment of the invention, modeling of the interconnect tree load at the gate output (i.e., the gate load) uses the accurate RC Π model or open-ended (heuristic) RC Π model (hereafter collectively referred to as the “RC Π model”). The use of an open-ended RC Π model eliminates the need for moment computations at the gate output. The use of an accurate RC Π model requires a determination of the first three moments of the gate load admittance. Additionally, the gate is modeled using, for example, a Thévenin equivalent circuit to determine the voltage response at the gate output using the closed-form equation. As noted before, the closed-form equation is a single equation requiring only one iteration to derive a solution.

[0070] The effective capacitance value is closely estimated by matching the RC Π model response with that of the single capacitance model. A more detailed explanation of the non-iterative approach to estimating effective capacitance is now provided.

[0071] FIGS. 8( a)-8(e) illustrate the effective capacitance estimation in accordance with the non-iterative approach. In one embodiment, the effective capacitance estimation is performed using as an input a step voltage waveform, as shown in FIG. 8a.In a second embodiment, the effective capacitance estimation is performed using a ramp voltage waveform at the gate input, as is further shown in FIG. 8a.

[0072] As shown in FIGS. 8band 8c,the Thévenin equivalent circuit models the gate 102 by replacing it with a voltage source (v_s(t)) 102aand a linear source resistance (R_s) 102b.As indicated, in one embodiment the voltage source 102aprovides a step voltage waveform. In the the second embodiment the voltage source 102aprovides a ramp voltage waveform.

[0073] Initially, as shown in FIG. 8b,the interconnect tree load (the gate load) 104 at the gate output is modeled using an open-ended (heuristic) RC Π model. This RC Π model is used for determining the gate load admittance. The open-ended RC Π model includes a resistor (R₁) 104aand two capacitors (C₁and C₂) 104band 104c.An inductor (L) can be included as well to form an RLC Π model. However, for a simpler analysis the inductor is omitted. The open-ended RC Π model components, R₁, C₁and C₂, are expressed as a function of the total interconnect capacitance (C_tot) and resistance (R_tot) The components R₁, C₁, and C₂, are determined n accordance with the relationships as indicated in equation (2).

[0074] Instead of the open-ended RC Π model as shown in FIG. 8b,the gate load modeling can use an accurate RC Π model as shown in FIG. 8c.In this instance, the accurate RC Π model components, R₁, C₁and C₂, are determined by the relationships as indicated in equation (1).

[0075] As a next step in estimating the interconnect capacitive effects, the gate load 104 is modeled using the single capacitance model, as shown in FIG. 8d.As previously explained, the value of the effective capacitance, C_eff, 104′ (FIG. 8e) is closely estimated by matching the RC Π model response (FIGS. 8bor 8c) with that of the single capacitance model (FIG. 8d).

[0076] A. Effective Capacitance Estimation With Step Input

[0077] Starting with the step voltage waveform as an input (V_in) to the gate 102 (FIG. 8a). The gate output response (V_B(s)) produced thereby is analytically computed using the source resistance R_Sand the load which is modeled as the RC Π model as previously described.

[0078] Under these conditions, the response at the gate output (B) in the Laplace transform domain is given by the following transfer function:

\begin{matrix} \begin{matrix} V_{B} (s) = V_{s} (s) \frac{(1 + s R_{1} C_{2})}{1 + s (R_{s} C_{1} + R_{s} C_{2} + R_{1} C_{2}) + s^{2} R_{s} R_{1} C_{1} C_{2}} \\ = \frac{V_{0}}{s} [1 + \frac{(1 + s_{1} R_{1} C_{2})}{s_{1} b_{2} (s_{1} - s_{2})} \frac{1}{(s - s_{1})} + \frac{(1 + s_{2} R_{1} C_{2}}{s_{2} b_{2} (s_{2} - s_{1})} \frac{1}{s - s_{2})}] \end{matrix} & (3) \end{matrix}

[0079] where

b_{1} = R_{s} (C_{1} + C_{2}) + R_{1} C_{2}

b_{1} = R_{s} R_{1} C_{1} C_{2}

s_{1, 2} = \frac{b_{1} \pm \sqrt{b_{1}^{2} - 4 b_{2}}}{2 b_{2}}

[0080] where R₁104a,C₁, 104band C₂104c,are the components of the Π model, and V₀is the output voltage that approximates the maximum V_S.

[0081] Depending on the sign of b₁²−4b₂, the poles of the transfer function can be either real or complex. V_B(t) is the reverse Laplace transform of the transfer function expressing the time domain gate output response. The time domain response, V_B(t), is determined separately for each case, real and complex. Substituting the moments, b₁and b₂, for the parameters in the above equation, produces:

[0082] b₁²−4b₂=R_S²(C₁+C₂)²+R₁²C₂²+2R_SR₁C₂(C₂−C₁) (4)

[0083] For the most part, especially in the case of open-ended RC Π models, the value of C₂104bis greater than C₁104b.Hence, the time domain response, V_B(t), with a load at gate output (B) being represented by an RC Π model, is determined for real poles as follows:

\begin{matrix} V_{B} (t) = V_{0} [1 + \frac{(1 + s_{1} R_{1} C_{2})}{s_{1} b_{2} (s_{1} - s_{2})} ⅇ^{s_{1} t} + \frac{(1 + s_{2} R_{1} C_{2}}{s_{1} b_{2} (s_{2} - s_{1})} ⅇ^{s_{2} t}] & (5) \end{matrix}

[0084] This response is then used to determine the slew time (or delay with respect to input signal) at a specified threshold voltage by matching the results for a single capacitor as a gate load. Assuming that (in the step voltage waveform input case) the load is modeled as a single, step input capacitance, C_step. In other words:

[0085] V_B(t)=V_s(1−e^−t/RsCstep)

[0086] where V_sapproximates 100% of the gate output voltage represented by the voltage source 102a.C_step, the step input capacitance 104e,is the capacitor component of a single capacitance model that is excited by a step input waveform (FIG. 8d). It may be recalled that as the V_B(t) changes it passes through threshold points t=t₀and t=t_thdset for determining the gate response delay (slew rate). Hence, also assuming, for V_B(t), a threshold voltage, V_thd, that is greater than 0% and lower than 100% (e.g., 50%, 90% etc.). Then:

[0087] V_B(t)_thd=V_thd,

[0088] and:

\frac{t_{thd}}{R_{S} C_{step}} = \frac{T_{out}^{Π}}{R_{S} C_{step}} = \ln (\frac{1}{1 - V_{thd}}) = k_{1},

[0089] where k₁is a constant associated with the particular threshold voltage, V_thd, so that:

\begin{matrix} C_{step} = \frac{t_{thd}}{k_{1} R_{S}} = \frac{T_{out}^{Π}}{k_{1} R_{S}} & (6) \end{matrix}

[0090] where T_out^Π is the slew time for a Π model at the gate output for the particular V_thd.

[0091] Finally, the effective capacitance is determined in the range between the step input capacitance C_stepand the total load capacitance C_totunder full load conditions. It may be recalled, that under no load condition the gate response is fast since the gate will not see the interconnect load capacitance. Under full load conditions the gate response is slow because it needs to charge a full capacitive load. The range between C_stepand C_totis set by obtaining the intrinsic gate delay D_NLand the gate load delay D_LD. The intrinsic gate delay, D_NL, is a gate response delay with no load at the gate output, and the gate load delay, D_LD, is a gate response delay with C_totas a load. Intrinsic and gate load delays for specific loads are predetermined and can be obtained from K-factor formulas or look-up tables available for each gate in the cell library. Accordingly, C_effcan be expressed as follows:

\begin{matrix} C_{eff} = C_{step} + (C_{tot} - C_{step}) \frac{1}{1 + D_{LD} / D_{NL}} & (7) \end{matrix}

[0092] This implies that

[0093] C_eff≈C_stepif D_LD/D_NL>>1,

[0094] and

[0095] C_eff≈C_totif D_LD/D_NL<<1.

[0096] Given the Π model parameters (R₁,C₁,C₂) and the predetermined output delay table for the gate, the above-described embodiment provides a non-iterative method for estimating the effective capacitance. The method for estimating the effective capacitance of an interconnect load when the gate is excited with a step voltage waveform includes steps as hereafter outlined. First, determine Π model parameters in accordance with the relationship as expressed in either equation (1) or equation (2). Second, determine the threshold time, t_thd, using a transfer function as demonstrated by equation (5) for the voltage response at the gate output. Third, determine the single capacitor, C_step, from t_thdand R_Susing the relationship of equation (6). Fourth, obtain from the gate delay table the gate load delay D_LDfor the total capacitance, C_tot, as a load and the intrinsic gate delay D_NLfor the no load condition. Fifth, determine C_effusing the relationship expressed in equation (7).

[0097] B. Effective Capacitance Estimation With Ramp Input

[0098] For a ramp voltage waveform as an input to the gate, the following effective capacitance estimation process is presented. In this case, the gate is modeled with a Thévenin equivalent circuit that replaces the gate with a ramp voltage source V_Sand a series source resistance R_S. The ramp voltage is characterized by rise time T_R. To approximate the entire interconnect load tree at the gate output, the RC Π model is used (as before). The voltage V_Bat the gate output (B) in the Laplace transform domain is:

\begin{matrix} V_{B} (s) = V_{S} (s) = \frac{(1 + {sR}_{1} C_{2})}{1 + s (R_{S} C_{1} + R_{S} C_{2} + R_{1} C_{2}) + s^{2} R_{S} R_{1} C_{1} C_{2}} \\ = \frac{V_{O} (1 - ⅇ^{- {sT}_{R}})}{T_{R}} [\frac{1}{s^{2}} - \frac{R_{s} (C_{1} + C_{2})}{s} + \\ \frac{(1 + s_{1} R_{1} C_{2})}{b_{2} s_{1}^{2} (s_{1} - s_{2})} \frac{1}{(s - s_{1})} - \frac{(1 + s_{2} R_{1} C_{2}}{b_{2} s_{2}^{2} (s_{1} - s_{2})} \frac{1}{(s - s_{2})}] \end{matrix}

[0099] where:

[0100] b₁=R_S(C₁+C₂)+R₁C₂,

[0101] b₂=R_SR₁C₁C₂, and:

s_{1, 2} = \frac{- b_{1} \pm \sqrt{b_{1}^{2} - 4 b_{2}}}{2 b_{2}}

[0102] The time-domain response is:

\begin{matrix} \begin{matrix} V_{B} (t) = \frac{V_{O}}{T_{R}} [t - R_{S} (C_{1} + C_{2}) + \frac{(1 + s_{1} R_{1} C_{2})}{b_{2} s_{1}^{2} (s_{1} - s_{2})} ⅇ^{s_{1} t} - \\ \frac{(1 + s_{1} R_{1} C_{2})}{b_{2} s_{2}^{2} (s_{1} - s_{2})} ⅇ^{s_{2} t}] \end{matrix} & (8) \end{matrix}

[0103] for t≦T_R, and:

\begin{matrix} V_{B} (s) = \frac{V_{O}}{T_{R}} [T_{R} + \frac{(1 + s_{1} R_{1} C_{2}) (1 - ⅇ^{- T_{R} s_{1}})}{b_{2} s_{1}^{2} (s_{1} - s_{2})} ⅇ^{s_{1} t} - \\ \frac{(1 + s_{2} R_{1} C_{2}) (1 - ⅇ^{- T_{R} s_{1}})}{b_{2} s_{2}^{2} (s_{1} - s_{2})} ⅇ^{s_{2} t}] \end{matrix}

[0104] for t>T_R.

[0105] Depending on the sign of b₁²−4b₂, the poles will be either real or complex. As before (equation (4)), the quantity b₁²−4b₂is positive. Accordingly, the case of real poles is analyzed here.

[0106] From the output response, V_B(t), the threshold time, t_thd, is determined for a user-specified threshold voltage (e.g. 50%, 90% etc.). The ramp input capacitance, C_ramp, 104eis the capacitive component of the single capacitance model, excited by a ramp voltage waveform, as shown in FIG. 8d.The ramp input capacitance, C_ramp, is then determined for the given threshold time, t_thd(T_out^Π for Π model) as follow:

\begin{matrix} C_{ramp} = \frac{t_{thd}}{k_{2} R_{S}} = \frac{T_{out}^{Π}}{k_{2} R_{S}} & (9) \end{matrix}

[0107] where the constant k₂is an absolute value expressed as:

\begin{matrix} k_{2} = | \ln (\frac{1}{1 + \frac{V_{thd} T_{R}}{R_{S} C_{tot}} - \frac{T_{R}}{R_{S} C_{tot}}}) | for t \leq T_{R}, & (10) \end{matrix}

[0108] and:

k_{2} = | \ln (\frac{R_{S} C_{tot}}{T_{R}} \cdot \frac{(ⅇ^{\frac{1}{R_{S} C_{tot} / T_{R}}} - 1)}{(1 - V_{thd})}) | for t > T_{R} .

[0109] Finally, the effective capacitance, C_eff, is determined in the range between the ramp input capacitance C_rampand total load capacitance C_tot, as in the previous case. The intrinsic gate load, D_NL, and the gate load, D_LD, with C_totas the load, are then obtained from the k-factor formulas or delay tables for the gate. From the above, the the effective capacitance, C_eff, is determined as follows:

\begin{matrix} C_{eff} = C_{ramp} + (C_{tot} - C_{ramp}) \cdot \frac{1}{1 + D_{LD} / D_{NL}} & (11) \end{matrix}

[0110] This again implies that:

[0111] C_eff≈C_stepif D_LD/D_NL>>1,

[0112] and

[0113] C_eff≈C_totif D_LD/D_NL<<1.

[0114] Given the Π model parameters (R₁,C₁,C₂) and the predetermined output delay table for the gate, this embodiment provides a non-iterative method for estimating the effective capacitance. The following method for estimating the effective capacitance of an interconnect load is suitable when the gate is excited with a ramp voltage waveform. First, determine Π model parameters using the relationships expressed in either equation (1) or equation (2). Second, determine the threshold time, t_thd, by determining the voltage response at the gate output based on a transfer function as expressed in equation (8). Third, determine the single capacitance, the ramp input capacitance C_ramp, from t_thdand R_Sin accordance with the relationships as expressed in equations (9) and (10). Fourth, obtain from the gate delay table the gate load delay D_LDfor C_totas a load and the intrinsic gate delay D_NLfor the no load condition. Fifth, determine C_effusing the relationship expressed in equation (11).

[0115] In summary, the present invention provides a new non-iterative approach for estimating the interconnect capacitive effects on the gate output response. This approach includes estimating the effective capacitance of an interconnect load at the gate output. For logic synthesis and layout optimization, this approach models interconnect effects more accurately. This non-iterative approach is considerably faster than conventional methods for computing effective capacitance, with little or no loss of accuracy. This approach for estimating effective capacitance works especially well for threshold voltages between 30% to 60%.

[0116] Accordingly this non-iterative approach is advantageous in providing accurate delay analysis within a tight synthesis-analysis loop. For instance, in performance-driven layout optimization, this non-iterative approach is suitable as a step within the analysis loop.

[0117] Other embodiments will be apparent to those skilled in the art from consideration of the specification and practice of the invention disclosed herein. It is intended that the specification and examples be considered as exemplary only, with a true scope of the invention being indicated by the following claims and equivalents.

Claims

What is claimed is:

1. A method for estimating interconnect capacitive effects, comprising:

modeling a gate; and

estimating an effective capacitance that models the interconnect capacitive effects, the effective capacitance estimation including:

modeling a gate load at an output of the gate, including:

approximating an admittance of the gate load to a single capacitance model; and

approximating the admittance of the gate load to a Π model; and

matching a gate response for the Π model with the gate response for the single capacitance model to determine the effective capacitance.

2. The method of claim 1, being implemented in a computer system.

3. A method of claim 1, wherein the effective capacitance has a value falling within a range extending between a total capacitance of the load and a capacitance of the single capacitance model, the capacitance being determined for a particular voltage waveform applied at an input of the gate and a threshold voltage at the gate output.

4. A method of claim 3, wherein the range is set by obtaining an intrinsic gate delay and a gate load delay, and wherein the intrinsic gate delay and the gate load delay are obtained using a table look-up.

5. A method of claim 3, wherein the voltage waveform is one of step and ramp voltage waveforms, and wherein based on the voltage waveform the single capacitance model includes one of a step input capacitance (C_step) and a ramp input capacitance (C_ramp).

6. The method of claim 1, wherein the gate is modeled using an equivalent circuit including a Thévenin equivalent with an impedance driven by a voltage source.

7. The method of claim 6, wherein the impedance is determined such that non-linear characteristics of the gate are approximated as a piece-wise linear resistor.

8. The method of claim 1, wherein the gate is modeled using parameters including a slew rate and load capacitance.

9. The method of claim 1, wherein the Π model is an RC Π model including a resistor and two capacitors.

10. The method of claim 1, wherein the Π model is an RLC model including a resistor, an inductor and two capacitors.

11. The method of claim 1, wherein the gate modeling is for solving a closed-form equation for a voltage response at a gate output.

12. A method for estimating interconnect capacitive effects on a response of a gate, comprising:

modeling the gate;

determining Π model parameters of a load at an output of the gate;

determining a gate delay for a threshold time (t_thd) at a threshold voltage taking into account the Π model parameters, the gate delay being associated with a voltage response at the gate output;

determining a capacitance of a single capacitance model of the load, the capacitance being dependent on the threshold time (t_thd);

obtaining from a gate delay table a gate load delay for a total capacitance (C_tot) as the load and an intrinsic gate delay for a no load condition; and

determining an effective capacitance (C_eff) based on the capacitance of the single capacitance model, the intrinsic gate delay and the gate load delay.

13. A method of estimating interconnect capacitive effects, comprising:

modeling a gate using an equivalent circuit;

modeling a load at an output of the gate, including determining Π model parameters, the Π model representing the load at the gate output, the Π model parameters being associated with a response at the gate output;

modeling the load using a single capacitance model, including:

determining a threshold time corresponding to a threshold voltage at the gate output; and

determining a capacitance of the single capacitance model using the threshold time;

obtaining an intrinsic gate delay;

obtaining a gate load delay for a total capacitance as a load; and

determining an effective capacitance taking into account the capacitance of the single capacitance model, total capacitance, intrinsic gate delay and gate load delay.

14. The method of claim 13, being implemented in a computer system.

15. The method of claim 13, further comprising providing a voltage waveform at an input of the gate to produce a response at the gate output, and wherein the voltage waveform is one of step and ramp voltage waveforms.

16. The method of claim 13, wherein the equivalent circuit is a thévenin equivalent that substitutes the gate with a voltage source and a series resistor.

17. The method of claim 13, wherein the load is an interconnect tree load having a total resistance and the total capacitance, and wherein the parameters are determined in accordance with one of two relationships, a first of the two relationships being a function of the total capacitance and total resistance when the Π model is an open-ended Π model, and a second of the two relationships being a function of the first three moments of an admittance of the load when the Π model is an accurate Π model, the Π model approximating the load admittance.

18. The method of claim 13, wherein the intrinsic gate delay and gate load delay are predetermined for various load values and are obtained from a cell library.

19. The method of claim 18, wherein for each gate in the cell library at least two gate delay tables exist, one for a delay and one for a slew rate.

20. The method of claim 19, wherein the format of the gate delay tables is equivalent to empirical K-factor formulas for delay and slew rate.

Patent Citations (4)

Patent	Date	Inventor	Cited By
US5285165	1994-02-01	Renfors et al.	Applicant
US5544068	1996-08-01	Takimoto et al.	Examiner
US5790415	1998-08-01	Pullela et al.	Examiner
US5841672	1998-11-01	Spyrou et al.	Examiner

Non-Patent Literature (40)

Arunachalam et al., “CMOS Gate Delay Models for General RLC Loading,” 1997 IEEE, pp. 224-229.Applicant
Hafed et al., “CMOS Inverter Current and Delay Model Incorporating Interconnect Effects,” 1998 IEEE, pp. 86-89.Applicant
Kahng et al., “Improved Effective Capacitance Computations for Use in Logic and Layout Optimization,” Proc. 12th Int'l Conference on VLSI Design, Jan. 1999 [no page numbers].Applicant
Krauter et al., “Including Inductive Effects in Interconnect Timing Analysis,” IEEE 1999 Custom ICs Conference, pp. 445-452.Applicant
Semiconductor Industry Association, National Technology Roadmap for Semiconductors, pages Table of Contents, pp. 1-3, 7-19, 23-113, 163-178, Appendix B1-C8, 1994.Applicant
Personal communication, SIA NTRS 1997 Revision, Design and Test Technology Working Group (chairs: R. Howard, P. Verhofstadt), 1997, Table of Contents, pp. 1-3, 8, 10-17, 25-38, 94-109, Appendix B, C and D, 1997.Applicant
C. J. Alpert and A. Devgan, “Wire Segmenting for Improved Buffer Insertion”, Proc. Design Automation Conf., pp. 558-593, Jun. 1997.Applicant
D. P. LaPotin, U. Ghoshal, E. Chiprout, S. R. Nassif, “Physical Design Challenges For Performance”, International Symposium on Physical Design, pp. 225-226, Apr. 1997.Applicant
L. Scheffer, “A Roadmap Of CAD Tool Changes For Sub-Micron Interconnect Problems”, International Symposium on Physical Design, pp. 104-109, Apr. 1997.Applicant
R. F. Sechler, “Interconnect design with VLSI CMOS”, IBM Journal of Research and Development, pp. 23-31, Jan.-Mar. 1995.Applicant
J. Cong, L. He, A. B. Kahng, D. Noice, N. Shirali and S. H.-C. Yen, Analysis And Justification Of A Simple, Practical 2½-D Capacitance Extraction Methodology, Proc. Design Automation Conference, pp. 627-632, Jun. 1997.Applicant
L. Gwennap, “IC Vendors Prepare for 0.25-Micron Leap”, Microprocessor Report, pp. 11-15, Sep. 16, 1996.Applicant
S.Y. Oh, K.-J. Chang, N. Chang and K. Lee, “Interconnect Modeling And Design In High-Speed VLSI/ULSI Systems”, Proc. International Conference on Computer Design: VLSI in Computers and Processors, pp. 184-189, Oct. 1992.Applicant
H.B. Bakoglu, “Circuits, Interconnections, and Packaging for VLSI,” Addison-Wesley Publishing Company, 1990, pp. 202-207, 212-215, 282-285.Applicant
A. Devgan, “Efficient Coupled Noise Estimation for On-Chip Interconnects,” IEEE International Conference on Computer-Aided Design, Nov. 1997, pp. 147-151Applicant
G.A. Katopis and H.H. Smith, “Coupled Noise Predictors for Lossy Interconnects,” IEEE Transactions on Components, Packaging, and Manufacturing Technology—Part B. vol. 17, No. 4, Nov. 1994, pp. 520-524.Applicant
H. Kawaguchi and T. Sakurai, “Delay and Noise Formulas for Capacitively Coupled Distributed RC Lines,” Proc. Asian and South Pacific Design Automation Conference, 1998, pp. 35-43.Applicant
K. Rahmat, O.S. Nakagawa, S-Y. Oh and J. Moll, “A Scaling Scheme for Interconnect in Deep-Submicron Processes,” IEEE International Electronic Devices Meeting, 1995, pp. 10.2.1-10.2.4.Applicant
K.L. Shepard, S.M. Carey, E.K. Cho, B.W. Curran, R.F. Hatch, D.E. Hoffman, S.A. McCabe, G.A. Northrop, R. Seigler, “Design Methodology for the S/390 Parallel Enterprise Server G4 Microprocessors,” IBM Journal of Research and Development, vol. 41, No. 4/5, Jul./Sep. 1997, pp. 515-547.Applicant
A. Vittal and M. Marek-Sadowska, “Crosstalk Reduction for VLSI,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 16, No. 3, Mar. 1997, pp. 290-298.Applicant
G. Yee, R. Chandra, V. Ganesan and C. Sechen, “Wire Delay in the Presence of Crosstalk,” ACM/IEEE International Workshop on Timing Issues in the Specification and Synthesis of Digital Systems, Dec. 97, pp. 170-175.Applicant
K.L. Shepard and V. Narayanan, “Conquering Noise in Deep-Submicron Digital Ics,” IEEE Design & Test of Computers, Jan.-Mar. 1998, pp. 51-62.Applicant
K. Rahmat, J. Neves and J.F. Lee, “Methods for calculating coupling noise in early design: a comparative analysis,” IEEE 1998, pp. 76-81.Applicant
R. Macys and S. McCormick, “A New Algorithm for Computing the Effective Capacitance in Deep Sub-micron Circuits,” IEEE Custom Integrated Circuits Conference, 1998, pp. 313-316.Applicant
T. Sakurai, “Closed-Form Expressions for Interconnection Delay, Coupling, and Crosstalk in VLSI's”, IEEE Transactions on Electron Devices, vol., 40, No. 1, pp. 118-124, Jan. 1993.Applicant
W. C. Elmore, “The Transient Response Of Damped Linear Networks with Particular Regard To Wideband Amplifiers,” Journal of Applied Physics, vol. 19, Jan.-Dec. 1948, pp. 55-63.Applicant
A.B. Kahng and S. Muddu, “Efficient Gate Delay Modeling For Large Interconnect Loads,” Proc. IEEE Multi-Chip Module Conference, Feb. 1996, 6 pages.Applicant
A.B. Kahng and S. Muddu, “An Analytical Delay Model For RLC Interconnects,” IEEE 1996, pp. 237-240.Applicant
A.B. Kahng, K. Masuko and S. Muddu, “Analytical Delay Models For VLSI Interconnects Under Ramp Input”, IEEE/ACM International Conference on CAD, Nov. 1996, 7 pages.Applicant
A.B. Kahng and S. Muddu, “A Glossary On Analysis And Modeling Of VLSI Interconnections,” marked Confidential, including Contents, Feb. 1996, 3 pages.Applicant
S.P. McCormick, “Modeling and Simulation of VLSI Interconnections with Moments,” RLE Technical Report No. 543, PhD Thesis, MIT, May 1989, No page #s.Applicant
J.K. Ousterhout, “A Switch-Level Timing Verifier For Digital MOS VLSI,” IEEE Transactions on Computer-Aided Design, vol. CAD-4, No. 3, Jul. 1985, pp. 336-349.Applicant
P.R. O'Brien and T.L. Savarino, “Modeling the Driving-Point Characteristic Of Resistive Interconnect For Accurate Delay Estimation,”Proc. IEEE, 1989, pp. 512-515.Applicant
P.R. O'Brien and T.L. Savarino, “Efficient On-Chip Delay Estimation For Leaky Models Of Multiple-Source Nets,” Proc. IEEE 1990, Custom Integrated Circuits Conference, pp. 9.6.1-9.6.4.Applicant
L.T. Pillage, “Asymptotic Waveform Evaluation For Timing Analysis,” IEEE Transactions on Computer-Aided Design, vol. 9, No. 4, Apr. 1990, pp. 352-366.Applicant
J. Qian, S. Pullela and L. Pillage, “Modeling The Effective Capacitance For The RC Interconnect Of CMOS Gates,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 13, No. 12, Dec. 1994, pp. 1526-1535.Applicant
J. Rubinstein, P. Penfield, Jr. And M.A. Horowitz, “Signal Delay In RC Tree Networks,” IEEE Transactions on Computer-Aided Design, vol. CAD-2, No. 3, Jul. 1983, pp. 202-211.Applicant
C.L. Ratzlaff, S. Pullela and L. T. Pillage, “Modeling The RC-Interconnect Effects In A Hierarchical Timing Analyzer,” IEEE Custom Integrated Circuits Conference, May 1992, pp. 15.6.1-15.6.4.Applicant
Synopsys, “Design Compiler Family Reference Manual,” Version 3.3a, Mar. 1995, pp. 8-1-8-5.Applicant
A.B. Kahng, K. Masuko and S. Muddu, “Analytical Delay Models for VLSI Interconnects Under Ramp Input,” IEEE/ACM International Conference on CAD, Nov. 1996, 7 pages.Applicant