On efficient Monte Carlo-based statistical static timing analysis of digital circuits

ABSTRACT

The Monte-Carlo (MC) technique is a well-known solution for statistical analysis. In contrast to probabilistic (non-Monte Carlo) Statistical Static Timing Analysis (SSTA) techniques, which are typically derived from simple statistical or timing models, the MC-based SSTA technique encompasses complicated timing and process variation models. However, a precise analysis that involves a traditional MC-based technique requires many timing simulation runs (1000s). In this paper, the behavior of the critical delay of digital circuits is investigated by using a Legendre polynomial-based ANOVA decomposition. The analysis verifies that the variance of the critical delay is mainly due to the pairwise interactions among the Principal Components (PCs) of the process parameters. Based on this fact, recent progress on the MC-based SSTA, through Latin Hypercube Sampling (LHS), is also studied. It is shown that this technique is prone to inefficient critical delay variance and quantile estimating. Inspired by the decomposition observations, an efficient algorithm is proposed which produces optimally low L₂-discrepancy Quasi-MC (QMC) samples which significantly improve the precision of critical delay statistical estimations, compared with that of the MC, LHS, and traditional QMC techniques.

REFERENCES

• 1: D. Blaauw et. al., "Statistical timing analysis: from basic principles to state-of-the-art," IEEE Trans. Computer-Aided Design, vol. 27, pp. 589--607, Apr. 2008.
• 2: L. Scheffer, "The count of Monte Carlo," ACM/IEEE TAU, 2004.
• 3: V. Veetil et. al., "Criticality aware Latin Hypercube Sampling for efficient statistical timing analysis," ACM/IEEE TAU, personal communication.
• 4: Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 5: S. M. Ross, Simulation. 4th edition, Academic Press, 2006.
• 6: M. D. McKay , R. J. Beckman , W. J. Conover, A comparison of three methods for selecting values of input variables in the analysis of output from a computer code, Technometrics, v.42 n.1, p.55-61, Feb. 2000 [doi>10.2307/1271432]
• 7: J. F. Traub , A. G. Werschulz, Complexity and information, Cambridge University Press, New York, NY, 1999
• 8: Paul Bratley , Bennett L. Fox, Algorithm 659: Implementing Sobol's quasirandom sequence generator, ACM Transactions on Mathematical Software (TOMS), v.14 n.1, p.88-100, March 1988 [doi>10.1145/42288.214372]
• 9: J. H. Halton, "On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals," Numer. Math., 2, pp. 84--90, 1960.
• 10: Bennett L. Fox, Algorithm 647: Implementation and Relative Efficiency of Quasirandom Sequence Generators, ACM Transactions on Mathematical Software (TOMS), v.12 n.4, p.362-376, Dec. 1986 [doi>10.1145/22721.356187]
• 11: H. Niederreiter and C. Xing, "Low-discrepancy sequences and global function fields with many rational places," Finite Fields and Their Applications, vol. 2, pp. 241--273, 1996.
• 12: T. T. Warnock, "Computational investigations of low-discrepancy point sets II," in Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, Springer, pp. 354--361, 1995.
• 13: Ian H. Sloan , Henryk Woźniakowski, When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?, Journal of Complexity, v.14 n.1, p.1-33, March 1998 [doi>10.1006/jcom.1997.0463]
• 14: A. Papageorgiou, Sufficient conditions for fast quasi-Monte Carlo convergence, Journal of Complexity, v.19 n.3, p.332-351, June 2003 [doi>10.1016/S0885-064X(02)00004-3]
• 15: R. Caflisch et. al., "Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension," J. Comp. Finance, vol. 1, pp. 27--46, 1997.
• 16: Xiaoqun Wang , Ian H. Sloan, Why Are High-Dimensional Finance Problems Often of Low Effective Dimension?, SIAM Journal on Scientific Computing, v.27 n.1, p.159-183, 2005 [doi>10.1137/S1064827503429429]
• 17: Xiaoqun Wang , Kai-Tai Fang, The effective dimension and quasi-Monte Carlo integration, Journal of Complexity, v.19 n.2, p.101-124, April 2003 [doi>10.1016/S0885-064X(03)00003-7]
• 18: C. LeMieux and A. Owen, "Quasi-regression and the relative importance of the ANOVA components of a function," in Monte Carlo and Quasi-Monte Carlo Methods, Springer, pp. 331--344, 2002.
• 19: A. Jian and A. Owen, "Quasi-regression," Journal of Complexity, vol. 17, pp. 588--607, 2001.
• 20: H. Chang and S. Sapatnekar, "Statistical timing analysis under spatial correlations," IEEE Trans. Computer-Aided Design, vol. 24, pp. 1467--1482, Sept. 2005.
• 21: William J. Morokoff , Russel E. Caflisch, Quasi-random sequences and their discrepancies, SIAM Journal on Scientific Computing, v.15 n.6, p.1251-1279, Nov. 1994 [doi>10.1137/0915077]
• 22: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 23: P. Jaeckel, Monte Carlo methods in finance. Wiley, 2002.
• 24: I. M. Sobol, "Uniformly distributed sequences with an additional uniform property," U.S.S.R. Computational Math. and Math. Phys. 16, pp. 236--242, 1976.
• 25: Stephen Joe , Frances Y. Kuo, Remark on algorithm 659: Implementing Sobol's quasirandom sequence generator, ACM Transactions on Mathematical Software (TOMS), v.29 n.1, p.49-57, March 2003 [doi>10.1145/641876.641879]
• 26: Jian Cheng , Marek J. Druzdzel, Computational Investigation of Low-Discrepancy Sequences in Simulation Algorithms for Bayesian Networks, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.72-81, June 30-July 03, 2000
• 27: S. Heinrich, Efficient algorithms for computing the L2-discrepancy, Mathematics of Computation, v.65 n.216, p.1621-1633, Oct. 1996 [doi>10.1090/S0025-5718-96-00756-9]
• 28: "Capo: A large-scale fixed-die placer from UCLA," Available at: http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/Placement.
• 29: Hee Sun Hong , Fred J. Hickernell, Algorithm 823: Implementing scrambled digital sequences, ACM Transactions on Mathematical Software (TOMS), v.29 n.2, p.95-109, June 2003 [doi>10.1145/779359.779360]