Interconnect Parasitic Extraction

Speaker: Wenjian Yu Tsinghua University, Beijing, China

Thanks to J. White, A. Nardi, W. Kao, L. T. Pileggi, Zhenhai Zhu

Outline
Introduction to parasitic extraction Resistance extraction Capacitance extraction Inductance and impedance (RLC) extraction

Introduction to Parasitic Extraction

Introduction
Interconnect: conductive path Ideally: wire only connects functional elements (devices, gates, blocks, ) and does not affect design performance This assumption was approximately true for large design, it is unacceptable for DSM designs
Slides courtesy A. Nardi, UC Berkeley

Introduction
Real wire has:
Resistance Capacitance Inductance

Therefore wiring forms a complex geometry that introduces capacitive, resistive and inductive parasitics. Effects:
Impact on delay, energy consumption, power distribution Introduction of noise sources, which affects reliability To evaluate the effect of interconnects on design performance we have to model them
Slides courtesy A. Nardi, UC Berkeley

Conventional Design Flow

Funct. Spec RTL Logic Synth. Front-end Back-end Gate-level Net. Floorplanning Parasitic Extrac. Place & Route Layout
Slides courtesy A. Nardi, UC Berkeley

Behav. Simul.
Stat. Wire Model

Gate-Lev. Sim.

From electro-magnetic analysis to circuit simulation

Parasitic extraction / Electromagnetic analysis Filament with uniform current Panel with uniform charge

Thousands of R, L, C

Model order reduction

Reduced circuit
7

Challenges for parasitic extraction

Parasitic Extraction
As design get larger, and process geometries smaller than 0.35m, the impact of wire resistance, capacitance and inductance (aka parasitics) becomes significant Give rise to a whole set of signal integrity issues

Challenge
Large run time involved (trade-off for different levels of accuracy) Fast computational methods with desirable accuracy
8

Resistance Extraction

Outline
Introduction to parasitic extraction Resistance extraction
Problem formulation Extraction techniques Numerical techniques Other issues

Capacitance extraction Inductance and RLC extraction

01

Resistance extraction
Problem formulation
A simple structure
V L L = R= = i S HW
H L W i

Two-terminal structure
R= V i
A + V

i B

Its a single R value

Multi-terminal (port) structure

NxN R matrix; diagonal entry is undefined
11

Resistance extraction
Extraction techniques
R=R

Square counting Analytical approximate formula

For simple corner structure

L W

2-D or 3-D numerical methods

For multi-terminal structure; current has irregular distribution Solve the steady current field for i under given bias voltages Set V1 = 1, others all zero,
flowing-out current

1 i1k = R1k
21

Repeating it with different settings

Resistance extraction
Extraction techniques numerical method
How to calculate the flowing-out current ? Field solver Field equation and boundary conditions
Laplace equation inside conductor:

u = 0
divergence

2u 2u 2u 2 u= 2 + 2 + 2 =0 x y z

Boundary conditions: port surface

uk: u is known
En = u =0 n
31

Normal component other surface: is zero; current can not flow out

The BVP of Laplace equation becomes solvable

Resistance extraction
Numerical methods for resistance extraction Methods for the BVP of elliptical PDE: 2 u = 0
Finite difference method
ui +1, j , k 2ui , j , k + ui 1, j , k 2u Derivative -> finite difference: x 2 (x )2 Generate sparse matrix; for ODE and PDE

Finite element method

Express solution with local-support basis functions construct equation system with Collocation or Galerkin method Widely used for BVP of ODE and PDE

Boundary element method

Only discretize the boundary, calculate boundary value Generate dense matrix with fewer unknowns For elliptical PDE
41

Resistance extraction
Where are expensive numerical methods needed ?
Complex onchip interconnects:
Wire resistivity is not constant Complex 3D geometry around vias

Substrate coupling resistance in mixed-signal IC

51

Resistance extraction
All these methods calculate DC resistance
Suitable for analysis of local interconnects, or analysis under lower frequency High frequency: R of simple geometry estimated with skin depth; R of complex geometry extracted along with L

Reference
W. Kao, C-Y. Lo, M. Basel and R. Singh, Parasitic extraction: Current state of the art and future trends, Proceedings of IEEE, vol. 89, pp. 729-739, 2001. Xiren Wang, Deyan Liu, Wenjian Yu and Zeyi Wang, "Improved boundary element method for fast 3-D interconnect resistance extraction," IEICE Trans. on Electronics, Vol. E88-C, No.2, pp.232240, Feb. 2005.
61

Capacitance Extraction

71

