Interval-based robust statistical techniques for non-negative convex functions, with application to timing analysis of computer chips

ABSTRACT

In chip design, one of the main objectives is to decrease its clock cycle. On the design stage, this time is usually estimated by using worst-case (interval) techniques, in which we only use the bounds on the parameters that lead to delays. This analysis does not take into account that the probability of the worst-case values is usually very small; thus, the resulting estimates are over-conservative, leading to unnecessary over-design and under-performance of circuits. If we knew the exact probability distributions of the corresponding parameters, then we could use Monte-Carlo simulations (or the corresponding analytical techniques) to get the desired estimates. In practice, however, we only have partial information about the corresponding distributions, and we want to produce estimates that are valid for all distributions which are consistent with this information.In this paper, we develop a general technique that allows us, in particular, to provide such estimates for the clock time.

REFERENCES

• 1: D. Berleant, M.-P. Cheong, C. Chu, Y. Guan, A. Kamal, G. Sheblé, S. Ferson, and J. F. Peters, Dependable handling of uncertainty, Reliable Computing 9(6) (2003), pp. 407--418.
• 2: D. Berleant, L. Xie, and J. Zhang, Statool: a tool for Distribution Envelope Determination (DEnv), an interval-based algorithm for arithmetic on random variables, Reliable Computing 9(2) (2003), pp. 91--108.
• 3: D. Berleant and J. Zhang, Using Pearson correlation to improve envelopes around the distributions of functions, Reliable Computing, 10(2) (2004), pp. 139--161.
• 4: D. Berleant and J. Zhang, Representation and Problem Solving with the Distribution Envelope Determination (DEnv) Method, Reliability Engineering and System Safety, 85 (1--3) (July-Sept. 2004).
• 5: D. Berleant and J. Zhang, Using Pearson correlation to improve envelopes around the distributions of functions, Reliable Computing, 10(2) (2004), pp. 139--161.
• 6: D. Boning and S. Nassif, "Models of process variations in device and interconnect", in: A. Chandrakasan (ed.), Design of High-Performance Microcomputer Ciucruits, 2000.
• 7: D. G. Chinnery , K. Keutzer, Closing the gap between ASIC and custom: an ASIC perspective, Proceedings of the 37th conference on Design automation, p.637-642, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337602]
• 8: D. Chinnery and K. Keutzer (eds.), Closing the Gap Between ASICs and Custom, Kluwer, 2002.
• 9: R. E. Edwards, Functional analysis: theory and applications, Dover Publ., N.Y., 1995.
• 10: S. Ferson, RAMAS Risk Calc 4.0: Risk Assessment with Uncertain Numbers, CRC Press, Boca Raton, Florida, 2002.
• 11: S. Ferson, L. Ginzburg, V. Kreinovich, and J. Lopez, "Absolute Bounds on the Mean of Sum, Product, etc.: A Probabilistic Extension of Interval Arithmetic", Extended Abstracts of the 2002 SIAM Workshop on Validated Computing, Toronto, Canada, May 23--25, 2002, pp. 70--72.
• 12: J. Galambos, The Asymptotic Theory of Extreme Order Statistics, Wiley, New York, 1987.
• 13: P. J. Huber, Robust statistics, Wiley, New York, 2004.
• 14: L. Jaulin, M. Kieffer, O. Didrit, and E. Walter, Applied interval analysis: with examples in parameter and state estimation, robust control and robotics, Springer-Verlag, London, 2001.
• 15: S. Kotz and S. Nadarajah, Extreme Value Distributions: Theory and Applications, Imperial College Press, London, UK, 2000.
• 16: V. Kreinovich and S. Ferson, "Computing best-possible bounds for the distribution of a sum of several variables is NP-hard", International Journal of Approximate Reasoning, to appear.
• 17: V. Kreinovich, S. Ferson, and L. Ginzburg, "Exact Upper Bound on the Mean of the Product of Many Random Variables With Known Expectations", Reliable Computing, 9(6) (2003), pp. 441--463.
• 18: V. Kreinovich and L. Longpré, "Computational complexity and feasibility of data processing and interval computations, with extension to cases when we have partial information about probabilities", In: V. Brattka, M. Schroeder, K. Weihrauch, and N. Zhong, Proceedings of the Conference on Computability and Complexity in Analysis CCA '2003, Cincinnati, Ohio, USA, August 28--30, 2003, pp. 19--54.
• 19: V. Kreinovich, G. N. Solopchenko, S. Ferson, L. Ginzburg, and R. Aló, "Probabilities, intervals, what next? Extension of interval computations to situations with partial information about probabilities", Proceedings of the 10th IMEKO TC7 International Symposium on Advances of Measurement Science, St. Petersburg, Russia, June 30-July 2, 2004, Vol. 1, pp. 137--142.
• 20: A. T. Langewisch and F. F. Choobineh, "Mean and variance bounds and propagation for ill-specified random variables", IEEE Transactions on Systems, Man, and Cybernetics, Part A, 34(4) (2004), pp. 494--506.
• 21: M. Orshansky, "Increasing circuit performance through statistical design techniques", in: D. Chinnery and K. Keutzer (eds.), Closing the Gap Between ASICs and Custom, Kluwer, 2002.
• 22: 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]
• 23: 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]
• 24: Kurt Keutzer , Michael Orshansky, From blind certainty to informed uncertainty, Proceedings of the 8th ACM/IEEE international workshop on Timing issues in the specification and synthesis of digital systems, December 02-03, 2002, Monterey, California, USA [doi>10.1145/589411.589419]
• 25: S. Rajasekaran, P. Pardalos, J. Reif, and J. Rolim (eds.), Handbook on Randomized Computing, Kluwer, 2001.
• 26: R. Trejo and V. Kreinovich, "Error Estimations for Indirect Measurements: Randomized vs. Deterministic Algorithms For 'Black-Box' Programs", In: S. Rajasekaran, P. Pardalos, J. Reif, and J. Rolim (eds.), Handbook on Randomized Computing, Kluwer, 2001, pp. 673--729.
• 27: H. M. Wadsworth Jr., Handbook of statistical methods for engineers and scientists, McGraw-Hill, N.Y., 1990.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
  B.8 Performance and Reliability
      B.8.0 General
  B.m MISCELLANEOUS
      Subjects: Design management

General Terms:
Design, Performance