Transcript Fast 3-D Interconnect Capacitance Extraction and Related

Fast 3-D Interconnect
Capacitance Extraction and
Related Numerical Techniques
Wenjian Yu
EDA Lab, Dept. Computer Science
& Technology, Tsinghua University
Nov. 22, 2004
Outline

Background

3-D capacitance extraction with direct BEM

Fast capacitance extraction with QMM
acceleration and other numerical techniques

Numerical results

Conclusion
2
Background

Parasitic extraction in SOC
Interconnect dominates circuit performance



Other parasitics




Interconnect delay > device delay
Crosstalk, signal integrity, power, reliability
Substrate coupling in mixed-signal circuit
Thermal parasitics for on-chip thermal analysis
Interconnect parasitic extraction


Resistance, Capacitance and Inductance
Becomes a necessary step for performance
verification in the iterative design flow
3
From electro-magnetic
analysis to circuit simulation
Parasitic extraction
/ Electromagnetic
analysis
Panel with
uniform
charge
Filament
with
uniform
current
Thousands of R, L, C
Model order
reduction
Reduced circuit
4
VLSI capacitance extraction

1V
Capacitance extraction


For m conductors solve m
potential problems for the
conductor surface charges
1 2
4
3
Electric potential u fulfill:
u u u
  (u )  2  2  2  0
x y
z
2
2
2
0V
C1i= -Qi (i1)

Capacitance is function of wire shape, environment,
distance to substrate, distance to surrounding wires

Challenges: high accuracy (3-D method), high speed,
suitable for complex process
5
VLSI capacitance extraction

3-D methods for capacitance extraction







Finite difference /
Finite element
Sparse matrix, but with
large number of unknowns
Boundary integral formulation (BEM)
Fewer unknowns, more accurate, handle complex
geometry
Two kinds: indirect BEM makes dense matrix
direct BEM has localization property
Both BEM’s need Krylov subspace iterative solver
and fast algorithms (multipole acceleration, hierarchical,
precorrected FFT, SVD-based, quasi-multiple medium, …)
6
Direct BEM for Cap. Extraction

Physical equations

Laplace equation within each subregion

Finite domain model

Bias voltages set on conductors
u
q
2
1
conductor
u is electrical potential
q is normal electrical field intensity on boundary
7
Direct BEM for Cap. Extraction

Direct boundary element method

v
u
Green’s Identity  (u v  v u )d     (u  v )d 
n
n
Freespace Green’s function as weighting function

The Laplace equation is transformed into the BIE:
2

cs u s 
*
q
 s u d 
 i
2
*
u
 s q d
 i
s is a collocation point
u*s is freespace Green’s function,
or the fundamental solution of
Laplace equation
More details:
C. A. Brebbia, The Boundary Element Method for Engineers,
London: Pentech Press, 1978
8
Direct BEM for Cap. Extraction

Discretize domain boundary
•
Partition quadrilateral elements with
constant interpolation
•
Non-uniform element partition
•
Integrals (of kernel 1/r and 1/r3) in discretized BIE:
N
N
cs us   (  q d)u j   (  us*d)q j
j 1
j
*
s
•
Singular integration
•
Non-singular integration
j 1
s
j
Y
P4(x4,y2,z2)
j
P1(x1,y1,z1)
P3(x3,y2,z2)
t
P2(x2,y1,z1)
•
Dynamic Gauss point selection
•
O
X
Z
Semi-analytical approach improves
computational speed and accuracy for near singular integration
9
Direct BEM for Cap. Extraction

Write the discretized BIEs as:
i
i
i
i
H  u  G  q , (i=1, …, M)
Compatibility equations
along the interface
 a  u a na   b  ub nb
u  u
b
 a
Ax  f
• Non-symmetric large-scale matrix A
• Use GMRES to solve the equation
• Charge on conductor is the sum of q
For problem involving multiple regions, matrix A exhibits sparsity!
10
Fast algorithms - QMM

Quasi-multiple medium method

In each BIE, all variables are within same dielectric region; this
leads to sparsity when combining equations for multiple regions
q
u
3-dielectric
structure
v11 u12 q21 v22 u23 q32 v33
s11
s12
s21
s22
③
②
Population
of matrix A
s23
①
s32
s33
substrate


Make fictitious cutting on the normal structure, to enlarge
the matrix sparsity in the direct BEM simulation.
With iterative equation solver, sparsity brings actual benefit.
QMM !
11
Fast algorithms - QMM

QMM-based capacitance extraction



Make QMM cutting
Environment
Conductors
Then, the new structure with many
z
subregions is solved with the BEM
Time analysis

while the iteration number
dose not change a lot
x
y
tZ