Outline
Introduction to parasitic extraction Resistance extraction Capacitance extraction
Fundamentals and survey Volume discretization method Boundary element method Future issues

Inductance and RLC extraction

81

Capacitance extraction
Problem formulation
A parallel-plate capacitor Voltage: V = 1 2
Q and Q are induced on both plates; Q is proportional to V The ratio is defined as C: C=Q/V If the dimension of the plate is large compared with spacing d,

Other familiar capacitors

91

interdigital capacitor

Coaxial capacitor

Capacitance extraction
Problem formulation
Capacitance exists anywhere ! Single conductor can have capacitance
Conductor sphere

N-conductor system, capacitance matrix is defined:

[Q ] = [C ] [U ]
Coupling capacitance Total capacitance Electric potential

02

Capacitance extraction
Interconnect capacitance extraction
Only simple structure has analytical formula with good accuracy Different from resistance, capacitance is a function of not only wires own geometry, but its environments All methods have error except for considering the Shield; whole chip; But electrostatic has locality character window Stable model Technique classification:
analytical and 2-D methods
C /unit length 2-D method ignores 3-D effect, using numerical technique to solve cross section geometry
12

Capacitance extraction
Interconnect capacitance extraction
analytical and 2-D methods 2.5-D methods
fringing

lateral

parallel

Error > 10%

From Digital Integrated Circuits, 2nd Edition, Copyright 2002 J. Rabaey et al.

Commercial tools
Task: full-chip, full-path extraction Goal: error 10%, runtime ~ overnight for given process
22

Capacitance extraction
Interconnect capacitance extraction
Commercial tools(pattern-matching): Geometric parameter extraction
According to given process, generate geometry patterns and their parameters

Build the pattern library

Field solver to calculate capacitances of pattern This procedure may cost one week for a given process

Calculation of C for real case

Chop the layout into pieces Pattern-matching Combine pattern capacitances
32

Cadence - Fire & Ice Synopsys - Star RCXT Mentor - Calibre xRC

Error: pattern mismatch, layout decomposition

Capacitance extraction
3-D numerical methods
Model actual geometry accurately; highest precision Shortage: capacity, running time Current status: widely investigated as research topic; used as library-building tool in industry, or for some special structures deserving high accuracy

Motivation
The only golden value Increasing important as technology becomes complicated Algorithms for C extraction can be directly applied to R extraction; even extended to handle L extraction
42

Capacitance extraction
Technology complexity
Dielectric configuration
Conformal dielectric Air void Multi-plane dielectric

Metal shape and type

Bevel line Trapezoid cross-section Floating dummy-fill

They are the challenges, even for 3-D field solver

52

Capacitance extraction
3-D numerical methods general approach
Set voltages on conductor; solve for Qi
u n

Solve the electrostatic field for u, then

Qi =
i

Global method to get the whole matrix

Classification
Volume discretization: FDM, FEM Raphaels RC3 -Synopsys SpiceLink, Q3D Ansoft Boundary integral (element) method FastCap, HiCap, QBEM Stochastic method QuickCap - Magma Others semi-analytical approaches
62

Slides courtesy J. White, MIT

72

Slides courtesy J. White, MIT

82

Slides courtesy J. White, MIT

92

Capacitance extraction
Volume methods
Whats the size of simulation domain ? Two kinds of problem: finite domain and infinite domain

Which one is correct ?

both in most time

3-D extraction is not performed directly on a real case In the chopping & combination procedure, both models used Because of attenuation of electric field, the results from two models can approach to each other Because of its nature, volume methods use finite-domain model
03

inside alg. of FastCap

MoM (method of moment) Method of virtual charge Indirect boundary element method
Slides courtesy J. White, MIT

13

Polarized charge

Slides courtesy J. White, MIT

23

Slides courtesy J. White, MIT

33

Slides courtesy J. White, MIT

43

Slides courtesy J. White, MIT

53

Multipole expansion with order l l=0:

Slides courtesy J. White, MIT

63

Slides courtesy J. White, MIT

73

Slides courtesy J. White, MIT

83

Capacitance extraction
3-D numerical methods direct BEM
Field equation and boundary conditions
Laplace equation in dielectric region:

u = 0
divergence

2u 2u 2u 2u = 2 + 2 + 2 = 0 x y z u

Boundary conditions: conductor surface

u Neumann boundary: E = =0 n n

2
: u is known

1
conductor

Finite-domain model, Nuemann boundary condition Inside alg. of QBEM

93

Capacitance extraction
3-D numerical methods direct BEM
2 2

