Tech Report CS-90-15
An Approach to Uncertainty in VLSI Design
Cheryl Lynn Harkness
Computer-aided design (CAD) tools take a circuit description and analyze the design to predict circuit behavior. Although these descriptions take many forms ranging from behavioral specifications to mask layouts, all of them contain bits of quantitative information about the circuit (e.g. physical dimensions, logic values, threshold voltages, parasitic capacitances). Often the precise values of these circuit characteristics cannot be determined before the layout is completed and/or the chip is fabricated. Even though the exact values are not known, estimates in the form of bounds, probability distributions, or average values can be obtained for these uncertain circuit parameters. Most current CAD tools employ only `expected' values in their calculations, returning one of several possible outcomes. A fundamental issue is how the circuit will behave with other combinations of possible values.
In this thesis, we present a general framework based on interval algebra for modeling uncertainty in VLSI. Our approach is to represent uncertain parameters as bounding intervals and to develop algebras for manipulating these ranges. We explore applications for this framework in several areas of VLSI design, including switch-level simulation, timing analysis, and placement. For each area, we create an application-specific interval algebra and incorporate this algebra within an existing algorithm for solving the problem. The result is a new interval version of the algorithm that uses the full range of values for each uncertain parameter in its computations and returns all possible solutions.
The different applications reveal the strengths and the weaknesses of the interval paradigm. Among its many advantages are its versatility, simplicity, and speed. Its main liability is that it may produce over-conservative bounds for some applications. For these cases, we provide alternative interval-based techniques that improve the bounds but require more computation time.
(complete text in pdf)