Efficient statistical timing analysis of circuits

• US 7,350,171 B2
• Filed: 11/17/2005
• Issued: 03/25/2008
• 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: Hu, YuHen, Zhang, Lizheng, Chen, Chun-ping
• Primary Examiner(s): Kik; Phallaka
• Application Number:
  US11/282,003
• Publication Number:
  US 20070113211A1
• Time in Patent Office: 859 Days
• Field of Search: 716/6, 703/2, 703/16
• 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 a 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 delay Y therein such that covariance cov(X, Y) is nonzero,

(4) one or more sets of correlated signal delays arises 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 a mean of a distribution defining X;

N is a number of signal delays in the circuit;

M is a number of global variations in the circuit;

R_i and G_j are each Gaussian random variables;

α

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

β

_X,j is a global sensitivity reflecting a 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:

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

d. 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 a 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 a step of representing the signal delay at a path intersection by an output of a function wherein:

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

b. a 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 a 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 a step of representing the signal delay at a path intersection by an output of a function wherein:

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

b. 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 a 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 covariance 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 a step of representing the signal delay at a path intersection by an output of a function wherein:

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

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

c. the output at least approximates a 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 a step of representing the signal delay at a path intersection by an output of a function wherein:

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

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

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

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

15. The method of claim 8 wherein each signal delay is represented in a 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 a mean of a distribution defining X;

N is a number of signal delays in the circuit;

M is a number of global variations in the circuit;

R_i and G_j are each Gaussian random variables;

α

_X,i is a node sensitivity reflecting a 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 steps of:

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

d. reassigning different values to α

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

17. A method for predicting a 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) an output of the function is at least substantially equivalent to a maximum of the signal delays of the intersecting circuit paths if 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 a 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 cumulative signal delays of all prior elements and interconnects along the path.

19. The method of claim 17 further comprising a 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 covariance cov(X′

, Y′

)=0.

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

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

22. The method of claim 17 wherein each signal delay is represented in a 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 a mean of a distribution defining X;

N is a number of signal delays in the circuit;

M is a number of global variations in the circuit;

R_i and G_j are each Gaussian random variables;

α

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

β

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

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

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

d. reassigning different values to α

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

24. A method for predicting a 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 other signal delay,

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 cumulative signal delays of all prior elements and interconnects along the path; and

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

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

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

(3) the output approximates a 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 a 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, equivalent uncorrelated signal delays X′

+W and Y′

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

, Y′

)=0.

27. The method of claim 24 wherein at least some of the signal delays are each represented in a 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 a mean of a distribution defining X;

N is a number of signal delays in the circuit;

M is a number of global variations in the circuit;

R_i and G_j are each Gaussian random variables;

α

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

β

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

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

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

e. reassigning different values to α

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