Z: number of non-zeros in
the final coefficient matrix A
Confirmed in our later experiments
Master Conductor
A 3-D multi-dielectric case within finite
domain, applied 32 QMM cutting
12
Fast algorithms - QMM

Select optimal cutting pair



Empirical formula, or manually specifying
Automatic selection, make total
computation achieve highest speed; make
use of the linear relationship between
computational time and the parameter Z
Flowchart
Cutting pair: (3, 2)
Determine theset S containing the
candidates of cutting numbers
Calculate the Z-value for a cutting
number in the set S
Select the optimal cutting number
according to the Z-values
with minimal Z-val
13
Fast algorithms - QMM

Heuristic rules for set S -- candidates of (m, n)




Relatively small size for the sake of saving time
Moderate value range of m (along X-axis) and n (along Y-axis)
Range is relevant to the dimensions along X/Y-axis
Calculate the Z-value

Two types of boundary element

Nuemann: one u variable / element

Dirichlet: one q variable / element

Interface: both u and q variable / element ( Type 2) bi
( Type 1) ai
N

N
The discretized BIE: csus   ( q d)u j   ( us*d)q j


So,
j 1
*
s
j
j 1
Z i  N i  Vi  (ai  bi )(ai  2bi )
Need not construct the actual geometry & boundary mesh !
j
Q
Z   Zi
i 1
14
Fast algorithms - Equ. organ.
 Too many subregions produce complexity of equation
organizing and storing
 Bad scheme makes non-zero entries dispersed, and worsens
the efficiency of matrix-vector multiplication in iterative solution
 We order unknowns and collocation points correspondingly;
suitable for multi-region problems with arbitrary topology
 Example of matrix population
v11 u12 q21 v22 u23 q32 v33
s11
s12
s21
s22
s23
Three
stratified
medium
12 subregions
after applying
22 QMM
s32
s33
15
Fast algorithms - Preconditioning

Basics of the preconditioning technique

Aim: improve the condition of the coefficient matrix,
so as to obtain faster convergence rate
Ax

The right-hand preconditioning:


Suitable for GMRES
 f
APy  f, x = Py
Construct the GMRES preconditioner (matrix P )



AP should has better spectrum of eigenvalues than A
P should be a brief approximation to A-1
To balance the speedup of convergence and the additional consumption of the preconditioner (to construct it, multiple it in each iteration)
a sparer one should be good !
16
Fast algorithms - Preconditioning

A brief overview



Jacobi method (the diagonal preconditioner: diag(A)-1 )
Mesh neighbor method: (can’t applied directly)

S.A. Vavasis, SIAM J. Matrix Anal. Appl. 1992

K. Chen, SIAM J. Sci. Comput. 1998

K. Chen, SIAM J. Matrix Anal. Appl. 2001
Nearest neighbor method (in FastCap2.0)


Coupled with the multipole algorithm
Emphasis of our work


Suitable for direct boundary element method
Simpler and more efficient, since the Jacobi preconditioner has
reduced the iterative number down to several tens
17
Fast algorithms - Preconditioning

Principle of the MN method
T T
 PA  I  A P
 I  AT pi  ei , i  1, ..., N


The neighbor variables of variable i: L  {l1 , l2 , ... , ln }  {1, 2, ... , N}
Solve the reduced equation A pi  ei , fill back to ith row of P
T
l1 l2 l 3
Solve, and fill P
Var. i
l1 l2 l 3
Reduced equation
A
T
A
pi =
0
1
0
P
i
18
Fast algorithms - Preconditioning

Extended Jacobi preconditioner




Singular integral is importance
Singular integrals from interface elements
are not all at the main diagonal
Except for row corresponding to interface
element, solve a 22 reduced equation to
involve all singular integrals
v11 u12 q21 v22 u23 q32 v33
s11
s12
s21
s22
s23
s32
s33
MN (n) preconditioner



n is the number of neighbor elements
Scan the ith row, use the absolute value as measure of neighborhood
When n=1, 2, performs well
30% or more time reduction, compared with using the
Jacobi preconditioner, for more than 100 structures
19
Fast algorithms -
nearly linear
Efficient organization and solution technique ensure
near linear relationship between the total computing
time and non-zero matrix entries (Z-values)

For two cases from actual layout:
4
35
3.5
30
Computing time (s)
Computing time (s)

3
2.5
2
1.5
1
0.5
25
20
15
10
5
0
0
0
200
400
Z -value (10 3 )
m: 2~9, n: 2~6
600
0
2000
4000
Z -value (10 3 )
m: 2~7, n: 2~10
6000
20
Numerical results (1)

Experiment environment

SUN UltraSparc II processors (248 MHz)

Programs




