Efficient statistical timing analysis of circuits
Statistical timing analysis methods for circuits are described which compensate for circuit elements having correlated timing delays with a high degree of computational efficiency. An quadratic timing model is used to represent each delay element along a circuit path, wherein each element's delay has a first-order relationship to local variations and a second-order relationship to global variations. Propagation of the modeled delays through the circuit is efficiently done via straightforward ADD operations where an input propagates through another element in a circuit path, and via a MAX operation (or an approximation thereof) where two or more inputs merge at an intersection. The inputs to the MAX operator can be tested for gaussianity, and can be processed by the MAX operation (or its approximation) if they are substantially gaussian. Otherwise, they may be stored in a tuple for processing at later points along the circuit path.
1. A method for predicting the signal delay in a circuit having circuit paths formed by elements connected by interconnects wherein:
(1) at least some of the circuit paths intersect;
(2) all elements and interconnects each:
(a) have an associated signal delay D, and
(b) have at least one of:
(i) an adjacent upstream element or interconnect from which a signal delay is propagated, and
(ii) an adjacent downstream element or interconnect to which the signal delay D is propagated;
(3) at least one set of correlated signal delays is present, wherein at least one of the signal delays D X therein is correlated with at least one of the other signal delays D Y therein such that cov(D X , D Y ) is nonzero, and
(4) one or more sets of correlated signal delays arise from global variations, the method comprising the following steps at any path intersection wherein at least two circuit paths intersect, with a first circuit path having a signal delay D 1 and a second circuit path having a signal delay D 2 :
a. modeling each signal delay D by a function dependent on
∑
i
=
1
M
∑
k
=
1
M
Γ
i
,
k
G
i
G
k
wherein:
M is the number of global variations in the circuit;
G i and G k are each a global variation reflecting the uncertainty in the value of D, each such uncertainty being shared by the element and one or more other elements in the circuit; and
Γ i,k is a global sensitivity coefficient reflecting the dependence of D on both of global variations G i and G k in the circuit;
b. evaluating using a computer the gaussianity of the function MAX(D 1 , D 2 );
c. if the gaussianity does not meet a threshold standard, storing signal delays D 1 and D 2 in a signal delay tuple Mt; and
d. propagating the signal delay tuple Mt to any downstream element or interconnect using the computer.
2. The method of claim 1 wherein:
a. the step of evaluating the gaussianity of the function MAX(D 1 , D 2 ) includes determining the skewness of the function MAX(D 1 , D 2 ); and
b. the step of storing signal delays D 1 and D 2 in a signal delay tuple Mt is performed if the skewness of the function MAX(D 1 , D 2 ) is greater than a threshold value.
3. The method of claim 1 wherein the signal delay of any adjacent downstream element or interconnect is added to each signal delay within the signal delay tuple Mt.
4. The method of claim 1 further comprising the step, at any downstream path intersections at which the circuit path bearing the signal delay tuple Mt intersects with a circuit path bearing a signal delay D 0 , of storing the signal delay D 0 in the signal delay tuple Mt.
5. The method of claim 4 further comprising the steps of:
a. evaluating the gaussianity of the function MAX(D 0 , D Mt ), wherein D Mt is a signal delay from within the signal delay tuple Mt;
b. if the gaussianity meets a threshold standard, substituting MAX(D 0 , D Mt ) for D 0 and D Mt within the signal delay tuple Mt.
6. The method of claim 5 wherein the step of evaluating the gaussianity of the function MAX(D 0 , D Mt ) includes determining the skewness of the function MAX(D 0 , D Mt ).
7. The method of claim 1 further comprising the steps, at any downstream path intersections at which the circuit path bearing the signal delay tuple intersects with a circuit path bearing a signal delay D, of:
a. evaluating the gaussianity of the function MAX(D 0 , D Mt ), wherein D Mt is a signal delay from within the signal delay tuple Mt;
b. if the gaussianity meets a threshold standard, substituting MAX(D 0 , D Mt ) for D Mt within the signal delay tuple Mt.
8. The method of claim 1 further comprising the step of performing Monte Carlo simulation on the signal delays within the signal delay tuple Mt.
9. The method of claim 1 wherein the function modeling each signal delay D is also dependent on:
∑
i
=
1
M
β
i
G
i
wherein β i is a global sensitivity coefficient reflecting the dependence of D on global variation G i in the circuit.
10. A method for predicting the signal delay in a circuit having circuit paths formed by elements connected by interconnects wherein:
(1) at least some of the circuit paths intersect;
(2) all elements and interconnects each:
(a) have an associated signal delay D, and
(b) have at least one of:
(i) an adjacent upstream element or interconnect from which a signal delay is propagated, and
(ii) an adjacent downstream element or interconnect to which the signal delay D is propagated;
(3) at least one set of correlated signal delays is present, wherein at least one of the signal delays D X therein is correlated with at least one of the other signal delays D Y therein such that cov(D X , D Y ) is nonzero, and
(4) one or more sets of correlated signal delays arise from global variations, the method comprising the following steps at any path intersection wherein at least two circuit paths intersect, with a first circuit path having a signal delay D 1 and a second circuit path having a signal delay D 2 ,
a. evaluating using a computer the gaussianity of the function MAX(D 1 , D 2 );
b. if the gaussianity does not meet a threshold standard, storing signal delays D 1 and D 2 in a signal delay tuple Mt; and
c. propagating the signal delay tuple Mt to any downstream element or interconnect using the computer;
wherein each signal delay D is modeled by:
D
=
μ
D
+
∑
j
=
1
N
α
j
R
j
+
∑
i
=
1
M
β
i
G
i
+
∑
i
=
1
M
∑
k
=
1
M
Γ
i
,
k
G
i
G
k
wherein:
μD is a nominal value for D;
N is the number of signal delays in the circuit;
M is the number of global variations in the circuit;
α j is a node sensitivity coefficient reflecting the dependence of D on signal delay j in the circuit;
R j is a local variation reflecting the uncertainty in the value of D localized in the element;
G i and G k are each a global variation reflecting the uncertainty in the value of D, each such uncertainty being shared by the element and one or more other elements in the circuit;
β i is a global sensitivity coefficient reflecting the dependence of D on global variation Gi in the circuit; and
Γ i, k is a global sensitivity coefficient reflecting the dependence of D on both of global variations Gi and Gk in the circuit.
11. A method for predicting the signal delay in a circuit having circuit paths formed by elements connected by interconnects wherein:
(1) at least some of the circuit paths intersect,
(2) all elements and interconnects each:
(a) have an associated signal delay D, and
(b) have at least one of:
(i) an adjacent upstream element or interconnect from which a signal delay is propagated, and
(ii) an adjacent downstream element or interconnect to which the signal delay D is propagated;
(3) at least one set of correlated signal delays is present, wherein at least one of the signal delays D X therein is correlated with at least one of the other signal delays D Y therein such that cov(D X , D Y ) is nonzero, and
(4) one or more sets of correlated signal delays arise from global variations, the method comprising the steps of:
a. modeling, using a computer, each signal delay D by:
D
=
μ
D
+
∑
j
=
1
N
α
j
R
j
+
∑
i
=
1
M
β
i
G
i
+
∑
i
=
1
M
∑
k
=
1
M
Γ
i
,
k
G
i
G
k
wherein:
μD is a nominal value for D;
N is the number of signal delays in the circuit;
M is the number of global variations in the circuit;
α j is a node sensitivity coefficient reflecting the dependence of D on signal delay j in the circuit;
R j is a local variation reflecting the uncertainty in the value of D localized in the element;
G i and G k are each a global variation reflecting the uncertainty in the value of D, each such uncertainty being shared by the element and one or more other elements in the circuit;
β i is a global sensitivity coefficient reflecting the dependence of D on global variation G i in the circuit; and
Γ i, k is a global sensitivity coefficient reflecting the dependence of D on both of global variations G i and G k in the circuit;
b. subsequently propagating the modeled signal delays throughout at least one of the circuit paths.
12. The method of claim 11 wherein at least one of the global variations G varies in value between two locations A and B in the circuit such that cov(G A , G B ) decreases as the distance between locations A and B increases, wherein G A is the global variation at location A and G B is the global variation at location B.
13. The method of claim 11 wherein at least one of the global variations G varies in value between two locations A and B in the circuit such that cov(G A , G B ) decreases exponentially with the distance between locations A and B, wherein G A is the global variation at location A and G B is the global variation at location B.
14. The method of claim 11 wherein at least one of the global variations G varies in value between two locations A and B in the circuit such that:
cov
(
G
A
,
G
B
)
=
σ
G
2
exp
(
-
r
A
B
r
c
)
wherein
G A is the global variation at location A;
G B is the global variation at location B;
σ G is the standard deviation of the global variation G,
r AB is the distance between locations A and B; and
R c is a nonzero constant spatial correlation distance.
15. The method of claim 14 wherein:
a. the circuit is partitioned into an array of elements of at least substantially equal
b. r AB is the distance between elements A and B; and
c. r c is equal to the product of:
(1) the average size of the elements, and
(2) a user-defined resolution.
16. The method of claim 11 wherein the method further comprises the following steps at any path intersection at which at least two circuit paths intersect, with a first circuit path having a signal delay D 1 and a second circuit path having a signal delay D 2 :
a. evaluating the gaussianity of the function MAX(D 1 , D 2 );
b. if the gaussianity does not meet a threshold standard, storing signal delays D 1 and D 2 in a signal delay tuple Mt; and
c. propagating the signal delay tuple Mt to any downstream element or interconnect.
17. A method for predicting the signal delay in a circuit having circuit paths formed by elements connected by interconnects wherein:
(1) at least some of the circuit paths intersect,
(2) all elements and interconnects each:
(a) have an associated signal delay D, and
(b) have at least one of:
(i) an adjacent upstream element or interconnect from which a signal delay is propagated, and
(ii) an adjacent downstream element or interconnect to which the signal delay D is propagated;
(3) at least one set of correlated signal delays is present, wherein at least one of the signal delays D X therein is correlated with at least one of the other signal delays D Y therein such that cov(D X , D Y ) is nonzero, and
(4) one or more sets of correlated signal delays arise from global variations,
the method comprising the steps of:
a. modeling, using a computer, each signal delay D by a function dependent on
∑
i
=
1
M
∑
k
=
1
M
Γ
i
,
k
G
i
G
k
wherein:
M is the number of global variations in the circuit;
G i and G k are each a global variation reflecting the uncertainty in the value of D, each such uncertainty being shared by the element and one or more other elements in the circuit; and
Γ i, k is a global sensitivity coefficient reflecting the dependence of D on both of global variations G i and G k in the circuit;
b. subsequently propagating the modeled signal delays throughout at least one of the circuit paths.
18. The method of claim 17 wherein the function modeling each signal delay D is also dependent on:
∑
i
=
1
M
β
i
G
i
wherein β i is a global sensitivity coefficient reflecting the dependence of D on global variation G i in the circuit.
19. The method of claim 18 wherein the function modeling each signal delay D is also dependent on:
μ
D
+
∑
j
=
1
N
α
j
R
j
wherein: μ D is a nominal value for D;
N is the number of signal delays in the circuit
α j , is a node sensitivity coefficient reflecting the dependence of D on signal delay j in the circuit; and
R j is a local variation reflecting the uncertainty in the value of D localized in the element.
20. The method of claim 17 wherein the method further comprises the following steps at any path intersection at which at least two circuit paths intersect, with a first circuit path having a signal delay D 1 and a second circuit path having a signal delay D 2 :
a. evaluating the gaussianity of the function MAX(D 1 , D 2 );
b. if the gaussianity does not meet a threshold standard, storing signal delays D 1 and D 2 in a signal delay tuple Mt; and
c. propagating the signal delay tuple Mt to any downstream element or interconnect.