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 an order of magnitude while yielding 10-100 times speedups over Monte Carlo. The formulation relies on the following 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.

We show how advances in the handling of correlated interval representations of range uncertainty can be used to approximate the mass of a probability density function as it moves through numerical operations and, in particular, to predict the impact of statistical manufacturing variations on linear interconnect. We represent correlated statistical variations in resistance-inductance-capacitance parameters as sets of correlated intervals and show how classical model-order reduction methods - asymptotic waveform evaluation and passive reduced-order interconnect macromodeling algorithm - can be retargeted to compute interval-valued, rather than scalar-valued, reductions. By applying a simple statistical interpretation and sampling to the resulting compact interval-valued model, we can efficiently estimate the impact of variations on the original circuit. Results show that the technique can predict mean delay and standard deviation with errors between 5% and 10% for correlated parameter variations up to 35%.

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.

Correlated interval representations of range uncertainty offer an attractive solution to approximating computations on statistical quantities. The key idea is to use finite intervals to approximate the essential mass of a probability density function (pdf) as it moves through numerical operators; the resulting compact interval-valued solution can be easily interpreted as a statistical distribution and efficiently sampled. This paper first describes improved interval-valued algorithms for asymptotic wave evaluation (AWE)/passive reduced-order interconnect macromodeling algorithm (PRIMA) model order reduction for tree-structured interconnect circuits with correlated resistance, inductance, and capacitance (RLC) parameter variations. By moving to a much faster interval-valued linear solver based on path-tracing ideas, and making more optimal tradeoffs between interval- and scalar-valued computations, the delay statistics roughly 10/spl times/ faster than classical Monte Carlo (MC) simulation, with accuracy to within 5% can be extracted. This improved interval analysis strategy is further applied in order to build statistical effective capacitance (C/sub eff/) models for variational interconnect, and show how to extract statistics of C/sub eff/ over 100/spl times/ faster than classical MC simulation, with errors less than 4%.

Technology-oriented tools provide the raw data needed to optimize the fabrication process itself, and to predict problematic variational impacts on silicon design. Unfortunately, even in these physics-oriented tools, statistically uncertain quantities appear as crucial inputs. To date, Monte Carlo techniques have been the dominant solution method. We suggest an alternative in which uncertainties are represented as correlated intervals, and interval-valued computations replace the standard scalar operations in the numerical algorithm for the tool. We use an oxide chemical-mechanical polishing tool as an example, and show how to "retrofit" workable statistical models on top of the original algorithm. Accuracies to within /spl sim/1-10% of Monte Carlo simulation, and speedups of /spl sim/10-100X can be achieved, depending on whether we choose a formulation which emphasizes accuracy, or efficiency.

We show how recent advances in the handling of correlated interval representations of range uncertainty can be used to predict the impact of statistical manufacturing variations on linear interconnect. We represent correlated statistical variations in RLC parameters as sets of correlated intervals, and show how classical model order reduction methods - AWE and PRIMA - can be re-targeted to compute interval-valued, rather than scalar-valued reductions. By applying a statistical interpretation and sampling to the resulting compact interval-valued model, we can efficiently estimate the impact of variations on the original circuit. Results show the technique can predict mean delay with errors between 5-10%, for correlated RLC parameter variations up to 35%.