Statistical iterative timing analysis of circuits having latches and/or feedback loops
Statistical timing analysis methods for circuits having latches and feedback loops are described wherein the circuit yield, and/or the critical cycle mean (the largest cycle mean among all loops in the circuit), may be iteratively calculated with high speed and accuracy, thereby allowing their ready usage in the analysis and validation of proposed circuit designs.
1. A method for predicting performance criteria in a circuit having latches and feedback loops, the method comprising the iterative repetition of the following steps in an electronic processor:
a. for each latch i having one or more input latches j,
(1) first calculating for each input latch j:
(a) the earliest signal arrival time a i at latch i as the lesser of:
(i) any previously defined value for the earliest signal arrival time a i , and
(ii) the sum of
1) the earliest signal departure time d j at latch j in any prior iteration and
2) the minimum combinational delay δ ji from latch j to latch i;
(b) the latest signal arrival time A i at latch i as the greater of:
(i) any previously defined value for the latest signal arrival time A i , and
(ii) the sum of:
1) the latest signal departure time D j at latch j in any prior iteration and
2) the maximum combinational delay Δ ji from latch j to latch i;
(c) the cumulative delay P i at latch i as the greater of:
(i) any previously defined value for the cumulative delay P i , and
(ii) the sum of
1) the cumulative delay P j at latch j in any prior iteration and
2)the maximum combinational delay Δ ji from latch j to latch i;
(2) then calculating:
(a) the setup time violation s i at latch i as the latest signal arrival time A i:
(i) minus the rising clock edge arrival time C i ,
(ii) minus the clock high time T i h at latch i, plus the setup time S i of latch i;
(b) the hold time violation h i at latch i as the earliest signal arrival time a i :
(i) minus the rising clock edge arrival time C i ;
(ii) minus the clock high time T i h at latch i;
(iii) minus the hold time H i of latch i;
(iv) plus the clock cycle time T c;
(c) the critical setup time violation limit s c ∞ as the greater of:
(i) any previously defined value for the critical setup time violation limit s c ∞ , and
(ii) the setup time violation s i at latch i;
(d) the critical hold time violation limit h c ∞ as the lesser of:
(i) any previously defined value for the critical hold time violation limit h c ∞ , and
(ii) the hold time violation h i at latch i;
(e) the critical iteration mean O c as the greater of:
(i) any previously defined value for the critical iteration mean O c , and
(ii) the ratio of:
1) the cumulative delay P i at latch i, and
2) the number of iterations thus far performed plus 1;
b. calculating the circuit timing yield Y within the electronic processor as the probability that both
(1) the critical setup time violation limit s c ∞ being less than or equal to zero, and
(2) the critical hold time violation limit h c ∞ being greater than or equal to zero.
2. The method of claim 1 further comprising the following steps in the electronic processor:
a. during each iterative repetition, calculating at least one of:
(1) the average critical iteration mean μ O as the mean of the critical iteration means O c calculated in all iterations thus far performed;
(2) the standard deviation of the critical iteration mean σ O as the standard deviation of the critical iteration means O c calculated in all iterations thus far performed;
b. ceasing the iterative repetition when the change in the standard deviation of the critical iteration mean σ O between iterations is less than a threshold amount.
3. A method for predicting performance criteria in a circuit having latches and feedback loops, the method comprising the iterative repetition of the following steps within an electronic processor for each latch i:
a. where latch i has one or more input latches j, calculating the cumulative delay P i at latch i for each input latch j, the cumulative delay P i being the greater of:
(1) any previously defined value for the cumulative delay P i ,and
(2) the sum of
(a) the cumulative delay P j at latch j in any prior iteration and
(b) the maximum combinational delay Δ ji from latch j to latch i;
b. calculating the critical iteration mean O c within the electronic processor as the greater of:
(1) any previously defined value for the critical iteration mean O c , and
(2) the ratio of:
(a) the cumulative delay P i at latch i, and
(b) the number of iterations thus far performed, plus 1.
4. The method of claim 3 further comprising the following steps within the electronic processor:
a. during each iterative repetition, calculating the average critical iteration mean μ O as the mean of the critical iteration means O c calculated in all iterations thus far performed;
b. ceasing the iterative repetition when the change in the average critical iteration mean μ O between iterations is less than a threshold amount.
5. The method of claim 3 further comprising the following steps within the electronic processor:
a. during each iterative repetition, calculating the standard deviation of the critical iteration mean σ O as the standard deviation of the critical iteration means O c calculated in all iterations thus far performed;
b. ceasing the iterative repetition when the change in the standard deviation of the critical iteration mean σ O between iterations is less than a threshold amount.
6. The method of claim 3 further comprising the following steps within the electronic processor:
a. providing a circuit model representing a proposed circuit design;
b. calculating the critical iteration mean O c for the circuit model; and
c. revising the circuit model in response to the calculated critical iteration mean O c .
7. The method of claim 3 further comprising the following steps within the electronic processor:
a. iteratively repeating the following steps for each latch i having one or more input latches j,
(1) first calculating for each input latch j:
(a) the earliest signal arrival time a i at latch i as the lesser of:
(i) any previously defined value for the earliest signal arrival time a i ,and
(ii) the sum of
1) the earliest signal departure time d j at latch j in any prior iteration and
2) the minimum combinational delay δ ji from latch j to latch i;
(b) the latest signal arrival time A i at latch i as the greater of:
(i) any previously defined value for the latest signal arrival time A i ,and
(ii) the sum of:
1) the latest signal departure time D j at latch j in any prior iteration and
2) the maximum combinational delay Δ ji from latch j to latch i;
(2) then calculating:
(a) the earliest signal departure time d i at latch i as the greater of
(i) the rising clock edge arrival time C i at latch i, and
(ii) the earliest signal arrival time a i at latch i, minus the clock cycle time;
(b) the latest signal departure time D i at latch i as the greater of
(i) the rising clock edge arrival time C i at latch i, and
(ii) the latest signal arrival time A i at latch i, minus the clock cycle time;
(c) the setup time violation s i at latch i as the latest signal arrival time A i:
(i) minus the rising clock edge arrival time C i,
(ii) minus the clock high time T i h at latch i, plus the setup time S i of latch i;
(d) the hold time violation h i at latch i as the earliest signal arrival time a i :
(i) minus the rising clock edge arrival time C i ;
(ii) minus the clock high time T i h at latch i;
(iii) minus the hold time H i of latch i;
(iv) plus the clock cycle time T c;
(e) the critical setup time violation limit s c ∞ as the greater of:
(i) any previously defined value for the critical setup time violation limit s c ∞ , and
(ii) the setup time violation s i at latch i;
(f) the critical hold time violation limit h c ∞ as the lesser of:
(i) any previously defined value for the critical hold time violation limit h c ∞ , and
(ii) the hold time violation h i at latch i;
b. calculating the circuit timing yield Y as the probability that both
(1) the critical setup time violation limit s c ∞ is less than or equal to zero, and
(2) the critical hold time violation limit h c ∞ is greater than or equal to zero.
8. A method for predicting performance criteria in a circuit having latches and feedback loops, the method comprising the iterative repetition of the following steps within an electronic processor:
a. for each latch i having one or more input latches j,
(1) first calculating for each input latch j:
(a) the earliest signal arrival time a i at latch i as the lesser of:
(i) any previously defined value for the earliest signal arrival time a i ,and
(ii) the sum of
1) the earliest signal departure time d j at latch j in any prior iteration and
2) the minimum combinational delay δ ji from latch j to latch i;
(b) the latest signal arrival time A i at latch i as the greater of:
(i) any previously defined value for the latest signal arrival time A i ,and
(ii) the sum of:
1) the latest signal departure time D j at latch j in any prior iteration and
2) the maximum combinational delay Δ ji from latch j to latch i;
(c) the cumulative delay P i at latch i as the greater of:
(i) any previously defined value for the cumulative delay P i ,and
(ii) the sum of
1) the cumulative delay P j at latch j in any prior iteration and
2) the maximum combinational delay Δ ji from latch j to latch i;
(2) then calculating:
(a) the earliest signal departure time d i at latch i as the greater of
(i) the rising clock edge arrival time C i at latch i, and
(ii) the earliest signal arrival time a i at latch i, minus the clock cycle time;
(b) the latest signal departure time D i at latch i as the greater of
(i) the rising clock edge arrival time C i at latch i, and
(ii) the latest signal arrival time A i at latch i, minus the clock cycle time;
(c) the setup time violation s i at latch i as the latest signal arrival time A i:
(i) minus the rising clock edge arrival time C i,
(ii) minus the clock high time T i h at latch i, plus the setup time S i of latch i;
(d) the hold time violation h i at latch i as the earliest signal arrival time a i :
(i)minus the rising clock edge arrival time C i ;
(ii) minus the clock high time T i h at latch i;
(iii) minus the hold time H i of latch i;
(iv) plus the clock cycle time T c;
(e) the critical setup time violation limit s c ∞ as the greater of:
(i) any previously defined value for the critical setup time violation limit s c ∞ , and
(ii) the setup time violation s i at latch i;
(f) the critical hold time violation limit h c ∞ as the lesser of:
(i) any previously defined value for the critical hold time violation limit h c ∞ , and
(ii) the hold time violation h i at latch i;
b. calculating the circuit timing yield Y within the electronic processor as the probability that both
(1) the critical setup time violation limit s c 28 is less than or equal to zero, and
(2) the critical hold time violation limit h c 28 is greater than or equal to zero;
c. calculating the critical iteration mean O c , as the greater of:
(1) any previously defined value for the critical iteration mean O c , and
(2) the ratio of:
(a) the cumulative delay P i at latch i, and
(b) the number of iterations performed, plus 1.
9. The method of claim 8 further comprising the step of ceasing repetition when successive calculations of the circuit timing yield Y change by less than a threshold value between iterations.
10. The method of claim 8 further comprising the following steps within the electronic processor:
a. during each iterative repetition, calculating at least one of:
(1) the average critical iteration mean μ O as the mean of the critical iteration means O c calculated in all iterations performed;
(2) the standard deviation of the critical iteration mean σ O as the standard deviation of the critical iteration means O c calculated in all iterations performed;
b. ceasing the iterative repetition when the change in the standard deviation of the critical iteration mean σ O between iterations is less than a threshold amount.
11. The method of claim 8 further comprising the step of calculating within the electronic processor, during each iteration and for each latch i, the earliest signal departure time d i , at latch i as the greater of
a. the rising clock edge arrival time C i at latch i, and
b. the earliest signal arrival time a i at latch i, minus the clock cycle time.
12. The method of claim 8 further comprising the step of calculating within the electronic processor, during each iteration and for each latch i, the latest signal departure time D i at latch i as the greater of
a. the rising clock edge arrival time C i at latch i, and
b. the latest signal arrival time A i at latch i, minus the clock cycle time.
13. The method of claim 8 further comprising the following steps within the electronic processor:
a. during each iterative repetition, calculating the average critical iteration mean μ O as the mean of the critical iteration means O c calculated in all iterations performed;
b. ceasing the iterative repetition when the change in the average critical iteration mean μ O between iterations is less than a threshold amount.
14. The method of claim 8 further comprising the following steps within the electronic processor:
a. during each iterative repetition, calculating the standard deviation of the critical iteration mean σ O as the standard deviation of the critical iteration means O c calculated in all iterations performed;
b. ceasing the iterative repetition when the change in the standard deviation of the critical iteration mean σ O between iterations is less than a threshold amount.
15. The method of claim 8 further comprising the following steps within the electronic processor:
a. providing a circuit model representing a proposed circuit design;
b. calculating the circuit timing yield Y and the critical iteration mean O c for the circuit model; and
c. revising the circuit model in response to at least one of the calculated circuit timing yield Y and the critical iteration mean O c .