Probabilistic interval-valued computation: toward a practical surrogate for statistics inside CAD tools

ABSTRACT

Interval methods offer a general, fine-grain strategy for modeling correlated range uncertainties in numerical algorithms. We present a new, improved interval algebra that extends the classical affine form to a more rigorous statistical foundation. Range uncertainties now take the form of confidence intervals. In place of pessimistic interval bounds, we minimize the probability of numerical "escape"; this can tighten interval bounds by 10X, while yielding 10-100X speedups over Monte Carlo. The formulation relies on three critical ideas: liberating the affine model from the assumption of symmetric intervals; a unifying optimization formulation; and a concrete probabilistic model. We refer to these as probabilistic intervals, for brevity. Our goal is to understand where we might use these as a surrogate for expensive, explicit statistical computations. Results from sparse matrices and graph delay algorithms demonstrate the utility of the approach, and the remaining challenges.

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: 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]
• 3: Murari Mani , Anirudh Devgan , Michael Orshansky, An efficient algorithm for statistical minimization of total power under timing yield constraints, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065661]
• 4: Xin Li , Jiayong Le , P. Gopalakrishnan , L. T. Pileggi, Asymptotic probability extraction for non-normal distributions of circuit performance, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.2-9, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382533]
• 5: R.E. Moore, Interval Analysis, Prentice-Hall, 1966.
• 6: L. H. de Figueiredo and J. Stolfi, "Self-validated numerical methods and applications", Brazilian Mathematics Colloqium monograph, IMPA, Rio de Janeiro, July 1997.
• 7: C.L. Harkness, et al, "Interval Methods for Modeling Uncertainty in RC Timing Analysis," Proc. ACM/IEEE ICCAD, Nov. 1992.
• 8: 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]
• 9: Claire Fang Fang , Rob A. Rutenbar , Markus Püschel , Tsuhan Chen, Toward efficient static analysis of finite-precision effects in DSP applications via affine arithmetic modeling, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775960]
• 10: 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]
• 11: James D. Ma , Rob A. Rutenbar, Fast interval-valued statistical interconnect modeling and reduction, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055170]
• 12: Claire Fang Fang , Rob A. Rutenbar, Probabilistic interval-valued computation: representing and reasoning about uncertainty in dsp and vlsi design, Carnegie Mellon University, Pittsburgh, PA, 2005
• 13: W. Feller, "An Introduction to Probability Theory and Its Applications", Vol. 2, 3rd ed., Wiley, New York, 1971
• 14: G. Marsaglia, "Ratio of Normal Variables and Ratios of Sums of Uniform Variables", J. of Amer. Stat. Assn., 60(309), Mar 1965
• 15: A. Singhee, et al, "Probabilistic Interval-Valued Computation: Toward a Practical Surrogate for Statistics Inside CAD Tools," CMU CSSI Technical Report manuscript, in progress.
• 16: Gregory Steele , David Overhauser , Steffen Rochel , Syed Zakir Hussain, Full-chip verification methods for DSM power distribution systems, Proceedings of the 35th annual conference on Design automation, p.744-749, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277231]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design

Keywords:
DFM, algorithms, intervals