Transcript Date presentation - Tsinghua University

An Efficient Method for Chip-Level Statistical
Capacitance Extraction Considering Process
Variations with Spatial Correlation
W. Zhang, W. Yu, Z. Wang, Z. Yu, R. Jiang, J. Xiong
To be presented on DATE’2008
1
Outline
•
•
•
•
Introduction
Preliminary
Statistical Capacitance Extraction
Chip-Level Capacitance Extraction
Considering Spatial Correlation
• Numerical Results
• Conclusion
2
Process Variations
• Become an issue in 90nm technology and beyond
• Systematic:
– Pattern-dependent
– Modeled with deterministic methods
• Random:
– Need stochastic modeling
Photo from Synopsys [GLS-VLSI’06]
– Challenges to computational efficiency
• Monte-Carlo simulation
– Involves thousands of stochastic samplings
– Suffers from huge computational time (converging rate 1/
3
– Benchmark approach
M)
Existing Methods
• Recently proposed approaches
– FastSies [ICCAD’05]: rough surface, non-sampling, SBIE
– Perturbation [ICCAD’05]: quadratic model of C, Taylor’s
expansion on potential matrix and solution
– Spectral Stochastic Collocation Method [DATE’07]:
HPC technique, higher accuracy than perturbation, efficient
techniques for solving potential matrix and variable reduction
• Limitations of Perturbation & SSCM
– Model the fluctuation of each surface panel (large #variable k)
– Time  k2  time of running 3-D field solver
• Small structures; variation model for rough surface
4
Our Contribution
• Chip-level capacitance extraction
– Considering fluctuation of each panel may not be necessary
– Window-based method, covariance among windows needed
– How to get the statistical capacitance of a critical path
• Contributions
– Simple variation model
– Intra-window algorithm
– Capacitance covariance
among windows
– Statistical method for full-path extraction
– 100x or more faster than MC simulation
5
Outline
• Introduction
• Preliminary
– Grid-Based Variation Model
– Homogenous Chaos Expansion
• Statistical Capacitance Extraction
• Chip-Level Capacitance Extraction
Considering Spatial Correlation
• Numerical Results
• Conclusion
6
Grid-Based Variation Model
• Described in [TCAD’07]
• Random variables
ILD2
Space1
ILD1
T
Space2
W
– Width, thickness, spacing, ILD thickness
• Grid model and spatial correlation
– In each cell: each physical
parameter has an unique value
– Among cells: characterized
by a correlation matrix
• Gridding scheme depends on
Uniform grids Nonuniform grids
– Knowledge of manufacturing
– Error tolerance
7
Homogenous Chaos
• Homogenous chaos expansion for stochastic function



d
d
i1
C ( )   c j  j ( )  a0 0   ai1 1 (i1 )   ai1i2  2 (i1 , i2 )  ...
j 1
i1 1
i1 1 i2 1
• Hermite polynomials are for Gaussian random process
0
–  1
1
–  (i )  i
– 2 (i ,  j )  i j  ij
• The orthogonality of Hermite polynomials
  i ( ),  j ( )     ...  i ( ) j ( )  ( )d1...d d   ij
1
d
1 d  12 T 
where   (
) e
is the probability density function
2
Homogenous Chaos
• HCE converges for any Gaussian random
process with finite second-order moments
• HPC has optimal convergence rate for a
Gaussian random process [SIAM-JSC’02]
The Askey Scheme
9
Outline
• Introduction
• Preliminary
• Statistical Capacitance Extraction
– Hermite Polynomial Collocation (HPC) Method
– Variable Preprocessing
• Chip-Level Capacitance Extraction
Considering Spatial Correlation
• Numerical Results
• Conclusion
10
HPC Method
• Hermite polynomial expansion of capacitance:

C ( )   c j  j ( )
j 1
• Perform Galerkin method with M polynomials:
M
 C ( ),  k ( )   c j  j ( ),  k ( ) , k  1, 2, ..., M
j 1
cj 
 C ( ),  j ( ) 
  j ( ),  j ( ) 
(Orthogonality )
 C ( ),  j ( )   C ( ) j ( )  ( )d
Computing time:
K times of conventional
capacitance extraction,
independent of solver
K
  wi C ( i ) j ( i ) ( Numerical quadrature,  i is Hermit-Gauss point)
i 1
11
Sparse Grid Quadrature
• A technique to reduce collocation points for quadrature
• Level k grid has 2k+1 degree of exactness
• One-dimensional quadrature (Gaussian quadrature)
– Collocation point set 1k :k+1 points
• d-dimensional quadrature
– Point set kd 
k 1 d |i| k
(1i1  ...  1id ),| i |  i j
– About 2d points for level 1 accuracy, 2d2 for level 2
– Weights:
i1...id
ji1 ... j id
w
 (1)
k |i|
 d 1 
im

w

 m jim
k

|
i
|


12
HPC with Sparse Grid
• Solve  C ( )
j
( )  ( ) d
with sparse grid
Order k expansion
C and Ψj at most order k
CΨj at most order 2k
Need level k grid for 2k+1 degree of exactness
• Conclusion: sparse grid with level k accuracy
required for order k expansion of capacitance
For quadratic capacitance model, sparse grid with level 2 accuracy is
13
needed, that means 2d2 collocation points for numerical quadrature
Some Acceleration Techniques
• If the number of variable (quadrature dimension) is
small, Sparse Grid may have more collocation points
than the Gaussian quadrature
– In this case, we use Gauss quadrature instead
• There are duplicate points with different weights
– Consider it to reduce calls of capacitance extraction
• If 3-D capacitance extractor with iterative solver is
used, minimum spanning tree of collocation points is
constructed
– Employing the preceding solution as the initial guess of
iterative solver can speedup the next capacitance solution
14
Variable Preprocessing
• HPC requires independent random variables
• For an intra-window extraction, the variables may be
not independent if several variation cells are involved
• Get independent variables with Cholesky factorization
covariance matrix n  LLT ,   L *
• A simple example

2
w1
1


1
 LL , L   w1 

1
 

T
0
1    w1
      1   2
w1
 2   w1
3   0
0



2
1   
0
0  1* 
  *
0   2 
 w 2  3* 
 
 : standard deviation
 : correlation coefficient
 * : independent variable 15
Summary: Intra-Window Extraction
Algorithm Intra-Window Capacitance Extraction (Wi)
1. Preprocess variables inside Wi
2. Calculate collocation points {pj}
Can be done
by any solver
3. For each pj
4. Solve desired capacitances in Wi at pj
5. For each desired capacitance CklM
6. Evaluate coefficients in Ckl   cklj  j ( )
j 1
7.
Evaluate mean and variance with
 E (Ckl )  ckl1

M

2
D
(
C
)

c
  j ( ),  j ( ) 

kl

klj
j 2

16
Outline
•
•
•
•
Introduction
Preliminary
Statistical Capacitance Extraction
Chip-Level Capacitance Extraction
– Window and Grid Partition
– Inter-Window Covariance
– Full-Path Capacitance Extraction
• Numerical Results
• Conclusion
17
Window and Grid Partition
• Sophisticated techniques are actually used for
window partition and capacitance assembling
• Because we focus on the variation-aware extraction,
assume a simple partition and assembling technique
• Extraction windows and variation grid
– The setting of extraction windows depend on balancing
the accuracy and efficiency
– Variation grid depends on manufacturing process and
accuracy tolerance
– They have different strategy, and a window may involve
several variation grid cells
18
Inter-Window Covariance
• For any two windows i and j:
Mj
Mi
Cki   ckip  p ( ), Ckj   ckiq  q ( ')
p 1
q 1
Mi M j
cov(Cki , Ckj )   ckip ckjq cov( p ( ), q ( '))
Transformed to
covariance between
functionals
p 1 q 1
• Firstly consider the covariance between variables
– Reverse the preprocessing step to have physical parameters
  Li 1 * ,    Lj1 *
cov(a , b )  cov( liatt* ,  l jbrr* )
t
r
  liat l jbr cov(t* , r* )
t
r
Check out from the
grid-based variation
model
19
Covariance between functionals
• Level-0 functional has 0 covariance with any other
• Other functionals in the quadratic model produce the
following covariance pairs
cov(a , b )
cov(a 2 1, b2 1)  2cov(a , b )2
cov(ac , b2 1)  2cov(a , b )cov(c , b )
cov(ac , bd )  cov(a , b )cov(c , d )  cov(a , d )cov(c , b )
cov(ac , b )  0
cov(a 1, b )  0
2
All converted to the
covariance between
variables
20
Covariance between functionals, proof
• Problem: Derive cov(ac , bd )
• Solution: Correlation matrix of (a , c , b, d )
 I PT 
 cov(a , b ) cov(c , b ) 
n  
 where P  



cov(

,

)
cov(

,

)
P
I
a
d
c
d 



– Perform Cholesky decomposition:
I 0 
 x11
n  LL , L  
, Lx  

 x21
 P Lx 
cov( a c , b d )
T
0
T
2
,
and
L
L

(
I

P
)
x
x

x22 
 cov( a c , ( P11 a  P12 c  x11 b*)( P21 a  P22 c  x21 b*  x22 d*))
 cov( a c , ( P11 P22  P12 P21 ) a c )
 cov( a , b ) cov( c ,  d )  cov( a ,  d ) cov( c , b )
21
Computational Complexity
• Most covariance between functionals are 0.
• Only O(Mi+Mj) calculations are needed, if a window
does not include many grid cells
• Not many window pairs need to
be considered, because the
correlation coefficient decays
to about 10-4 at distance 3
0
10
-2
10
-4
– Ignore far window induces
little error
Correlation
coefficient
10
-6
10
-8
10
-10
10
Correlation coefficient   exp(r 2 /  2 )
1.5
2
2.5
3
3.5
* Correlation Length
4
4.5
22
5
Full-Path Capacitance Extraction
• We consider simple capacitance assembling
– Just sum the capacitances from related windows
– Mean of total capacitance
E(Ck )  E( Ck i )   E(Ck i )
i
C14
i
C13
– Variance of total capacitance
D(Ck )  D( Cki )   D(Cki )  2 cov(Cki , Ckj )
i
i
i j
C12
• Explicit quadratic form or PDF
C
11
– Get the independent variable
– PFA may be need to reduce variable
– Obtain PDF with the technique of characteristic function
23
[ICCAD’05]
Summary: Full-Path Extraction
Algorithm Full-Path Capacitance Extraction
1.Partition windows for capacitance extraction
2.For each window Wi do
3. Run Intra-Window Extraction(Wi)
4.For each critical net k with related window set Wk
5. Utilize the capacitances for windows in Wk to
calculate the full-path capacitance.
24
Outline
•
•
•
•
Introduction
Preliminary
Statistical Capacitance Extraction
Chip-Level Capacitance Extraction
Considering Spatial Correlation
• Numerical Results
• Conclusion
25
Experiment 1
• FastCap 2.0 is used to extract intra-window
capacitances with samplings of geometry
• Experiments run on a Sun server with 750MHz CPU
• The first case
– 2 conductors: 1140um each, with spacing 2um
– 10 windows(each: 114um)
– Variation grid and window partition
have coincide boundary
– Variation sources: one thickness, two widths
– Standard deviation：0.2um
26
Exp 1, Results
• 10,000 Monte-Carlo simulations: 13293s
Total Cap Err.
Model
Quadrature
Points
Time(s)
Linear
7
Quadratic
25
Capacitance variance is
largely underestimated if
ignore the inter-window
correlation
Coupling Cap Err.
Mean
Std
Mean
Std
9.34
-0.10%
-1.00%
-0.06%
-1.31%
33.5
-0.03%
-0.66%
0.04%
-0.70%
Experiment 2
• Overlapped grids and windows
– # variable in each window increases from 3 to 6
Model
Quadrature
Points
Time(s)
Linear
13
Quadratic
85
Total Cap Err.
Coupling Cap Err.
Mean
Std
Mean
Std
19.2
-0.12%
-0.90%
-0.10%
-1.74%
126
0.06%
-0.44%
0.06%
-0.32%
– Speedup to Monte-Carlo simulation is still > 100
– Due to increase of variable, computational time increases by
2.0 and 3.8 times
– Up to now, the linear model show enough accuracy
– The following experiment shows the necessity of quadratic
28
model
Experiment 3 & 4
• Choose spacing as the only variation source
Model
Points
Time(s)
Linear
2
Quadratic
3
Total Cap Err.
Coupling Cap Err.
Mean
Std
Mean
Std
2.67
0.04%
-3.45%
0.08%
-3.09%
3.97
-0.02%
-0.69%
-0.07%
-0.83%
– Significant advantage of quadratic model
• A practical large case
– width, height, ILD thickness, spacing
– 8 normal window and 1 shift widow
Model
Points
(normal)
Points
(shift)
Time(s)
Speedup
to MC
Mean
Err.
Std Err.
Linear
13
21
251
718
0.01%
-1.89%
Quadratic
85
221
1803
100
-0.07%
-0.83%
29
Outline
•
•
•
•
Introduction
Preliminary
Statistical Capacitance Extraction
Chip-Level Capacitance Extraction
Considering Spatial Correlation
• Numerical Results
• Conclusion
30
Conclusion
• A practical framework for chip-level capacitance extraction
considering spatial correlated variations
• An efficient HPC technique is presented for extract the
statistical capacitances within the extraction window
• The formula for the covariance of capacitances from different
windows is derived
• Efficient algorithm is proposed to calculate the statistics of
full-path capacitance
• Numerical experiments show that the method is of high
accuracy and more than 100x faster than the MC simulation
31