Non-parametric statistical static timing analysis: an SSTA framework for arbitrary distribution

ABSTRACT

We present a new statistical STA framework based on Monte Carlo analysis that can deal with arbitrary statistical distribution and delay models. Order statistics (non-parametrics) is consistently adopted by which the timing analysis and criticality calculation become distribution-independent. To make Monte Carlo process computationally practical, delays are handled as vectors so that iterations are eliminated. The vector dimension or required number of Monte Carlo iterations which guarantees no timing violation at any user-specified probability is analytically determined. A path criticality metric using order statistics is also defined. Experimental results using various delay models show the validity and usefulness of our proposed algorithm.

REFERENCES

• 1: M. Pan, C. Chu, and H. Zhou, "Timing yield estimation using statistical static timing analysis," in Proc. ISCAS, No. 3, pp. 2461--2464, 2005.
• 2: A. Srivastava, D. Sylvester, and D. Blaauw, "Statistical analysis and optimization for VLSI: timing and power," Reading, Springer, 2005.
• 3: A. Nadas, "Probabilistic PERT," IBM J. Res. Dev., Vol. 23, No. 3, pp. 339--347, May 1979.
• 4: T. I. Kirkpatric and N. R. Clark, "PERT as an aid to logic design," IBM J. Res. Dev., Vol. 10, No. 2, pp. 135--141, 1966.
• 5: Jiayong Le , Xin Li , Lawrence T. Pileggi, STAC: statistical timing analysis with correlation, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996665]
• 6: C. Visweswariah , K. Ravindran , K. Kalafala , S. G. Walker , S. Narayan, First-order incremental block-based statistical timing analysis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996663]
• 7: Yaping Zhan , A. J. Strojwas , M. Sharma , D. Newmark, Statistical critical path analysis considering correlations, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.699-704, November 06-10, 2005, San Jose, CA
• 8: Lizheng Zhang , Weijen Chen , Yuhen Hu , John A. Gubner , Charlie Chung-Ping Chen, Correlation-preserved non-gaussian statistical timing analysis with quadratic timing model, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065606]
• 9: J. L. Wong, A. Davoodi, V. Khandelwal, A. Srivastava, and M. Potkonjak, "Statistical timing analysis using kernel smoothing," in Proc. ICCD, pp. 97--102, 2007.
• 10: Michael Orshansky , Arnab Bandyopadhyay, Fast statistical timing analysis handling arbitrary delay correlations, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996664]
• 11: A. Agarwal, V. Zolotov, and D. T. Blaauw, "Statistical timing analysis using bounds and selective enumeration," IEEE Trans. CAD, Vol. 22, No. 9, pp. 1243--1260, Sep. 2003.
• 12: M. Imai, T. Sato, N. Nakayama, and K. Masu, "An evaluation method for the number of Monte Carlo STA trials," IEICE Trans. Fundamentals, Vol. E91-A, No.4, Apr. 2008.
• 13: E. L. Lehmann, "NONPARAMETRICS, Statistical methods based on ranks," Reading, Holden-Day, 1975.
• 14: ISCAS benchmark circuits, http://www.fm.vslib.cz/~kes/asic/iscas/.

INDEX TERMS

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

General Terms:
Algorithms, Performance, Verification

Keywords:
Monte Carlo simulation, SSTA, STA, non parametrics, order statistics