v u Greens Identity (u v v u )d = (u v )d n n

Scalar field

Free-space Greens function as weighting function The Laplace equation is transformed into the BIE:

cs u s +

q u d = u q d
* s * s i

s is a collocation point

u* is the fundamental solution of s Laplace equation

More details: C. A. Brebbia, The Boundary Element Method for Engineers, London: Pentech Press, 1978
04

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:
* c s u s + ( q d ) u j = ( u s d ) q j j =1 j * s j =1 j N N
s

Singular integration Non-singular integration

P4(x4,y2,z2)

P3(x3,y2,z2)

j
P1(x1,y1,z1) O

t
P2(x2,y1,z1) X

Dynamic Gauss point selection

Z Semi-analytical approach improves computational speed and accuracy for near singular integration
14 uY n a ijneW

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 a = ub

Ax = f

For problem involving multiple regions, matrix A exhibits sparsity!

24 uY n a ijneW

Non-symmetric large-scale matrix A Use GMRES to solve the equation Charge on conductor is the sum of q

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

3-dielectric structure

q
s11 s12 s21 s22 s23

v11 u12 q21 v22 u23 q32 v33

Population of matrix A

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.
34 uY n a ijneW

s32
s33

substrate

QMM !

Fast algorithms - QMM

QMM-based capacitance extraction
Environment Make QMM cutting 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
Master Conductor

tZ
Z: number of non-zeros in the final coefficient matrix A

A 3-D multi-dielectric case within finite domain, applied 32 QMM cutting

44

revlos SERMG denoitidnocerp dna noitazinagro xirtam tneiciffe yb deetnarauG

uY n a ijneW

FastCap vs. QBEM

Contrast FastCap Formulation Matrix degree Acceleration System matrix Dense
N, the number of panels Multipole method: less than vector product

QBEM
Dense for single-region, otherwise sparse A little larger than N QMM method -- maximize the matrix each matrix-vector product Efficient organizing and storing of sparse matrix make matrix-vector product easy

Single-layer potential formula Direct boundary integral equation

N2 operations in each matrix- sparsity: much less than N2 operations in

Other cost

Cube partition and multipole expansion are expensive

Resemblance:

boundary discretization stop criterion of 10-2 in GMRES solution similar preconditioning

54

almost the same iteration number

uY n a ijneW

Sparse blocked matrix each block is dense

Slides courtesy J. White, MIT

64

QuickCap FastCap FFTCap QBEM Raphael

Slides courtesy J. White, MIT

74

Capacitance extraction
Future issues
Improve speed and accuracy for complex process Make field solver suitable for full-chip or full-path extraction task Parallelizability Rough surface effect stochastic integral equation solver Process variation (multi-corner) # pattern becomes larger Consider DFM issues (dummy-fill, OPC, etc)
84

Capacitance extraction
Reference
[1] W. Kao, C-Y. Lo, M. Basel and R. Singh, Parasitic extraction: Current state of the art and future trends, Proceedings of IEEE, vol. 89, pp. 729-739, 2001. [2] Wenjian Yu and Zeyi Wang, Capacitance extraction, in Encyclopedia of RF and Microwave Engineering , K. Chang [Eds.], John Wiley & Sons Inc., 2005, pp. 565576. [3] K. Nabors and J. White, FastCap: A multipole accelerated 3-D capacitance extraction program, IEEE Trans. Computer-Aided Design, 10(11): 1447-1459, 1991. [4] Y. L. Le Coz and R. B. Iverson, A stochastic algorithm for high speed capacitance extraction in integrated circuits, Solid State Electronics, 35(7): 1005-1012, 1992. [5] J. R. Phillips and J. White, A precorrected-FFT method for electrostatic analysis of complicated 3-D structures, IEEE Trans. Computer-Aided Design, 16(10): 10591072, 1997 [6] W. Shi, J. Liu, N. Kakani and T. Yu, A fast hierarchical algorithm for threedimensional capacitance extraction, IEEE Trans. Computer-Aided Design, 21(3): 330-336, 2002. [7] W. Yu, Z. Wang and J. Gu, Fast capacitance extraction of actual 3-D VLSI interconnects using quasi-multiple medium accelerated BEM, IEEE Trans. Microwave Theory Tech., 51(1): 109-120, 2003. [8] W. Shi and F. Yu, A divide-and-conquer algorithm for 3-D capacitance extraction, IEEE Trans. Computer-Aided Design, 23(8): 1157-1163, 2004.
94

Inductance Extraction

05

Outline
Basic
Two laws about inductive interaction Loop inductance

