System and method for fast interconnect delay estimation through iterative refinement
First Claim
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).
7 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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). - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
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:
-
where;
wherein a node(i) is adjacent to node(j) and between node(j) and the source node;
where Rj is the resistance between node(j) and node(i);
where Cj is the capacitance adjacent to node(j); and
where tr 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;
wherein a node(i) is adjacent to node(j) and located between node (j) and the source node, and further wherein;
Rj is the resistance between node(j) and node(i), Cj is the capacitance adjacent to node(j), and tr 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. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18)
-
-
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:
-
where;
wherein a node(i) is adjacent to node(j) and between node(j) and the source node;
where Rj is the resistance between node(j) and node(i);
where Cj is the capacitance adjacent to node(j); and
where tr 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:
-
where Ci is the capacitance adjacent to node(i);
where Cj is an effective capacitance of an RC tree node(j) adjacent to node(i) in the direction of a sink;
where Kj is the capacitance shielding factor at node(j), which is defined as;
where wherein a node(i) is adjacent to node(j) and between node(j) and the source node;
where Rj is the resistance between node(j) and node(i);
where Cj is the capacitance adjacent to node(j); and
where tr 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;
wherein a node(i) is adjacent to node(j) and between node(j) and the source node, and further wherein;
Rj is the resistance between node(j) and node(i), Cj is the capacitance adjacent to node(j), and tr 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;
-
Specification