Statistical timing based on incomplete probabilistic descriptions of parameter uncertainty

ABSTRACT

Existing approaches to timing analysis under uncertainty are based on restrictive assumptions. Statistical STA techniques assume that the full probabilistic distribution of parameter uncertainty is available; in reality, the complete probabilistic description often cannot be obtained. In this paper, a new paradigm for parameter uncertainty description is proposed as a way to consistently and rigorously handle partially available descriptions of parameter uncertainty. The paradigm is based on a theory of interval probabilistic models that permit handling uncertainty that is described in a distribution-free mode - just via the range, the mean, and the variance. This permits effectively handling multiple real-life challenges, including imprecise and limited information about the distributions of process parameters, parameters coming from different populations, and the sources of uncertainty that are too difficult to handle via full probabilistic measures (e.g. on-chip supply voltage variation). Specifically, analytical techniques for bounding the distributions of probabilistic interval variables are proposed. Besides, a provably correct strategy for fast Monte Carlo simulation based on probabilistic interval variables is introduced. A path-based timing algorithm implementing the novel modeling paradigm, as well as handling the traditional variability descriptions, has been developed. The results indicate the proposed algorithm can improve the upper bound of the 90th-percentile circuit delay, on average, by 5.3% across the ISCAS'85 benchmark circuits, compared to the worst-case timing estimates that use only the interval information of the partially specified parameters.

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: 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, San Diego, California, USA [doi>10.1145/1065579.1065605]
• 4: 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, San Diego, California, USA [doi>10.1145/1065579.1065604]
• 5: 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, San Diego, California, USA [doi>10.1145/1065579.1065606]
• 6: J. D. Ma , R. A. Rutenbar, Interval-valued reduced order statistical interconnect modeling, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.460-467, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382621]
• 7: Andreas Lemke , Lars Hedrich , Erich Barke, Analog circuit sizing based on formal methods using affine arithmetic, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.486-489, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774643]
• 8: Dan Ernst , Shidhartha Das , Seokwoo Lee , David Blaauw , Todd Austin , Trevor Mudge , Nam Sung Kim , Krisztian Flautner, Razor: Circuit-Level Correction of Timing Errors for Low-Power Operation, IEEE Micro, v.24 n.6, p.10-20, November 2004 [doi>10.1109/MM.2004.85]
• 9: D. Kouroussis , I. A. Ferzli , F. N. Najm, Incremental partitioning-based vectorless power grid verification, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.358-364, November 06-10, 2005, San Jose, CA
• 10: V. P. Kouznetsov, Interval Statistical Models, Radio i Svyaz, Moscow, 1991 (In Russian).
• 11: R. E. Moore, Interval Analysis, Prentice-Hall, 1966.
• 12: J. Stolfi and L.H. de Figueiredo, "An introduction to affine arithmetic," TEMA Tend. Mat. Apl. Computing, 4, No. 3 (2003), 297--312.
• 13: W. Feller, An Introduction to Probability Theory and Its Applications, Wiley and Sons, 3rd Edition, 1968.
• 14: H. Godwin, Inequalities on Distribution Functions, Hafner, 1964.
• 15: S. Ferson et al, "Constructing probability boxes and Dempster-Shafer structures," Sandia Report, 2002.
• 16: S. Ferson, RAMAS Risk Calc 4.0 Software: Risk Assessment with Uncertain Numbers, CRC Press, 2002.
• 17: Scott Ferson , Lev Ginzburg , Vladik Kreinovich , Luc Longpré , Monica Aviles, Computing variance for interval data is NP-hard, ACM SIGACT News, v.33 n.2, June 2002 [doi>10.1145/564585.564604]
• 18: A. Agarwal et al, "Path-based statistical timing analysis considering inter- and intra-die correlations," TAU, 2002.
• 19: Michael Orshansky , Arnab Bandyopadhyay, Fast statistical timing analysis handling arbitrary delay correlations, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996664]
• 20: A. Nadas, "Probabilistic PERT," IBM. J. Res. Develop., vol. 23, no. 3, May 1979.
• 21: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 22: Michael Orshansky , Wei-Shen Wang , Martine Ceberio , Gang Xiang, Interval-based robust statistical techniques for non-negative convex functions, with application to timing analysis of computer chips, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France [doi>10.1145/1141277.1141664]
• 23: G. Fishman, Monte Carlo: Concepts, Algorithms, and Applications, Springer-Verlag, 1995.
• 24: Robert B. Hitchcock, Sr., Timing Verification and the Timing Analysis program, Proceedings of the 19th conference on Design automation, p.594-604, January 1982
• 25: H.-F. Jyu et al, "Statistical timing analysis of combinational logic circuits," Trans. on VLSI Systems, vol.1, (no.2), pp. 126--37, 1993.
• 26: J. Rice, Mathematical Statistics and Data Analysis, Wadsworth & Brooks, 1988.
• 27: Y. Cao et al, "New paradigm of predictive MOSFET and interconnect modeling for early circuit design," Proc. of CICC, pp. 201--204, 2000.
• 28: PTM: http://www.eas.asu.edu/~ptm.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Algorithms, Design, Performance, Reliability