Onchip inductance extraction

Partial inductance & PEEC model Frequency-dependent LR extraction FastHenry

Inductance or full-wave extraction with BEM

Maxwell equations & assumptions Boundary element method
15

Two inductive laws

Amperes Law
Curl operator Integral form (derived via Stokes Law): Magnetic field created by: currents in conductor loop, time-varying electric fields

For 1D wire, field direction predicted with right-hand rule

Displacement current density AC current flowing through capacitor

25

Two inductive laws

Amperes Law (contd)
Displacement current density Current density For IC, the second term is usually neglected 0.13m technology: Transistor switching current: 0.3mA minimal spacing of conductor: 0.13 m maximal voltage difference: 2V minimal signal ramp time: 20ps
(0.3 10 3 ) (0.13 0.26 1012 ) 1200 = Ratio = 3 8.9 1012 (2 /(0.13 106 )) (20 1012 ) 2.6

0.130.26

Quasi-static assumption:
35

Decouples inductive and capacitive effects in circuit

Two inductive laws

Faradays Law
Time-varying magnetic field creates induced electric field
dni

This induced electric field exerts force on charges in b Eind is a different field than the capacitive electric field Ecap:

Magnetic flux

How about curl?

Both electric fields have force on charge !

45

t B

Two inductive laws

Faradays Law (contd)
Induced voltage along the victim loop:

Orientation of the loop with respect to the Eind determines the amount of induced voltage.
Magnetic field effect on the orthogonal loop can be zero ! Thats why the partial inductive couplings between orthogonal wires becomes zero

55

Loop inductance
Three equations

All linear relationships

Relationship between time-derivative of current and the induced voltage is linear as well:
b

There are inductors in IC as components of filter or oscillator circuits; There are also inductors not deliberately designed into IC, i.e. parasitic inductance
65

aI

abL

Mutual inductance; self inductance if a=b

Onchip interconnect inductance

Parasitic inductive effect
An example Ringing behavior 50% delay difference is 17%
0.18 width, 1 length

Model magnetic interaction

chicken-and-egg problem

Far end of active line # Possible current loop: O(N2)

Generate L coefficients for all loop pairs is impractical ! O(N4) Many of these loop couplings is negligible due to little current; but in general we need to solve for them to make an accurate determination
75

Onchip interconnect inductance

Partial inductance model
Invented in 1908; introduced to IC modeling in 1972 Definition: magnetic flux created by the current through the virtual loop which victim segment forms with infinity Loop L is sums of partial Ls of segments forming loop
=
abL

Sij are -1 if exactly one of the currents in segments i and j is flowing opposite to the direction assumed when computing Lij, partial
85

aI

Onchip interconnect inductance

Partial inductance model
Partial inductance is used to represent the loop interactions without prior knowledge of actual loops Contains all information about magnetic coupling

PEEC model
Include partial inductance, capacitance, resistance Model IC interconnect for circuit simulation Has sufficient accuracy up to now
A two-parallel-line example

95

Onchip inductance extraction

To calculate partial inductance
Formula for two straight segments:
Assumptions: current evenly distributed

Analytical solution is quite involved even for simple geometry Numerical solution, such as Gaussian quadrature can be used, but much more time-consuming How about high-frequency effects ?
Skin effect; proximity effect Path of least impedance -> least loop L
Signal line & its return
06

Inductance extraction
Related research directions
Design solution to cope with inductive effects
Limited current loop; inductive effect is reduced, or easy to be analyzed (calculating partial L is costly) Simplify the problem

Use partial inductance (PEEC model)

Consider issues of circuit simulation Inductance brings dense matrix to circuit simulation; both extraction and simulation is expensive, if possible
s

Inductance extraction considering high-frequency

Beyond the onchip application MQS, EMQS, full-wave simulation
16

No L explicitly; just Z

No good locality as C Approaches of matrix sparsification

I R A V TA- G

I L V C

Frequency-dependent LR extraction
High frequency consideration
nonuniform current distribution affects R Extract R and partial L together Capacitive effects analyzed separately (MQS) Due to the interaction of magnetic field, values of L and R both rely on environments, like capacitance Problem formulation: Terminal pairs:
Impedance extraction:

Mutual resistance becomes visible at ultra-high frequency

26

Frequency-dependent LR extraction
FastHenry of MIT
Two assumptions: MQS; terminal pairs with known current direction Partitioned into filaments, current distributed evenly
Simplified PEEC

Z I b = Vb
Z = R + jwL
li Rii = ai

Lij =

Solve circuit equation !

36

