An efficient method for statistical circuit simulation

ABSTRACT

The dynamic behavior of a VLSI circuit can be described by a system of differential-algebraic equations. When some circuit elements are affected by process variations, the dynamic behavior of the circuit will deviate from its nominal trajectory. Monte-Carlo-type random sampling methods are widely used to estimate the trajectory deviation. However they can be quite time-consuming when the dimension of the parameter space is large. This paper offers an alternative solution by casting the problem into the theoretic frame work of non-linear non-Gaussian filtering. To estimate the mean and variance of the time-dependent circuit trajectory, we develop a method based on unscented transformation, which is an efficient Bayesian analysis sampling technique. Theoretically the method has linear runtime complexity. Experimental results show that compared to traditional Monte-Carlo methods, the new method can achieve over 10x speedup with less than 2% error.

REFERENCES

• 1: K. Agarwal, F. Liu, C. McDowell, et al. A test structure for characterizing local device mismatches. In Proceedings of 2006 Symposium on VLSI circuits, July 2006.
• 2: 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]
• 3: Min Chen , Wei Zhao , Frank Liu , Yu Cao, Fast statistical circuit analysis with finite-point based transistor model, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 4: L. Daldoss, P. Gubian, and M. Quarantelli. Multiparameter time-domain sensitivity computation. IEEE Transactions on VLSI Systems, 48:1296--1307, Nov. 1999.
• 5: G. Evensen. Sequential data assimilation with nonlinear quasi-geostrophic model using monte carlo methods to forecast error statistics. Journal of Geophysical Research, 9, May 1994.
• 6: C. William Gear, Numerical Initial Value Problems in Ordinary Differential Equations, Prentice Hall PTR, Upper Saddle River, NJ, 1971
• 7: A. H. Jazwinski. Stochastic process and filtering theory. Academic Press, New York and London, 1970.
• 8: S. Julier and J. K. Uhlmann. A general method for approximating nonlinear transformations of probability distributions. Available online http://citeseer.ist.psu.edu/julier96general.html, 1996.
• 9: S. Julier and J. K. Uhlmann. A new extension of the Kalman Filter to nonlinear systems. Available online http://citeseer.ist.psu.edu/julier97new.html, 1997.
• 10: R. E. Kalman. A new approach to linear filtering and prediction problems. Transaction of the ASME, Journal of Basic Engineering, 82, Mar. 1960.
• 11: Rouwaida Kanj , Rajiv Joshi , Sani Nassif, Mixture importance sampling and its application to the analysis of SRAM designs in the presence of rare failure events, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1146930]
• 12: P. E. Kloeden and E. Platen. Numerical solution of stochastic differential equations. Springer-Verlag, 1992.
• 13: L. T. Pang and B. Nikolic. Impact of layout on 90nm cmos process parameter flucturations. In Proceedings of 2006 Symposium on VLSI circuits, July 2006.
• 14: C. Visweswariah, K. Ravinder, et al. First-order incremental block-based statistical timing analysis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25:2170--2180, Oct. 2006.
• 15: S. F. Wojtkiewicz and L. A. Bergman. Numerical solution of high dimensional Fokker-Planck equations. In The 8th ASCE specialty conference on probablistic mechanics and structural reliability, July 2000.
• 16: Yaping Zhan , Andrzej J. Strojwas , Xin Li , Lawrence T. Pileggi , David Newmark , Mahesh Sharma, Correlation-aware statistical timing analysis with non-gaussian delay distributions, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065605]