Parameterized Timing Analysis with General Delay Models and Arbitrary Variation Sources Khaled R. Heloue and Farid N. Najm University of Toronto {khaled, najm}@eecg.utoronto.ca
Problem Timing verification is a crucial step - More pronounced in current technologies
Types of variations - Process variations are random statistical variations
- Environmental variations are uncertain variations that are non-statistical
… cause circuit delay variations! Parameterized Timing Analysis (PTA) - Delay is “parameterized” as a function of variations
- Propagated in the timing graph to determine arrival times
- Circuit delay becomes parameterized
- Useful information: sensitivities, margins, distributions, yield
Previous Work Statistical Static Timing Analysis (SSTA) - One type of PTA
- Parameters are random variables with known distributions
- Different delay models
- Different correlation models
- Grid/Quad-tree, Principal Component Analysis (PCA)
Limitations: - Can not handle uncertain variables, i.e. non statistical variables
- Some have difficulty in handling the Max operation efficiently
- In nonlinear/non-Gaussian case
Previous Work Multi-Corner Static Timing Analysis (MCSTA) - Is another type of PTA
- Get a conservative bound on maximum (worst case) corner delay
- Delay is parameterized using affine (linear) functions
- Parameters can be random variables and/or uncertain variables
Limitations - Linear delay models
- Does not follow well the spread of the circuit delay
- Accuracy guaranteed only at the maximum corner delay
- Sensitivities are not captured well
Our Approach Propose a Parameterized Timing Analysis technique - Random parameters with arbitrary distributions
- Uncertain non-statistical parameters
- General class of delay models
- Linear in circuit size (for linear and quadratic models)
- Using guaranteed upper/lower bounds
- Using an approximation that minimizes the square of the error
- Both methods preserve the nonlinearities of the delay model
Propose two applications: - MCSTA with linear/nonlinear models
- SSTA with nonlinear models, random & uncertain variables
General Delay Models To represent timing quantities, we will use a general class of delay models F This class of nonlinear functions F has the following three properties: - F is closed under linear (and/or affine) operations
- All functions in F are bounded
- All functions in F can be maximized and minimized efficiently
General Delay Models – Cont’d Property 1 Property 2 Property 3 - Guarantees overall efficiency of approach
Propagation To propagate arrival times in the timing graph - SUM operation
- MAX operation
SUM can be performed MAX is nonlinear - Bound the MAX using functions in F
- Approximate the MAX using functions in F
MAX Operation Let C = max(A,B) be the maximum of A and B and assume that A, B belong to F - C does not necessarily belong to F
We want to find
MAX Linear or Nonlinear?? The nonlinearity of the MAX depends on the difference D, between A and B Note that and that MAX is linear when - Dmin ≥ 0 that is A dominates B C = A
- Dmax ≤ 0 that is B dominates A C = B
MAX is nonlinear when Dmax ≥ 0 and Dmin ≤ 0
Bounding the MAX C = B + max(D,0) and Dmax ≥ 0, Dmin ≤ 0 Let Y = max(D,0) - Y does not belong to F since MAX is nonlinear
MAX Upper Bound Yu is the best ceiling on Y and is exact at the extremes Since Yu is a linear function of D, then
MAX Upper Bound – Cont’d Since C = B + Y, then Where
MAX Lower Bound
MAX Lower Bound – Cont’d
MAX Approximation
MAX Approximation – Cont’d Take the partial derivatives with respect to and - Set them to zero and solve for the variables
- Simple expressions in Dmax and Dmin
Summary Given a general class of nonlinear functions F with certain properties Then propagation (SUM & MAX) can be done while maintaining the same delay model The MAX is “linearized” - Coefficients are simple functions of Dmin and Dmax
- Independent of whether variables are random or uncertain
- Distribution independent
Application 1 Traditional STA Multi-corner STA - Parameterize delay as a function of process/environmental parameters
- Propagate once to get the maximum delay (also parameterized)
- Determine the maximum/minimum corner delays efficiently
Apply our framework to MCSTA with linear/quadratic models
Linear/quadratic models Timing quantities are expressed as follows: Show that all properties hold - Linear/quadratic models survive linear (affine) operations
- Bounded since -1 ≤ Xi ≤ 1
- Maximized efficiently (show in paper how this is done)
Results 90nm library and following process parameters: Characterized library to get delay sensitivities Used ISCAS’85 circuits - Maximum delay at the maximum/minimum corners are computed using exhaustive STA
- Maximum/minimum corner delays are determined using our approach (Bounds and LS-approximation)
Average errors:
Application 2 SSTA with quadratic delay models - random parameters with arbitrary distributions (Gaussian, uniform, triangular, etc…)
- uncertain non-random parameters varying in specified ranges
Delay model:
The Three properties… Surviving addition: Bounded & can be maximized and minimized - The maximum and minimum of a quadratic function depends on whether the vertex is within the range or not (explained in the paper)
Results In addition to Xr we use four global variables Xi - Truncated Gaussian, Uniform, and Triangular
- 10%-20% deviation in nominal delay
Compared our LS approach to Monte Carlo - Metrics: 95%-tile, 99%-tile, σ/μ
Avg error very small < 1%
CDF Comparison
Conclusion Proposed the first Parameterized Timing Analysis technique - Random parameters with arbitrary distributions
- Gaussian, uniform, triangular, etc…
- Uncertain non-statistical parameters
- General delay models (some restrictions)
- Simple and accurate technique
Applied our framework to - Multi-corner STA with linear and quadratic models
- Nonlinear (quadratic) SSTA with arbitrary distributions
Dostları ilə paylaş: |