Transcript 18 Parallel Processing - Electrical and Computer Engineering

Statistical Sampling-Based Parametric
Analysis of Power Grids
Dr. Peng Li
EE5970 Seminar
Presented by Xueqian Zhao
Outline
— Motivation
— Prior works
— Importance sampling technique
— Sampling-based localized sensitivity analysis
— Sampling-based 2nd order parametric analysis
— Conclusion
Motivation
• Power/Ground integrity becomes a
serious challenge for modern chip
design
• IR drops reduce noise margin and
increase circuit delay
— 10% supply voltage fluctuations may
translate in more than 10% timing
variation
• Technology scaling worsens the P/G
integrity
— Reduction of power supply voltage
Analysis Challenge
•
Modern P/G networks routinely reach multi-million
node complexity
— Full grid analysis becomes very expensive
•
Need to consider significant variation in power
consumption
— Active power is mode dependent
— Process and temperature variability impact
significantly the leakage power
•
Power grids are also subject to parametric
variations due to fabrication fluctuations
•
Multiplicity of variations in power grids make the
analysis even more difficult
Prior Works
• P/G can be modeled as a linear system:
Gv  b , G  R
nn
, v,b  R
n1
• Direct methods:
— LU, Cholesky decomposition
• Iterative methods:
— Conjugate gradient (CG), preconditioned CG
— Multigrid method
• Since G is a sparse matrix, the complexity of
above methods is around O(n2)
Random Walks
• Convert an electrical
network to a
random walk
• Circuit response
estimated locally via
mean estimation
— Average over a set
of statistical
samples
• Locality exploited
naturally without
solving the complete
network
2
G1 1
I1
G3
G2
3
4
P12 C1
2
1
4
P14
P13
3
Random Walks (cont.)
• Transition probabilities
between states are
obtained from the
electrical network
• The random walk can
be described as
Markov chain
• The complexity can be
reduced to O(n),
compared to prior
works.
m
Pa , k   Pa ,i
i 1
m
V a , k   Pa ,i D a ,i
i 1
VDD
VDD
Localized Analysis
• Locally solve for selected
circuit nodes
Target Node ni
VDD
• Compute the nominal
node voltage (IR drop)
for each node
— Achievable through
random walks
• Sensitivities with respect
to multiple
process/loading
variations??
• High order parametric
dependencies??
VDD
V (ni )
V (ni ) ??
??
p j
V (ni )  f ( p1, p2 ,) ??
Adjoint Sensitivity Analysis
• Classical adjoint sensitivity analysis
• Requires two complete linear solutions
— Obscure the possibility of locality
• Localized sensitivity analysis??
Intuition
• Original circuit differs
from the perturbed
circuit in circuit
element values
• Want to solve both
circuits simultaneously
by only sampling in
the original circuit
• Need to scale each
sample to correct the
sampling bias:
Original Circuit (A)
Pk1
Pk2
Pk3
node ni
…
Value: Dk
Vdd
Prob: Pk = Pk1Pk2
Perturbed Circuit (B)
node ni
…
P’k1
P’k2
P’k3
D’k  (P’k/Pk)D’k
Value: D’k
Prob: P’k = P’k1P’k2…
Vdd
Importance Sampling
• View random walks algorithms as a
Monte Carlo method
• Circuit response is estimated via
mean estimation
• Importance sampling allows us to
estimate the mean of a statistical
distribution while sampling
according to another distribution
• Ratio estimate
Localized Sensitivity Analysis
• Design / process parameters

  [ 1 ,  2 ,,  s ]T
• Perform sampling only in the nominal circuit


  0