Frequency-dependent LR extraction
FastHenry of MIT
Nodal analysis: Avoid forming Z-1: Mesh-based approach
A: incidence matrix Inverse of a dense matrix ! Much larger system M: mesh matrix

GMRES can be used to solve this system, with given Vs

YrVs = I s

Z r = Yr1

46

Frequency-dependent LR extraction
FastHenry of MIT
Multiple right-hand sides To solve: Multipole acceleration; preconditioning techniques

35 pins

30 pins

Application: package, wide onchip wires (global P/G, clock) Field solver ! Shortage: computational speed model inaccuracy; substrate ground plane
56

Problems of FastHenry
Lossy substrate discretization
Current direction is not clear Ground plane Huge # of unknowns ! Multilayer substrate

Segments are 1/3 actual width

With frequency increase

Filament # increases to capture skin, proximity effects

Used only under MQS assumption How to improve ?

Surface integral formulation (BEM)
66

Computational expensive !

Fundamentals of BEM
Governing equations

Inside alg. of FastImp of MIT

Maxwells equations are not in dispute

Two other equs usually known: Faradays law Amperes law

Constitutive equation for conductor

J ds =
S

V dv t
Inside each conductor:

Vector identity: E = ( E ) 2 E
76

Fundamentals of BEM
Equation in each conductor
Vector Holmholtz equ. General solution: Classification of PDE ?

With

86

Fundamentals of BEM
Equation in the homogeneous medium
Hold anywhere

A: Magnetic A = B , potential

Eind =

B t
Sum for all conductors

96

Fundamentals of BEM
Boundary conditions
Contact is artificially exposed surface
NC, C C

Hold due to assumption of no charge accumulation No transversal component of current into contact

C Here is surface charge density Totally 8 state variables:

NC C

Full wave simulation

07

Fundamentals of BEM
1
2

Fullwave analysis

1 , E1 ,

E1 n

2 , E2 ,

E 2 E 3 , E3 , 3 n n
7 8

Equation formulation

Discretization & E E E 4 , E4 , 4 5 , E5 , 5 6 , E6 , 6 unknown setting n n n

9
10

11

12

17

Fundamentals of BEM
Full wave
Complete Maxwells equations (no assumption)

Electro-Magneto-Quasistatics (EMQS)
Consider RLC Ignore the displacement current
G0 = 1 in medium equ. 4 r r
in conductor equ.
k1 = j i

Magneto-Quasistatics (MQS)
no Consider RL Ignore the displacement current

Three modes all are widebanded; they behave differently at high frequencies
27

FastImp
Algorithms in FastImp
Integral calculation
Singular, near-singular integral pFFT algorithm

Frequency-dependent multiple kernels

Scaling

Direct, interpolation, convolution, projection

size u is small Improve condition number

Preconditioning
Preconditioned GMRES

37

FastImp
Experiment results
A ring
MQS analysis

47

FastImp
Length: 2cm; separation: 50um

Experiment results

Cross-section: 50x50um2

Shorted transmission line EMQS, fullwave, 2D balanced T-Line MQS, FastHenry

57

Computational Results: Various Practical Examples

Slides courtesy Zhenhai Zhu, MIT

Computational Results: Various Practical Examples

10x3 Buses 9.5 min FastImp 340Mb 160 min Iterative 19Gb LU 136days 19Gb Stacked 9-turn Stacked 8-turn Circular spirals Rect. spirals 68 min 642 Mb 750 min 19 Gb 100 days 19 Gb 54 min 749 Mb 590 min 22 Gb 168 days 22 Gb
Slides courtesy Zhenhai Zhu, MIT

Inductance extraction
Reference
[1] M. W. Beattie and L. T. Pileggi, Inductance 101: modeling and extraction, in Proc. Design Automation Conference, pp. 323-328, June 2001. [2] M. Kamon, M. J. Tsuk, and J. K. White, Fasthenry: a multipoleaccelerated 3-D inductance extraction program, IEEE Trans. Microwave Theory Tech., pp. 1750 - 1758, Sep 1994. [3] Z. Zhu, B. Song, and J. White. Algorithms in Fastimp: a fast and wideband impedance extraction program for complicated 3-D geometries. IEEE Trans. Computer-Aided Design, 24(7): 981-998, July 2005. [4] W. Kao, C-Y. Lo, M. Basel and R. Singh, Parasitic extraction: Current state of the art and future trends, Proceedings of IEEE, vol. 89, pp. 729-739, 2001. [5] http://www.rle.mit.edu/cpg/research_codes.htm (FastCap, FastHenry, FastImp)

87