Fast statistical timing analysis handling arbitrary delay correlations

ABSTRACT

An efficient statistical timing analysis algorithm that can handle arbitrary (spatial and structural) causes of delay correlation is described. The algorithm derives the entire cumulative distribution function of the circuit delay using a new mathematical formulation. Spatial as well as structural correlations between gate and wire delays can be taken into account. The algorithm can handle node delays described by non-Gaussian distributions. Because the analytical computation of an exact cumulative distribution function for a probabilistic graph with arbitrary distributions is infeasible, we find tight upper and lower bounds on the true cumulative distribution. An efficient algorithm to compute the bounds is based on a PERT-like single traversal of the sub-graph containing the set of N deterministically longest paths. The efficiency and accuracy of the algorithm is demonstrated on a set of ISCAS'85 benchmarks. Across all the benchmarks, the average rms error between the exact distribution and lower bound is 0.7%, and the average maximum error at 95th percentile is 0.6%. The computation of bounds for the largest benchmark takes 39 seconds.

REFERENCES

• 1: Robert B. Hitchcock, Sr., Timing Verification and the Timing Analysis program, Proceedings of the 19th conference on Design automation, p.594-604, January 1982
• 2: H.-F. Jyu et al, "Statistical timing analysis of combinational logic circuits," Trans. on VLSI Systems, vol.1, (no.2), pp. 126--37, 1993.
• 3: M. Berkelaar, "Statistical Delay Calculation", International Workshop on Logic Synthesis, pp. 15--24, 1997.
• 4: Timing Yield Estimation from Static Timing Analysis, Proceedings of the 2nd International Symposium on Quality Electronic Design, p.437, March 26-28, 2001
• 5: Michael Orshansky , Kurt Keutzer, A general probabilistic framework for worst case timing analysis, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514059]
• 6: Aseem Agarwal , David Blaauw , Vladimir Zolotov , Sarma Vrudhula, Computation and Refinement of Statistical Bounds on Circuit Delay, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775922]
• 7: A. Agarwal et al, "Path-Based Statistical Timing Analysis Considering Inter- and Intra-Die Correlations," TAU, pp. 16--21, 2002.
• 8: J. A. G. Jess , K. Kalafala , S. R. Naidu , R. H. J. M. Otten , C. Visweswariah, Statistical timing for parametric yield prediction of digital integrated circuits, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.776066]
• 9: Hongliang Chang , Sachin S. Sapatnekar, Statistical Timing Analysis Considering Spatial Correlations using a Single Pert-Like Traversal, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.621, November 09-13, 2003 [doi>10.1109/ICCAD.2003.129]
• 10: Anirudh Devgan , Chandramouli Kashyap, Block-based Static Timing Analysis with Uncertainty, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.607, November 09-13, 2003 [doi>10.1109/ICCAD.2003.41]
• 11: A. Nadas, "Probabilistic PERT," IBM J. of Research and Development, vol. 23, no. 3, pp. 339--347, 1979.
• 12: W. Feller, An Introduction to Probability Theory and Its Applications, Wiley and Sons, 3rd Edition, 1968.
• 13: Y. L. Tong, Probability Inequalities in Multivariate Distributions, Academic Press, 1980.
• 14: A. W. Marshall, I. Olkin, Inequalities: Theory of Majorization and Its Applications, Academic Press, 1979.
• 15: S. Louhichi, "Rates of Convergence in the CLT for Some Weakly Dependent Random Variables," Theory Probab. Appl. Vol. 46, No. 2.
• 16: S. Nassif, "Delay Variability: Sources, Impact and Trends," Proc. of International Solid-State Circuits Conference, 2000.
• 17: S. H. Yen , D. H. Du , S. Ghanta, Efficient algorithms for extracting the K most critical paths in timing analysis, Proceedings of the 26th ACM/IEEE conference on Design automation, p.649-654, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74497]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Algorithms, Performance, Reliability

Keywords:
Algorithms, performance, reliability