System and method for fast interconnect delay estimation through iterative refinement

• US 6,601,223 B1
• Filed: 09/29/2000
• Issued: 07/29/2003
• Est. Priority Date: 09/29/2000
• Status: Active Grant

• Current Assignee: Globalfoundries US Incorporated (GlobalFoundries, Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Kung, David S., Drumm, Anthony, Puri, Ruchir
• Primary Examiner(s): Smith, Matthew
• Assistant Examiner(s): Bowers, Brandon
• Application Number:
  US09/675,634
• Time in Patent Office: 1,033 Days
• Field of Search: 716/6, 716/5, 716/2, 716/4, 716/1
• US Class Current: 716/113
• CPC Class Codes: G06F 30/33 Design verification, e.g. functional simulation or model checking

Abstract

A system and method are proposed for estimating interconnect delay in an Integrated Circuit (IC). A formula for effective capacitance is derived which considers the effect of slew as well as resistive shielding of capacitance, thus yielding more accurate delays for both the interconnects and the source driver (transistor gate). In the system and method, a resistor-capacitor (RC) tree model is used for iterative calculations of effective capacitance and slew for each RC tree node. The effective capacitance is determined for each node by proceeding outward from the source to the sinks, and the slew for each node is determined, using the effective capacitances just determined, by proceeding inward from the sinks to the source node. Once the source node slew determined at a previous iteration is within a specified threshold of the source node slew in the present iteration, the method stops and stores the present iteration values as the final estimates.

Claims

1. A method for estimating the interconnect delay times in an integrated circuit using a resistor-capacitor (RC) tree model, comprising the steps of:

a) initializing an effective capacitance for each RC tree node;

b) initializing a delay on each RC tree segment;

c) computing slew at a source node of the RC tree, using an effective capacitance last calculated for the source node;

d) computing remaining slews for each node in the RC tree by propagating outward to sinks from the source;

e) recomputing effective capacitances for each RC tree node by propagating inward to the source node from the sinks;

f) updating the delay of each RC tree segment using effective capacitances recomputed in step (e);

g) recomputing the source node slew using an effective capacitance recomputed in step (e); and

h) repeating steps (d) to (h) until the source node slew computed at step (c) is within a specified threshold from the source node slew recomputed at step (g).

2. The method as recited in claim 1, wherein each initial effective capacitance in step (a) is a sum of all capacitances downstream from said RC node.

3. The method as recited in claim 1, wherein each initial delay in step (b) and each updated delay in step (f) is a corresponding Elmore delay.

4. The method as recited in claim 1, wherein the slew function used in step (c) is a driver slew equation that depends only on output capacitance.

5. The method as recited in claim 1, wherein each remaining slew(i) is calculated in step (d) using the following equation:

6. The method as recited in claim 1, wherein recomputing step (e) uses a capacitance shielding factor for each node.

7. The method as recited in claim 6, wherein the capacitance shielding factor K for a node(j) is determined by the following equation:

$K_j=\left(1-2<br><br>\text{\hspace{1em}<br><br>}<br><br>x_j<br><br>\left(1-{\mathrm{<br><br>}}^{-\frac{1}{2<br><br>\text{\hspace{1em}<br><br>}<br><br>x_j}}\right)\right)$

where;

$x_j=\frac{R_j<br><br>C_j}{t_r}$

wherein a node(i) is adjacent to node(j) and between node(j) and the source node;

where R_j is the resistance between node(j) and node(i);

where C_j is the capacitance adjacent to node(j); and

where t_r is the slew of a ramp input voltage at node(i).

8. The method as recited in claim 1, wherein recomputing step (e) uses the following equation at tree node i:

9. A method for estimating interconnect delay times in an integrated circuit using an initialized resistor-capacitor (RC) tree model, comprising iteratively performing at least the following steps:

a) computing slews for each RC tree node, starting from a source node and proceeding outward to sinks, and using current values for effective capacitance, each of said current values being an initialized value or an updated value, said current values being determined during the current iteration; and

b) computing updated effective capacitances for each RC tree node using a capacitance shielding factor, starting at the sinks and proceeding inward to the source node;

wherein steps (a) and (b) are iteratively repeated until the source node slew calculated using the updated respective effective capacitance is within a specified threshold from the source node slew computed at a previous iteration of step (b);

wherein the capacitance shielding factor K for a node(j) is determined by the following equation;

$K_j=\left(1-2<br><br>x_j<br><br>\left(1-{\mathrm{<br><br>}}^{-\frac{1}{2<br><br>x_j}}\right)\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\text{where;<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_j=\frac{R_j<br><br>C_j}{t_r}$

wherein a node(i) is adjacent to node(j) and located between node (j) and the source node, and further wherein;

R_j is the resistance between node(j) and node(i),

C_j is the capacitance adjacent to node(j), and

t_r is the slew of a ramp input voltage at node(i).

10. A method for estimating the interconnect delay times in an integrated circuit using a resistor-capacitor (RC) tree model, comprising the steps of:

a) initializing an effective capacitance for each RC tree node with a sum of all downstream capacitances;

b) initializing a delay on each RC tree segment with a corresponding Elmore delay;

c) computing slew at a source node of the RC tree, using an effective capacitance last calculated for the source node;

