Copyright © 2008 The Institute of Electronics, Information and Communication Engineers
Special Section on Selected Papers from the 20th Workshop on Circuits and Systems in Karuizawa -- Papers |
An Evaluation Method of the Number of Monte Carlo STA Trials for Statistical Path Delay Analysis
1 The authors are with Integrated Research Institute, Tokyo Institute of Technology, Yokohama-shi, 226-8503 Japan. E-mail: imai{at}starc.or.jp, 2 The authors are with Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology, Yokohama-shi, 226-8503 Japan., 3 Presently, with Semiconductor Technology Academic Research Center.
We present an evaluation method for estimating the lower bound number of Monte Carlo STA trials required to obtain at least one sample which falls within top-k % of its parent population. The sample can be used to ensure that target designs are timing-error free with a predefined probability using the minimum computational cost. The lower bound number is represented as a closed-form formula which is general enough to be applied to other verifications. For validation, Monte Carlo STA was carried out on various benchmark data including ISCAS circuits. The minimum number of Monte Carlo runs determined using the proposed method successfully extracted one or more top-k % delay instances.
Key Words: SSTA, STA, Monte Carlo STA, timing analysis, ranking
Manuscript received June 26, 2007. Manuscript revised October 6, 2007.
Reference
[1] A. Srivastava, D. Sylvester, and D. Blaauw, Statistical Analysis and Optimization for VLSI: Timing and Power, Springer, 2005. [2] 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, March 1966. [3] A. Nadas, "Probabilistic PERT," IBM J. Res. Dev., vol.23, no.3, pp.339–347, May 1979. [4] J. Le, X. Li, and L.T. Pileggi, "STAC: Statistical timing analysis with correlation," Proc. DAC2004, pp.343–348, 2004. [5] C. Visweswariah, K. Ravindran, K. Kalafala, S.G. Walker, and S. Narayam, "First-order incremental block-based statistical timing analysis," Proc. DAC2004, pp.331–336, 2004. [6] L. Zhang, W. Chen, Y. Hu, J.A. Gubner, and C.C.-P. Chen, "Correlation-preserved non-Gaussian statistical timing analysis with quadratic timing model," Proc. DAC2005, pp.83–88, 2005. [7] L. Lee, L.-C. Wang, T.M. Mak, and K.-T. Cheng, "A path-based methodology for post-silicon timing validation," Proc. ICCAD 2004, pp.713–720, 2004. [8] P. Bremaud, An Introduction to Probabilistic Modeling, Springer, 2004. [9] K. Honma, T. Shibuya, I. Nitta, and H. Matsuoka, "A study of the execution path number and the accuracy of path-based statistical timing analysis," IEICE Technical Report, CPSY2005-74, 2005. [10] M. Orshansky and A. Bandyopadhyay, "Fast statistical timing analysis handling arbitrary delay correlations," Proc. DAC2004, pp.337–342, 2004. [11] J. Dambre, D. Stroobandt, and J. Van Campenhout, "A probabilistic approach to clock cycle prediction," Tau2002, pp.9–15, 2002. [12] X. Li, J. Le, M. Celik, and L.T. Pileggi, "Defining statistical sensitivity for timing optimization of logic circuits with large-scale process and environmental variations," ICCAD2005, pp.844–851, 2005. [13] A. Agarwal, V. Zolotov, and D.T. Blaauw, "Statistical timing analysis using bounds and selective enumeration," IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol.22, no.9, pp.1243–1260, Sept. 2003. [14] ISCAS benchmark circuits, available at http://www.fm.vslib.cz/~kes/asic/iscas/, Jan. 2007.
CiteULike 
Connotea 
Del.icio.us What's this?
This Article 
Abstract
Full Text (PDF)
Alert me when this article is cited
Alert me if a correction is posted
Services
Email this article to a friend
Similar articles in this journal
Alert me to new issues of the journal
Add to My Personal Archive
Download to citation manager
Request Permissions
Google Scholar
Articles by IMAI, M.
Articles by MASU, K.
Social Bookmarking
What's this?