Tech Report CS-89-38

Modeling Uncertainty in RC Timing Analysis

Cheryl L. Harkness and Daniel P. Lopresti

September 1989

Abstract:

Even subtle disturbances in the manufacturing process used to fabricate a chip introduce variations in the values of circuit parameters (e.g., capacitances, resistances, transistor sizes). Although expected values can be obtained for all such parameters, the true values are likely to differ from those stated. Given the range of possible values for each input parameter, our goal is to determine bounds on the resulting timing behavior produced by these variations.

We propose representing uncertain parameters as intervals and present a theoretical framework based on interval algebra for manipulating these ranges. To illustrate this methodology, we modify an existing RC analysis algorithms (Crystal's PR-Slope model) to create one which computes worst-case delay bounds when given uncertain input parameters. We provide proofs of correctness for our approach and test its performance. Analysis shows that our algorithm is much more efficient than Monte Carlo simulation and produces bounds with similar accuracy.

(complete text in pdf)