d) computing remaining slews in the RC tree by propagating outward to sinks from the source, using the following equation;

11. A computer system for estimating the interconnect delay times in an integrated circuit using a resistor-capacitor (RC) tree model, the computer system comprising:

at least one computer-readable medium including;

code that initializes an effective capacitance for each RC tree node;

code that initializes a delay on each RC tree segment;

code that computes a slew at a source node of the RC tree, using an effective capacitance last calculated for the source node;

code that computes remaining slews for each node in the RC tree by propagating outward to sinks from the source;

code that recomputes effective capacitances for each RC tree node by propagating inward to the source node from the sinks;

code that updates the delay on each RC tree segment using effective capacitances recomputed by the code that recomputes the effective capacitances;

code that recomputes the source node slew using an effective capacitance recomputed by the code that recomputes the effective capacitances; and

code that iterates through the code that computes the source node slew, the code that recomputes the effective capacitances, and code that recomputes the source node slew until the source node slew computed by the code that computes the source node slew is within a specified threshold from the source node slew recomputed by the code that recomputes the source node slew.

12. The computer system as recited in claim 11, wherein the code that initializes an effective capacitance for each RC tree node uses a sum of all capacitances downstream from said each RC node.

13. The computer system as recited in claim 11, wherein the code that initializes a delay on each RC tree segment and the code that updates the delay on each RC tree segment uses a corresponding Elmore delay.

14. The computer system as recited in claim 11, wherein the code that computes a slew at a source node of the RC tree, uses a driver slew equation that depends only on output capacitance.

15. The computer system as recited in claim 11, wherein the code that computes remaining slews for each node in the RC tree by propagating outward to sinks from the source uses the following equation:

16. The computer system as recited in claim 11, wherein the code that recomputes effective capacitances for each RC tree node by propagating inward to the source node from the sinks uses a capacitance shielding factor for each node.

17. The computer system as recited in claim 16, wherein the capacitance shielding factor K for a node(j) is determined by the following equation:

$K_j=\left(1-2<br><br>x_j\left(1-{\mathrm{<br><br>}}^{-\frac{1}{2<br><br>x_j}}\right)\right)$

where;

$x_j=\frac{R_j<br><br>C_j}{t_r}$

wherein a node(i) is adjacent to node(j) and between node(j) and the source node;

where R_j is the resistance between node(j) and node(i);

where C_j is the capacitance adjacent to node(j); and

where t_r is the slew of a ramp input voltage at node(i).

18. The computer system as recited in claim 11, wherein the code that recomputes effective capacitances for each RC tree node by propagating inward to the source node from the sinks uses the following equation at tree node i:

$C_{\mathrm{eff}}=C_i+\underset{\mathrm{over\_all}<br><br>\mathrm{\_nodes}<br><br>\mathrm{\_j}}{\sum <br><br>}<br><br>C_j<br><br>K_j$

where C_i is the capacitance adjacent to node(i);

where C_j is an effective capacitance of an RC tree node(j) adjacent to node(i) in the direction of a sink;

where K_j is the capacitance shielding factor at node(j), which is defined as;

$K_j=\left(1-2<br><br>x_j\left(1-{\mathrm{<br><br>}}^{-\frac{1}{2<br><br>x_j}}\right)\right)$

where $x_j=\frac{R_j<br><br>C_j}{t_r}$

wherein a node(i) is adjacent to node(j) and between node(j) and the source node;

where R_j is the resistance between node(j) and node(i);

where C_j is the capacitance adjacent to node(j); and

where t_r is the slew of a ramp input voltage.

19. A computer system for estimating interconnect delay times in an integrated circuit using an initialized resistor-capacitor (RC) tree model, the computer system comprising:

at least one computer-readable medium, said medium including computer-readable program code for iteratively performing the following;

a) computing slews for each RC tree node, starting from a source node and proceeding outward to sinks, and using current values for effective capacitance, each of said current values being an initialized value or an updated value, said current values being determined during the current iteration; and

b) computing updated effective capacitances for each RC tree node using a capacitance shielding factor, starting at the sinks and proceeding inward to the source node;

wherein steps (a) and (b) are iteratively repeated until the source node slew calculated using the updated respective effective capacitance is within a specified threshold from the source node slew computed at a previous iteration of step (b);

wherein the capacitance shielding factor K for a node(j) is determined by the following equation;

$K_j=\left(1-2<br><br>x_j<br><br>\left(1-{\mathrm{<br><br>}}^{-\frac{1}{2<br><br>x_j}}\right)\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\text{where;<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_j=\frac{R_j<br><br>C_j}{t_r}$

wherein a node(i) is adjacent to node(j) and between node(j) and the source node, and further wherein;

R_j is the resistance between node(j) and node(i),

C_j is the capacitance adjacent to node(j), and

t_r is the slew of a ramp input voltage at node(i).

20. A computer system for estimating the interconnect delay times in an integrated circuit using a resistor-capacitor (RC) tree model, the computer system comprising:

at least one computer-readable medium including;

code that initializes an effective capacitance for each RC tree node with a sum of all downstream capacitances;

code that initializes a delay on each RC tree segment with a corresponding Elmore delay;

code that computes a slew at a source node of the RC tree;

code that computes remaining slews for each node in the RC tree by propagating outward to sinks from the source, using the following equation;