Efficient Monte Carlo based incremental statistical timing analysis

ABSTRACT

Modeling and accuracy difficulties exist with traditional SSTA analysis and optimization methods. In this paper we describe methods to improve the efficiency of Monte Carlo-based statistical static timing analysis. We propose a Stratification + Hybrid Quasi Monte Carlo (SH-QMC) approach to reduce the number of samples required for Monte Carlo based SSTA. Our simulations on benchmark circuits up to 90K gates show that the proposed method requires 23.8X fewer samples on average to achieve comparable accuracy in timing estimation as a random sampling approach. Results on benchmark circuits also show that when SH-QMC is performed with multiple parallel threads on a quad core processor, the approach is faster than traditional SSTA with comparable accuracy. SH-QMC scales better than traditional SSTA with circuit size. We also propose an incremental approach to recompute a percentile delay metric after ECO. The results show that on average only 1.4% and 0.7% of original samples need to be evaluated for exact recomputation of the 95^th percentile and 99^th percentile delays, after sample size reduction using SH-QMC.

REFERENCES

• 1: 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]
• 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: K. Chopra , S. Shah , A. Srivastava , D. Blaauw , D. Sylvester, Parametric yield maximization using gate sizing based on efficient statistical power and delay gradient computation, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.1023-1028, November 06-10, 2005, San Jose, CA
• 4: Farid N. Najm , Noel Menezes, Statistical timing analysis based on a timing yield model, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996696]
• 5: L. Scheffer, "The Count of Monte Carlo," TAU, 2004.
• 6: M. Keramat and R. Kielbasa, "Worst Case Efficiency of LHSMC Yield Estimator of Electrical Circuits." Proc. ISCAS, v. 3, pp. 1660--1663, 1997.
• 7: 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]
• 8: S. Tasiran and A. Demir, "Smart Monte Carlo for Yield Estimation," TAU, 2006.
• 9: Amith Singhee , Rob A. Rutenbar, From Finance to Flip Flops: A Study of Fast Quasi-Monte Carlo Methods from Computational Finance Applied to Statistical Circuit Analysis, Proceedings of the 8th International Symposium on Quality Electronic Design, p.685-692, March 26-28, 2007 [doi>10.1109/ISQED.2007.79]
• 10: E. Hlawka, "Funktionen von beschrankter Variation in der Theorie der Gleich-verteilung", Ann. Mat. Pura Appl., 54, pp 325--333., 1961.
• 11: Reuven Y. Rubinstein, Simulation and the Monte Carlo Method, John Wiley & Sons, Inc., New York, NY, 1981
• 12: I. M. Sobol, "The Distribution of Points in a Cube and the Approximate Evaluation of Integrals", USSR Comp. Math and Math. Phys., 7(4), pp. 86--112, 1967.
• 13: 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]
• 14: Michael Stein, Large sample properties of simulations using latin hypercube sampling, Technometrics, v.29 n.2, p.143-151, May 1, 1987 [doi>10.2307/1269769]
• 15: F. Brglez and H. Fujiwara, "Neutral netlist of ten combinational benchmark circuits and a target translator in FORTRAN", Special session on ATPG and fault simulations, Proc. ISCAS, pp. 695--698, 1985.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Verification

Keywords:
Monte Carlo, statistical timing, variance reduction