Our QMM-BEM solver: QBEM
FastCap 2.0: FastCap(1), FastCap(2)
Raphael RC3 (3-D finite difference solver)
Test examples
z

kk crossovers in five
layered dielectrics (k=2
to 5)
Finite domain

C1 is calculated for comparison

3
1
2
4
x
The 2x2 case
21
Numerical results (2)

Computational configuration

FastCap: zero permittivity is set to the outer-space to
represent the Neumman boundary of the finite domain

Criterion: Result C1 of Raphael with 1M grids

Error formula:
Compar. I
C1  C1
2
C1
2
FastCap (1)
QMM-BEM
time mem panel err(%) time mem panel* err(%) Sp.
22
7.9
17.9 1080
1.6
1.0
1.7
1184
2.7
8
33
9.2
17.9 1284
2.1
1.3
2.7
1431
2.5
9
44
10.0 19.1 1487
3.4
1.6
2.1
1502
1.0
6
55
12.5 23.7 1804
2.9
1.5
2.1
1558
1.2
22
8
Numerical results (3)
FastCap (2)
QMM-BEM
Compar. II
time mem panel err(%) time mem panel* err(%) Sp.
22
11.5 26.4 1080
2.1
1.0
1.7
1184
2.7
12
33
15.1 28.4 1284
2.3
1.3
2.7
1431
2.5
12
44
17.5 30.7 1487
2.6
1.6
2.1
1502
1.0
11
55
24.3 38.5 1804
3.0
1.5
2.1
1558
1.2
16
Raphael (0.25M)
Compar. III
QMM-BEM
time mem panel err(%) time mem panel* err(%) Sp.
22
78.8
47
-
0.3
1.0
1.7
1184
2.7
79
33
67.1
45
-
0.4
1.3
2.7
1431
2.5
52
44
88.9
48
-
0.5
1.6
2.1
1502
1.0
56
55
81.9
48
-
0.8
1.5
2.1
1558
1.2
55
23
Numerical results (4)

Our QMM-BEM solver


Panel* don’t count the panels on interfaces between fictitious media
The optimal QMM cutting pairs are (4, 4), (5, 5), (3, 3), (3, 3)
respectively ; the EJ preconditioner is uesed
Comparison IV. Computational details for the 44 crossover problem
panel Ele_N Var_N Z-val Iter. mem Tgen(s) Tsol(s) Time
QBEM
1502
1896
2435 0.24M 11
2.1
1.02
0.29
1.6
FastCap(1) 1487
1487
1487
-
13
19.1
6.9
2.9
10.0
FastCap(2) 1487
1487
1487
-
9
30.7
13.4
4.0
17.5
Tgen: time of generating the linear system
Tsol: time of solving the linear system
24
Discussion
Contrast
FastCap
QBEM
Formulation
Single-layer potential formula Direct boundary integral equation
System matrix
Dense
Dense for single-region, otherwise sparse
Matrix degree
N, the number of panels
A little larger than N
Acceleration
Multipole method: less than
QMM method -- maximize the matrix
N2 operations in each matrix- sparsity: much less than N2 operations in
Other cost

vector product
each matrix-vector product
Cube partition and multipole
Efficient organizing and storing of sparse
expansion are expensive
matrix make matrix-vector product easy
Resemblance:

boundary discretization

stop criterion of 10-2 in GMRES solution

similar preconditioning

almost the same iteration number
25
Conclusion

Numerical techniques in the QMM-BEM solver






Analytical / Semi-analytical integration
Quasi-multiple medium acceleration (cutting pair selection)
Equation organization of discretized direct BEM
Preconditioning on the GMRES solver
Achieve about 10x speed-up to FastCap
Related work

Use the blocked Gauss method for capacitance extraction
with multiple master conductors

Handle problem with floating dummies in area filling

Apply the direct BEM to the substrate resistance extraction
26
For more information



Wenjian Yu, Zeyi Wang and Jiangchun Gu, “Fast capacitance extraction of
actual 3-D VLSI interconnects using quasi-multiple medium accelerated
BEM,” IEEE Trans. Microwave Theory Tech., Jan 2003 , 51(1): 109-120
Wenjian Yu and Zeyi Wang, “Enhanced QMM-BEM solver for 3-D multipledielectric capacitance extraction within the finite domain,” IEEE Trans.
Microwave Theory Tech., Feb 2004, 52(2): 560-566
Wenjian Yu, Zeyi Wang and Xianlong Hong, “Preconditioned multi-zone
boundary element analysis for fast 3D electric simulation,” Engng. Anal.
Bound. Elem., Sep 2004, 28(9): 1035-1044
27
Thank you !
For more information:
[email protected]