Transcript Y - Institut

Algorithm for Fast Statistical Timing Analysis
Jakob Salzmann, Frank Sill, Dirk Timmermann
SOC 2007,
Nov ‘07, Tampere, Finland
Institute of Applied Microelectronics and
Computer Engineering
University of
Rostock
Outline
Motivation
Static Timing Analysis
Statistical Timing Analysis
Simulation Results
Conclusion & Outlook
2
Motivation(1)
Progressive transistor scaling leads to higher impact of parameter
variations
Physical on-chip variations due to
Imprecise fabrication process
Gate oxide thickness
Transistor width, length
Doping
Environment
Ambient temperature
Cooling
Time
Electro migration
Mechanical stress
Thermal stress
3
Motivation(2)
Parameter variations lead to unpredictable timing behavior
I1
I2
Y
I1
I2
Time
Delay
Y
I1
I2
Y
?
Delay ?
Time
Chips compete against each other
Before market entry, knowledge about maximum speed in the worst case
Step forward: Information on speed distribution of a chip production set
Most chips are faster than worst case speed!
4
Static Timing Analysis
Classic Approach: Worst case analysis
Estimate margins of all parameters
Find parameter set which results in worst case delay
Simulate gate delay with worst case inputs
Add delays of each data path to get resulting delay of the
circuit
I1
I2
Y
Time
Worst case
delay
No realistic representation of timing behavior
Overstated circuit delay
5
Statistical Timing Analysis(1)
μ – mean value
σ – standard deviation
Innovative Approach
μ
Estimate margins and Gaussian distribution of all possible
parameters
Monte-Carlo simulations to get delay probabilities
Estimate Probability Density Function (PDF) of gate delay
σ
Calculate PDF of overall delay
PDF:
f ( x) 
1
 * 2
e
1 x 
 

2  
2
More realistic representation of timing behavior
Prediction how many circuits match
estimated delay
6
Statistical Timing Analysis(2)
Single input switching (SIS)
Simple mathematical approach
µY = µ1 + µ2, σY² = σ1² + σ2²
Correlations between gates
Not within scope of this
presentation
Multi input switching (MIS)
Former
Our
newapproach
approach[Aga04]
Lot ofone
simulation
setsset
perper
gate
Only
simulation
gate
Imprecise
calculationofof standard
No
underestimation
deviation deviation
standard
#Simulation
sets ~to#input²
Simple
extension
gates with
High calculation
effort
more
than 2 inputs
Low calculation effort
7
Statistical Timing Analysis(3)
Multi input switching – Simulation
Theses:
Resulting mean value depends on
Difference between Input Mean Values [ps]
Gate PDF
Input PDF
Order and time differences of inputs
µY increases in case of proximate inputs with high standard deviations
µG increases by proximate inputs
Resulting standard deviation depends on dominating input
8
Statistical Timing Analysis(4)
Approach to calculate proximate effect and dominating input
Separate behavior of gate into impact of Inputs and Gate itself
“Resulting Input PDF“ by convolution of all Input-PDFs
Addition of “Resulting Input PDF“ and ”Gate PDF” by Single Input Switching algorithm
I
I
σY² = σI² + σG²
µY = µI + µG
9
Statistical Timing Analysis(4)
Approach for Resulting „Input PDF“ by convolution of all Input-PDFs
Integration of all „Input PDF“ to obtain their Cumulative Density Function (CDF)
Approximation of all „Input CDF“ by a set of linear equations
Multiply the edges of the „Input CDFs“ approximations to get a “Resulting Input CDF“
Mean value by intersection with probability 0.5
Standard deviation by root-mean-square
deviation of the points of the “Resulting Input
CDF” from mean value
10
Simulation Results(1)
Algorithm must not underestimate gate delay!
Calculated mean value ≥ Simulated mean value
Calculated standard deviation ≥ Simulated standard deviation
NAND2 - Gate
Three example cases
Case1:
Case2:
Case3:
σA
σA
σA
= 5ps,
= 20ps,
= 40ps,
σB = 10ps
σB = 40ps
σB = 80ps
HSpice
Approximation
11
Simulation Results(2)
Tree structure – worst case of switching behavior
I1
I2
I3
...
Different input
switching cases
0→1
Y
...
I31
I32
Case1
Case 2
Case 3
Simulation
time
HSpice
simulation
μ 1052 ps
975 ps
1001 ps
20 min
σ
35 ps
38 ps
Presented
algorithm
μ 1082 ps 1039 ps
42 ps
42 ps
Former
Approach
(Agarwal)
μ 1044 ps 969 ps
989 ps
Static worst
case timing
analysis
μ 1295 ps 1295 ps
σ
σ
σ
32 ps
33 ps
27 ps
-
27 ps
-
1039 ps
75 ms
1.4 s
27 ps
1295 ps
60ms
-
12
Conclusion & Outlook
Goal: Developing algorithm for calculating statistical timing behavior
of a Multi Input Gate
Only one simulation set per gate
No underestimation of gate delay
Simple extension to gates with more than 2 inputs
Low calculation effort
Automatic tool for calculating statistical timing behavior of larger (and
real) circuits
13
Questions?
Thank you for your attention!
References
[AGA04]
A. Agarwal, F. Dartu, and D. Blaauw; Statistical Gate Delay Model
Considering Multiple Input Switching, 41st Design Automation
Conference, USA, 2004
14