Transcript X - Computer Science and Engineering

Forward Discrete Probability Propagation for Device
Performance Characterization
under
Process Variations
Rasit Onur Topaloglu and Alex Orailoglu
{rtopalog|alex}@cse.ucsd.edu
University of California, San Diego
Computer Science and Engineering Department
9500 Gilman Dr., La Jolla, CA, 92093
1
Outline
Forward Discrete Probability Propagation
Motivation and Comparison with Monte Carlo
Probability Discretization Theory
Q, F, B, R and Q-1 Operators
Experimental Results
Conclusions
2
Motivation
•Process variations have become dominant even at the device
level in deep sub-micron technologies
•To reduce design iterations, there is a need to accurately
estimate the effects of process variations on device
performance
•Current tools/methods not quite suitable for this problem
due to accuracy & speed bottlenecks
•Most simulators use SPICE formulas
3
SPICE Formula Hierarchy
tox
0
Weff
Leff
T
NSUB
F
Cox
k
Qdep
Level2
Vth
Level3
Level4
rout
ex: gm=2*k*ID
Level0
 Level1
ID
gm
ms
Level5
•SPICE formulas are hierarchical; hence can tie physical parameters to
circuit parameters
•A hierarchical tree representation possible : connectivity graphs 4
Process Variation Model
•Recent models attribute process variations to physical
parameters
•Physical parameters correspond to the lowest level in
connectivity graphs
•Probability density functions (pdf’s), acquired through a
test chip, can be independently input to the lowest
level nodes
5
Probability Propagation
•Estimation of device parameters at highest level needed to
examine effects of process variations
•An analytic solution not possible since functions highly nonlinear and Gaussian approximations not accurate in
deep sub-micron
•A method to propagate pdf’s to highest level necessary
GOALS
Algebraic tractability : enabling manual applicability
Speed : be comparable or outperform Monte Carlo
Flexibility : be able to use non-standard densities
6
Monte Carlo for Probability
Propagation
W
L
VFB
NSUB
Cox
Vth
k
ID
gm
n
tox
Level0
Level1
Level2
Level3
Level4
•Pick independent samples from distributions of Level0 parameters
•Compute functions using these samples until highest level reached
•Iterate by repeating the preceding 2 steps
7
•Construct a histogram to approximate the distribution
Shortcomings of Monte Carlo
•Not manually applicable due to large number of iterations and
random sampling
•Limited to standard distributions : Random number generators
in CAD tools only provide certain distributions
•Accuracy : May miss points that are less likely to occur due to
random sampling; a large number of iterations necessary
which is quite costly for simulators
8
Implementing FDPP
Analytic operation on continuous distributions difficult; instead
work in discrete domain and convert back at the end:
•Q (Quantize) : Discretize a pdf to operate on its samples
•F (Forward) : Given a function, estimates the distribution of
next node in the formula hierarchy using samples
•B (Band-pass) : Used to decrement number of samples
using a threshold on sample probabilities
•R (Re-bin) : Used to decrement number of samples by
combining close samples together
•Q-1 (De-Quantize) : Convert a discrete pdf back to continuous
9
domain : interpolation
Necessary Operators (Q, F, B, R) on a
Connectivity Graph
tox 0 Weff Leff
T
NSUB
ms
F
Cox
k

Qdep
Q
Q
T
NSUB
Vth
F
B
ID
R
PHIf
gm
rout
Q-1
•F, B and R repeated until we acquire the distribution of10a
high level parameter (ex. g )
pdf(X)
Probability Discretization Theory:
QN Operator
•can write spdf(X) as :
pdf(X)
(X ) 
 p  (x  w )
i1.. N
spdf(X)
X
spdf(X)=(X)
i
i
where :
pi : probability for i’th impulse
wi : value of i’th impulse
X
 ( X )  QN ( pdf ( X ))
•QN band-pass filter pdf(X) and divide into bins
N in QN indicates number or bins
•Use N>(2/m), where m is maximum derivative of
pdf(X), thereby obeying a bound similar to Nyquist
11
Error Analysis for Quantization
Operator
•If quantizer uniform and  small, quantization error
random variable Q is uniformly distributed
Variance of quantization error:
  E[Q ]  
2
Q
2
/2
 / 2
2
q pdf (Q) dq
2

12
12
F Operator
•F operator implements a function over spdf’s using
deterministic sampling
 (Y )  F ( ( X1 ),..,  ( X r ))
Xi, Y : random variables
•Corresponding function in connectivity graph
applied to deterministic combination of impulses
•Heights of impulses (probabilities) multiplied
•Probabilities are normalized to 1 at the end
 (Y ) 
p
s1 ,.., sr
X1
s1
.. p  ( y  f (w ,.., w ))
Xr
sr
X1
s1
X1
s1
pXs : probabilities of the set of all samples s belonging to X
13
Effect of Non-linear Functions
Impulses after F, before B and R
•Non-linear nature of functions cause accumulation in certain ranges
•De-quantization would not result in a correct shape
•Increased number of samples would induce a computational burden
14
Band-pass and re-bin operations needed after F operation
Band-pass, Be, Operator
 ' ( X )  Be ( ( X ))
Margin-based Definition:
•Eliminate samples having values out of range (6): might
cut off tails of bi-modal or long-tailed distributions
Novel Error-based Definition:
•Eliminate samples having probabilities least likely to occur :
eliminates samples in useful range hence offers more
computational efficiency
 p  (x  w )
(X ) 
i
i:( pi 
max i ( pi )
)  ( pi  ( X ))
e
i
e : error rate
•Implementation : eliminate samples with probabilities less
15
than 1/e times the sample with the largest probability
Re-bin, RN, Operator
Impulses after F
Unite into one  bin
 ' ( X )  RN ( ( X ))
Resulting spdf(X)
•Samples falling into the same bin congregated in one
st. w j  bi
 ( X )   p i  ( x  wi ) where : pi   p j
i
sj
•Without R, Q-1 would result in a noisy graph which16
is not a pdf as samples would not be equally separated
Error Analysis for Re-bin Operator
Distortion caused by representing samples in a bin by a single
2
sample:
d (m , w )  (m  w )
i
j
i
j
mi : center or i’th bin
Total distortion:
 d (m , w ) p
i , j:i ( jbi )
i
j
j
17
Experimental Results
(X) for Vth
(X) for gm
•Impulse representation for threshold voltage and
18
transconductance are obtained through FDPP on the graph
Monte Carlo – FDPP Comparison
Pdf of Vth
Pdf of ID
solid : FDPP
dotted : Monte Carlo
•A close match is observed after interpolation
19
Monte Carlo – FDPP Comparison with
a Low Sample Number
Pdf of F
solid : FDPP with 100 samples
noisy : Monte Carlo with 1000 samples
Pdf of F
solid : FDPP with 100 samples
noisy : Monte Carlo with 100000 samples
•Monte Carlo inaccurate for moderate number of samples
•Indicates FDPP can be manually applied without major
20
accuracy degradation
Conclusions
•Forward Discrete Probability Propagation is introduced as
an alternative to Monte Carlo based methods
•FDPP should be preferred when low probability samples
need to be accounted for without significantly
increasing the number of iterations
•FDPP provides an algebraic intuition due to deterministic
sampling and manual applicability due to using less
number of samples
•FDPP can account for non-standard pdf’s where Monte
Carlo-based methods would substantially fail in terms
of accuracy
21