Efficient statistical timing analysis of circuits

• US 20070113211A1
• Filed: 11/17/2005
• Published: 05/17/2007
• Est. Priority Date: 11/17/2005
• Status: Active Grant

• Current Assignee: Chun-Ping Chen, Lizheng Zhang, Yuhen Hu
• Original Assignee: Chun-Ping Chen, Lizheng Zhang, Yuhen Hu
• Inventors: Zhang, Lizheng, Chen, Chun-ping, Hu, YuHen
• Granted Patent: US 7,350,171 B2
• Time in Patent Office: Days
• US Class Current: 716/108
• CPC Class Codes: G06F 30/3312 Timing analysis

Abstract

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 extended canonical timing model is used to represent each delay element along a circuit path, wherein the model bears information regarding any correlations that each element has to any other elements in the circuit (and/or to any external global factors, e.g., global temperature variations over the circuit, etc.). The model can be represented in a vectorized format which allows enhancement of computational efficiency, wherein the coefficients of the vectors allow an objective measure of element correlation (and wherein the vectors can be “pruned” by dropping insignificant coefficients to further enhance computational efficiency). A decomposition procedure can be used to decompose correlated elements into uncorrelated elements to allow delays to me more easily propagated through the timing diagram representing the circuit. Finally, a bounded approximation for the output of the MAX operator is described which provides a safely conservative approximation regardless of the linearity of the MAX output.

Claims

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) each element and interconnect have an associated signal delay,

(3) at least one set of correlated signal delays is present, wherein at least one of the signal delays X therein is correlated with at least one of the other signal delays Y therein such that cov(X, Y) is nonzero,

(4) one or more sets of correlated signal delays may arise from global correlation, wherein the signal delays therein are all dependent on global variations;

the method comprising the steps of;

a. modeling each signal delay X by;

$X={\mathrm{\mu <br><br>}}_X+\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_{X,i}<br><br>R_i+\underset{j=1}{\overset{M}{\sum <br><br>}}<br><br>{\mathrm{\beta <br><br>}}_{X,j}<br><br>G_j$

wherein;

μ

_X is the mean of a distribution defining X;

N is the number of signal delays in the circuit;

M is the number of global variations in the circuit;

R_i and G_j are each Gaussian random variables;

α

_X,i is a node sensitivity reflecting the dependence of X on signal delay i in the circuit;

β

_Xj is a global sensitivity reflecting the dependence of X on global variation j in the circuit; and

b. subsequently propagating the modeled signal delays throughout at least one of the circuit paths.

2. The method of claim 1 further comprising the steps of:

a. modeling at least a portion of each signal delay as a vector, and

b. reassigning zero values to α

_X,i which have values below a predetermined drop threshold, thereby simplifying the vector.

3. The method of claim 1 wherein α

_X,i which have values below a predetermined drop threshold are assigned different values.

4. The method of claim 1 further comprising the step of substituting, for each pair of signal delays X and Y which are correlated such that cov(X, Y) is nonzero, equivalent uncorrelated signal delays

X′

+W=X and
Y′

+W=Y,

wherein W is such that cov(X′

, Y′

)=0.

5. The method of claim 1 wherein the step of propagating the signal delays throughout at least one of the circuit paths includes the step of representing the signal delay at a path intersection by the output of a function wherein:

a. the function is dependent on the signal delays of the intersecting circuit paths;

b. the distribution of the output is Gaussian if the distribution of the signal delays of the intersecting circuit paths are Gaussian; and

c. the output approximates the maximum of the signal delays of the intersecting circuit paths.

6. The method of claim 5 wherein the function is linearly dependent on the signal delays of the intersecting circuit paths.

7. The method of claim 1 wherein the step of propagating the signal delays throughout at least one of the circuit paths includes the step of representing the signal delay at a path intersection by the output of a function wherein:

a. the output of the function at least closely approximates Z=MAX(X,Y) if the skewness of Z is below a predetermined threshold; and

a. the output of the function is equal to an upper bound set in excess of Z=MAX(X,Y) if the skewness of Z is above the predetermined threshold.

8. 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) each element and interconnect have an associated signal delay, and

(3) at least one of the signal delays X is correlated with at least one of the other signal delays Y such that cov(X, Y) is nonzero,

the method comprising;

a. for each pair of signal delays X and Y which are correlated, substituting equivalent uncorrelated signal delays

X′

+W=X and
Y′

+W=Y,

 

wherein W is such that cov(X′

, Y′

)=0;

b. subsequently propagating the signal delays throughout at least one of the circuit paths.

9. The method of claim 8 wherein the step of propagating the signal delays throughout at least one of the circuit paths includes the step of representing the signal delay at a path intersection by the output of a function wherein:

a. the function is dependent on the signal delays of the intersecting circuit paths;

b. the distribution of the output is Gaussian if the distribution of the signal delays of the intersecting circuit paths are Gaussian; and

c. the output at least approximates the maximum of the signal delays of the intersecting circuit paths.

10. The method of claim 9 wherein the function is linearly dependent on the signal delays of the intersecting circuit paths.

11. The method of claim 9 wherein the output is equal to an upper bound set in excess of the maximum of the signal delays of the intersecting circuit paths if the maximum of the signal delays is significantly non-Gaussian.

12. The method of claim 8 wherein the step of propagating the signal delays throughout at least one of the circuit paths includes the step of representing the signal delay at a path intersection by the output of a function wherein:

a. the function is linearly dependent on the signal delays of the intersecting circuit paths;

