A new statistical max operation for propagating skewness in statistical timing analysis

ABSTRACT

Statistical static timing analysis (SSTA) is emerging as a solution for predicting the timing characteristics of digital circuits under process variability. For computing the statistical max of two arrival time probability distributions, existing analytical SSTA approaches use the results given by Clark in [8]. These analytical results are exact when the two operand arrival time distributions have jointly Gaussian distributions. Due to the nonlinear max operation, arrival time distributions are typically skewed. Furthermore, nonlinear dependence of gate delays and non-gaussian process parameters also make the arrival time distributions asymmetric. Therefore, for computing the max accurately, a new approach is required that accounts for the inherent skewness in arrival time distributions. In this work, we present analytical solution for computing the statistical max operation.¹ First, the skewness in arrival time distribution is modeled by matching its first three moments to a so-called skewed normal distribution. Then by extending Clark's work to handle skewed normal distributions we derive analytical expressions for computing the moments of the max. We then show using initial simulations results that using a skewness based max operation has a significant potential to improve the accuracy of the statistical max operation in SSTA while retaining its computational efficiency.

REFERENCES

• 1: Aseem Agarwal, David Blaauw, and Vladimir Zolotov. Statistical timing analysis using bounds and selective enumeration. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 22(9):1243--1260, Sept 2003.
• 2: Aseem Agarwal , David Blaauw , Vladimir Zolotov , Savithri Sundareswaran , Min Zhao , Kaushik Gala , Rajendran Panda, Statistical delay computation considering spatial correlations, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119825]
• 3: MRCM Berkelaar. Statistical delay calculation, linear time method. In Workshop TAU, 1997.
• 4: Sarvesh Bhardwaj , Sarma B. K. Vrudhula , David Blaauw, "AU: Timing Analysis Under Uncertainty, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.615, November 09-13, 2003 [doi>10.1109/ICCAD.2003.1]
• 5: M. Cain. The moment-generating function of the minimum of bivariate normal random variables. 48(2):124--125, 1994.
• 6: 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]
• 7: Hongliang Chang , Vladimir Zolotov , Sambasivan Narayan , Chandu Visweswariah, Parameterized block-based statistical timing analysis with non-gaussian parameters, nonlinear delay functions, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065604]
• 8: C. E. Clark. The greatest of a finite set of random variables. 9:85--91, 1961.
• 9: Anirudh Devgan , Chandramouli Kashyap, Block-based Static Timing Analysis with Uncertainty, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.607, November 09-13, 2003 [doi>10.1109/ICCAD.2003.41]
• 10: C. Fernandez and M. F. J. Steel. On bayesian modelling of fat tails and skewness. pages 359--371, 1998.
• 11: O. Kella. On the distribution of the maximum of bivariate normal random variables with general means and variances. 15(11):3265--3276, 1986.
• 12: Vishal Khandelwal , Ankur Srivastava, A general framework for accurate statistical timing analysis considering correlations, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065607]
• 13: Jing-Jia Liou , Angela Krstic , Li-C. Wang , Kwang-Ting Cheng, False-path-aware statistical timing analysis and efficient path selection for delay testing and timing validation, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514061]
• 14: Michael Orshansky , Kurt Keutzer, A general probabilistic framework for worst case timing analysis, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514059]
• 15: D. B. Owen. Tables for computing bivariate normal probabilities. 27:1075--1090, 1956.
• 16: Mike Patefield. Fast and accurate calculation of Owen's T function. Statistical Software, 5(5):1--25, 2000.
• 17: 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]
• 18: 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]
• 19: 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]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Switching theory
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

General Terms:
Design, Performance