• Estimate the response in any parametric circuit
• Need to propagate the first order sensitivities while
sampling in the nominal circuit
Localized Sensitivity Analysis
• Propagate circuit element parametric
sensitivities
• Perform a few scalar arithmetic operations
— Additions, subtractions, multiplications and
divisions
Localized Parametric Analysis Flow
Pick a new move
according to the
nominal ckt
Pick a new move
according to the
nominal ckt
Compute the prob. of this
move and update the path
prob. Ppath for the param. ckt
Accumulate the cost
incurred by the move
Compute the prob. of this
move and update the path
prob. Ppath for the param. ckt
……
Accumulate the cost
incurred by the move
……
Weight the gain of the
complete walk by
Wpath = Ppath/Ppath(nom)
……
Weight the gain of the
complete walk by
Wpath = Ppath/Ppath(nom)
+
Mean estimate:
Sum up and
normalize
Second Order Analysis
• 2nd order analysis gives more accurate results for larger
perturbations
• Straightforward implementation is prohibitively expensive
— 276 coefficients needed for 22 variables !
• Can exploit the inherent spatial locality in the algorithm
formulation
• Adopt two 2nd order parametric forms:
— Voltage response estimate /cost incurred due to current sources
— State-transition/path probabilities
Exploring Spatial Locality
• Naïve 2nd order analysis not
feasible for a large number of
inter-/intra die variations
Global
• Model variations sources using a
hierarchical model
Semi-Global
— Global, semi-global and local
variations
Local
• Local data types impacted only by
a small set of variations
— Represented in a SPARSE 2nd
order form
+
+
Exploring Spatial Locality
• Data interactions
Node of Interest
— Local + local: efficiently computable
— Global + global: only happen at end
of each random walk
— Global + local: many counts /
dominant cost!
• Exploring sparsity
X
• Dominant cost: O(NGNL), NL << NG
Importance Sampling Estimators
• Importance sampling
• Integration estimator
• Ratio estimator
Importance Sampling Estimators
• Regression estimator
Results
• Comparison of estimators
— 40k-node grid
— Solve the nominal ckt and the perturbed circuit
simultaneously
IR drop
estimation in the
perturbed circuit
Results
• Localized sensitivity analysis
— Simultaneously solve for sensitivities
— Compared with direct sensitivity
# Nodes
40K
90K
250K
1.1M
1.4M
Direct T.
83s
356s
40m30s
N/A
N/A
Int. T
1.38s
1.93s
2.21s
2.25s
4.81s
Int. Err.
45.1%
9.01%
0.14%
N/A
N/A
Ratio T.
1.42s
2.03s
2.29s
2.28s
4.85s
Ratio Err.
7.00%
2.49%
0.14%
N/A
N/A
Reg. T.
1.59s
2.24s
2.34s
2.33s
4.87s
Reg. Err
0.35%
1.31%
0.06%
N/A
N/A
Results


A 250K node grid
Resistance variation
 Average: 12.3%
 Max:
55%

22 variation sources
 1st order analysis: 23 coefficients
 2nd order analysis: 276 coefficients

Runtime


1000 samples: 1st order errors
1st order: 3.1s
2nd order: 22s
1000 samples: 2nd order errors
Results


A 1.1 million node grid
Resistance variation
 Average: 13%
 Max:
55%

Loading variation
 Average: 19%
 Max:
164%
1000 samples: 1st order errors

22 variation sources
 1st order analysis: 23 coefficients
 2nd order analysis: 276 coefficients

Runtime
 1st order: 4s
 2nd order: 28s
1000 samples: 2nd order errors
Results
• Runtime as a function of number of variations
— Near-linear complexity achieved by exploring spatial
locality
2nd order
analysis
runtime
Conclusion
•
Power/ground network verification is becoming increasingly difficult due to large
problem complexity
•
The analysis complexity exacerbates as we address process variations and
current loading uncertainties
•
Efficient parametric analysis is proposed to analyze large power grids locally
— Adopt importance sampling in Monte Carlo method
— Lends itself naturally to a localized version of the classical sensitivity analysis
•
2nd order analysis improves the accuracy for larger loading and process variations
— Explore the spatial locality of the algorithm formulation to achieve near-linear
complexity