b. the output approximates the maximum of the signal delays of the intersecting circuit paths.

13. The method of claim 8 further comprising the step of propagating the signal delays throughout all of the circuit paths.

14. The method of claim 13 further comprising the step of identifying the circuit path with the longest signal delay.

15. The method of claim 8 wherein each signal delay is represented in the form:

$X={\mathrm{\mu <br><br>}}_X+\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_{X,i}<br><br>R_i+\underset{j=1}{\overset{M}{\sum <br><br>}}<br><br>{\mathrm{\beta <br><br>}}_{X,j}<br><br>G_j$

wherein;

μ

_X is the mean of a distribution defining X;

N is the number of signal delays in the circuit;

M is the number of global variations in the circuit;

R_i and G_j are each Gaussian random variables;

α

_X,i is a node sensitivity reflecting the dependence of X on signal delay i in the circuit;

β

_Xj is a global sensitivity reflecting the dependence of X on global variation j in the circuit.

16. The method of claim 15 further comprising the steps of:

a. modeling at least a portion of each signal delay as a vector, and

b. reassigning different values to α

_X,i which have values below a predetermined drop threshold.

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) each element and interconnect have an associated signal delay, and

(3) at least one of the signal delays is correlated with at least one of the other signal delays,

the method comprising;

a. defining a function representing the signal delay at a path intersection wherein;

(1) the function is linearly dependent on the signal delays of the intersecting circuit paths; and

(2) the output of the function is at least substantially equivalent to the maximum of the signal delays of the intersecting circuit paths if the variances of the signal delays of the intersecting circuit paths are substantially similar; and

(3) the output of the function is at least substantially equivalent to an upper bound in excess of the maximum of the signal delays of the intersecting circuit paths if the variances of the signal delays of the intersecting circuit paths are substantially different;

b. determining the output of the function for at least one of the path intersections in the circuit, thereby defining the signal delay for the path intersection.

18. The method of claim 17 further comprising the step of defining the signal delay for at least one portion of a circuit path prior to a path intersection, this signal delay being defined by the cumulative signal delays of all prior elements and interconnects along the path.

19. The method of claim 17 further comprising the step of substituting, for each pair of correlated signal delays X and Y, equivalent uncorrelated signal delays:

X′

+W=X and
Y′

+W=Y,

wherein W is such that cov(X′

, Y′

)=0.

20. The method of claim 17 further comprising the step of propagating the signal delays throughout all of the circuit paths.

21. The method of claim 20 further comprising the step of identifying the circuit path with the longest signal delay.

22. The method of claim 17 wherein each signal delay is represented in the form:

$X={\mathrm{\mu <br><br>}}_X+\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_{X,i}<br><br>R_i+\underset{j=1}{\overset{M}{\sum <br><br>}}<br><br>{\mathrm{\beta <br><br>}}_{X,j}<br><br>G_j$

wherein;

μ

_X is the mean of a distribution defining X;

N is the number of signal delays in the circuit;

M is the number of global variations in the circuit;

R_i and G_j are each Gaussian random variables;

α

_X,i is a node sensitivity reflecting the dependence of X on signal delay i in the circuit;

β

_Xj is a global sensitivity reflecting the dependence of X on global variation j in the circuit.

23. The method of claim 22 further comprising the steps of:

a. modeling at least a portion of each signal delay as a vector, and

b. reassigning different values to α

_X,i which have values below a predetermined drop threshold.

24. 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) each element and interconnect have an associated signal delay, and

(3) at least one of the signal delays is correlated with at least one of the other signal delays,

the method comprising;

a. decomposing at least some of the correlated signal delays into an equivalent collection of uncorrelated signal delays;

b. representing the signal delay at any portion of a circuit path prior to a path intersection by the cumulative signal delays of all prior elements and interconnects along the path; and

c. representing the signal delay at a path intersection by the output of a function wherein;

(1) the function is dependent on the signal delays of the intersecting circuit paths;

(2) the distribution of the output is Gaussian if the distribution of the signal delays of the intersecting circuit paths are Gaussian; and

(3) the output approximates the maximum of the signal delays of the intersecting circuit paths.

25. The method of claim 24 wherein the function is linearly dependent on the signal delays of the intersecting circuit paths.

26. The method of claim 24 wherein the step of decomposing at least some of the correlated signal delays into an equivalent collection of uncorrelated signal delays includes the step of substituting, for each pair of correlated signal delays X and Y, the equivalent uncorrelated signal delays X′

+W and Y′

+W, wherein W is such that cov(X′

, Y′

)=0.

27. The method of claim 24 wherein at least some of the signal delays are each represented in the form:

$X={\mathrm{\mu <br><br>}}_X+\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>{\mathrm{\alpha <br><br>}}_{X,i}<br><br>R_i+\underset{j=1}{\overset{M}{\sum <br><br>}}<br><br>{\mathrm{\beta <br><br>}}_{X,j}<br><br>G_j$

wherein;

μ

_X is the mean of a distribution defining X;

N is the number of signal delays in the circuit;

M is the number of global variations in the circuit;

R_i and G_j are each Gaussian random variables;

α

_X,i is a node sensitivity reflecting the dependence of X on signal delay i in the circuit;

β

_Xj is a global sensitivity reflecting the dependence of X on global variation j in the circuit.

28. The method of claim 27 further comprising the steps of:

a. constructing vectors representing at least some of the signal delays; and

b. reassigning different values to α

_X,i which have values below a predetermined drop threshold.