Shankar bhaktha / Art No.

eme573 1^12

capacitance, resistance, and inductance, so that a more

CAPACITANCE EXTRACTION
accurate circuit simulation can be performed.
With the increase in working frequency and develop-
WENJIAN YU
ment of silicon technologies, the discrepancy between the
ZEYI WANG
Tsinghua University microwave IC and the common VLSI circuit becomes
Beijing, China marginal. Therefore, the electromagnetic modeling and
accurate extraction of the interconnect parasitics have
become a subject of advanced research in both fields to
1. INTRODUCTION date. Among the three parasitic parameters, capacitance
has attracted the most attention because it greatly influ-
Since the early 1950s, microwave circuits have evolved ences time delay, power consumption, and the signal
from discrete circuits to planar integrated circuits, then to integrity and its calculation becomes complicated under
multilayered and three-dimensional integrated circuits. DSM technologies.
With the increased circuit density, the multiconductor line In the following sections, the fundamental theory and
in multilayered dielectric media has become the major contemporary methodology and algorithms of capacitance
form of the transmission line or interconnect. Multi- extraction will be discussed.
layered routing reduces the area as well as the volume
of the circuit. However, as a result, electromagnetic cou-
pling among conductors greatly influences circuit perfor- 2. PROBLEM FORMULATION
mance. In some microwave integrated circuits, this
coupling effect is utilized to construct compact circuit As is well known, the capacitor is a commonly used
components, under most circumstances it is regarded as component in electric or electronic equipment. It is usually
a parasitic effect that must be modeled accurately for composed of two conductors insulated from each other.
verification of the circuit’s validity and performance. When charged, the two surfaces of the conductor facing
In the related field of very-large-scale integration each other carry equal and opposite charges Q and –Q,
(VLSI) circuits, electromagnetic coupling among intercon- respectively (see Fig. 2). The electric potential difference
nects is also becoming increasingly important. With the between the two conductors f1–f2 is called the voltage of
introduction of deep-sub-micrometer (DSM) semiconduc- the capacitor and is always denoted by V. Experiments
tor technologies, the on-chip interconnect wire can no and theoretical analyses show that, for a capacitor, Q is
AU : 1 longer be considered as an equipotential form of coupling. always proportional to V and thus the ratio Q/V is a
The parasitic effects introduced by the wires display a constant determined by the structure of the capacitor.
scaling behavior that differs from that of active devices This ratio is called the capacitance of the capacitor and is
such as transistors, and these effects tend to gain impor- denoted by C: C ¼ (Q/V).
tance as device dimensions are reduced and circuit speed In the International System of Units (SI), the unit of
is increased. In fact, they begin to dominate some of the capacitance is the faraday (F). It expresses the capaci-
relevant metrics of digital integrated circuits such as tance of a capacitor that has one coulomb on one of its
speed, energy consumption, and reliability. A typical polar planes when the potential difference is 1 V. Other AU : 2
recursive design flowchart of a state-of-the-art integrated commonly used units of capacitance are mF (10
6F), pF
circuit (IC) is shown in Fig. 1, where a postlayout step (10
12F), and fF (10
15F).
termed parasitic extraction precedes gate-level simulation. The capacitance of some simple capacitor can be calcu-
The task of parasitic extraction is to model the electro- lated easily. For example, for the parallel-plate capacitor
magnetic effects of the wire with parasitic components of shown in Fig. 2, we have

Function Spec. e0 er S
C¼ ð1Þ
d
RTL Behavior Simul.

Logic Synth. Stat. Wire Model

1 +Q

Front-end Gate-level Net. Gate-level Simul.

d
r
Back-end Floorplanning
Parasitic Extraction
S
Place & Route

2 −Q

Layout

Figure 1. A typical flowchart of IC design. Figure 2. A parallel-plate capacitor.

1
 Shankar bhaktha / Art No. eme573 1^12

2 CAPACITANCE EXTRACTION

where e0 is the dielectric constant of free space and in SI, is Many conductor interconnect wires are involved in the
expressed as microwave IC and the common VLSI circuit, and they are
insulated by some dielectric such as oxide SiO2. The
capacitance between any two wires reflects the electro-
1 static coupling effect between these wires, and calculating
e0 ¼ ¼ 8:85  10
12 C2 =N . m2
4p  9  109 these capacitances with high accuracy is very important
for analysis of the circuit’s performance.
For an N-conductor system, such as the interconnect
where er is the relative permittivity of the insulating
wires in an IC, an N  N capacitance matrix [Cij]N  N is
material, S is the area of the plate, and d is the distance
defined by
between two parallel plates.
Specific capacitors widely used in the design of micro-
wave circuits include the interdigital capacitor and the X
N
Qi ¼ Cij Uj ; i ¼ 1; 2; . . . N; ð2Þ
metal–insulator–metal (MIM) capacitor. Figure 3 shows j¼1
the physical layout of an interdigital capacitor with nine
fingers, and Fig. 4 shows the cross-sectional view of an
MIM capacitor with the GaAs process. The interdigital where Cij (iaj) is the coupling capacitance between con-
capacitor works with the electrostatic coupling between ductors i and j, and Cii is the self-capacitance or total
the intercrossed fingers, and has a very high Q value. So, capacitance of conductor i. Qi is the induced charge on
it is widely used in the high-frequency microwave circuits. conductor i, and Uj is the electric potential of conductor j
The MIM capacitor has simple geometry and is easily (usually the known bias voltage).
fabricated, and its capacitance is controlled by the dimen- Figure 5 shows a typical crossover wires in the VLSI
sions of the polar planes. Since the interdigital capacitor system, where the coupling capacitances between any two
and the MIM capacitor are widely used, calculation of the conductors need to be calculated.
parameters of their structures within given the working Accurate modeling of the wire capacitances in a state-
frequency and corresponding capacitor value becomes an of-the-art integrated circuit is not a trivial task. It is
important issue for both design and optimization. This can further complicated by the fact that the interconnect
be regarded as the reverse procedure of capacitance ex- structure of contemporary integrated circuits is three-
traction. For further discussion of this issue, please refer dimensional (see Fig. 5). The capacitance of such a wire
to the literature [39,40]. is a function of its shape, environment, distance from the
Actually, the capacitor has a more generalized form substrate, and distance to surrounding wires. Generally
than that described above; actually, it consists of two SiO2 is the insulating material among interconnect wires
AU : 3 isolated conductors. The capacitance of a single conductor in integrated circuits, although some materials with lower
(conductor 1) is defined as if another conductor (conductor permittivity, and thus lower capacitance, are coming into
2) were located at an infinite distance away to form a joint use. The relative permittivity er of several dielectrics
capacitor (conductors 1 þ 2). For example, the capacitance commonly used in integrated circuits is presented in Table
of an isolated conductor sphere with radius of R can be 1. It should also be pointed out that er of air or vacuum is 1.
calculated as C ¼ 4pe0 R.
3. METHODOLOGY AND ALGORITHMS

With the advances in IC technology, the methodology of

capacitance extraction has evolved from one-dimensional
(1D), two-dimensional (2D), 2.5-dimensional (2.5D), to

Master conductor, IV

Neumann boundary

Figure 3. An interdigital capacitor.

z
15.00 30

30.00

Grounded substrate 3.00

SiN SiO2 GaAs Figure 5. A structure involving 2  2 crossover interconnect

wires.
Figure 4. An MIM capacitor (cross-sectional view).
 Shankar bhaktha / Art No. eme573 1^12

CAPACITANCE EXTRACTION 3

Table 1. Relative Permittivity of Several Commonly used Dielectric Materials

Alumina Silicon Nitride Glassepoxy Silicon Polyimides
Dielectric Material Silicon (Package) (Si3N4) (PCB) Dioxide (Organic) Aerogels
Relative permittivity (er) 11.7 9.5 7.5 5 3.9 3–4 B1.5

three-dimensional (3D) to meet the required accuracy. In Cfringe

this section, the 1D and 2D methods are briefly intro-
duced. Then, the 2.5-D method and the mechanism of the
modern commercial capacitance extraction tools that em- Carea
ploy the 3D capacitance extractor are presented. Finally,
Ground
we will discuss some details of algorithms of the 3D field
solver for capacitance extraction. Figure 6. A conductor above a ground plane (cross-sectional
view).

3.1. 1D and 2D Methods

From the formula for calculation of parallel-plate capaci- Fringing Parallel
tance [Eq. (1)], we can infer that the capacitance is Lateral
proportional to the overlapping area between the conduc-
tors and inversely proportional to their separation dis-
tance. This is very important for capacitance extraction
without a high degree of precision. Substrate
Figure 6 shows a typical microstrip structure, where
there is only a single rectangular conductor over a ground Figure 7. Capacitive coupling between wires in a multilayered
plane. This structure is very different from the above interconnect system.
parallel-plate model discussed because of the existence
of the capacitance between the sidewalls of the wire and wire. The area can be that from single layer or a combina-
the substrate, called the fringing capacitance. To avoid the tion of layer overlaps.
time-consuming numerical modeling of this geometry, an Usually, the 1D extraction method works well when the
approximate 1D method can be used as a good engineering number of interconnect layers is restricted to only one or
practice. The capacitance is assumed to be the sum of two two. However, the current process technology often in-
components: (1) a parallel-plate capacitance determined volves many more interconnect layers, and they are also of
by the vertical field between a wire of width w and the high density. So, several capacitance components of a wire
ground plane and (2) the fringing capacitance modeled by embedded in the multilayered interconnect system may
a cylindrical wire with radius equal to the conductor exist, other than the only capacitive coupling to the
thickness H. So, this simple and practical 1D formula ground plane (see Fig. 7). Each wire is coupled not only
becomes to the grounded substrate but also to the neighboring
wires on the same layer and on adjacent layers. Not all
e.w 2pe capacitive components terminate at the grounded sub-
C ¼ Carea þ Cfringe ¼ þ strate; actually a large number of them connect to other
d log ðd=HÞ
wires. These (fringing, lateral, parallel, etc.) capacitors
between wires not only form a source of noise (crosstalk
where w ¼ W
H/2 is a good approximation for the width
among signal lines) but also can have a negative impact on
of the parallel-plate capacitor (W is the width of the wire),
the circuit performance.
d is the distance between the ground plane and the bottom
To model the capacitance in the multilayered intercon-
of wire, and e is the permittivity of the insulating material.
nect system with higher accuracy, 2D capacitance extrac-
With this formula, we obtain the approximate capacitance
tion methodology was developed. In 2D capacitance
per unit length.
extraction, accurate geometry modeling and numerical
In another kind of 1D capacitance extraction, the area
techniques are implemented for the cross section of simu-
and perimeter parameters of interconnect geometries are
lated structure (as in Fig. 7). For the 2D region of di-
first obtained. Then, a fine-tuned set of area and perimeter
electrics, the electric field equation is solved with
weights per routing layer can be used to calculate capaci-
numerical techniques. 2D extraction ignores all three
tance values as an inner product [1]:
dimensional details and assumes that the geometries
being modeled are uniform in one dimension, usually the
C ¼ ðarea dimensions; perimeter dimensionsÞ signal propagation direction. Therefore, 2D capacitance
extraction is only suitable only for some special cases, such
. ðarea weight; perimeter weightÞ
as like the transmission line.

AU : 4 Such area and perimeter weights can be obtained by

precharacterization of an ‘‘average’’ environment of a
 Shankar bhaktha / Art No. eme573 1^12

4 CAPACITANCE EXTRACTION

The details of numerical techniques for solving the collected either to fit some empirical formulas or to
electric field will be introduced in Section 3.3, albeit in a build lookup tables (either type is called a ‘‘pattern
3D manner. library’’). In Ref. 3, analytical equations are used for
model fitting. A good fit would require fewer simula-
tion points. The number of patterns can be reduced
3.2. 2.5D Method and Commercial Capacitance Extraction
by pattern reduction techniques. Arora et al. [4]
Tool
present a pattern compression technique that re-
The 2.5D (also called qausi-3D) method goes a step further duces the total number of precharacterizaiton pat-
than 2D extraction. Its main idea is to calculate the terns. With this technology, the capacitance in some
capacitance of several cross sections (using the 2D layout pattern can be extrapolated from the capaci-
method) and combine the 2-D results into the final capa- tance values in two simpler precharacterization
citance value. patterns, without losing much accuracy. Capaci-
A typical 2.5D capacitance extraction method is also tance field solvers employ different numerical algo-
called the ‘‘(2  2)D method’’, in which any 3D structure is rithms, and they may give different answers for
swept in two perpendicular directions and by considering certain special layout structures depending on the
the geometry overlapping, 3D structure can be modeled problem setup and boundary conditions. Therefore,
more accurately (see Fig. 8). the precharacterizaiton software should have the
In Fig. 8, an m2 wire crosses an m1 wire. Along flexibility to incorporate any third-party field sol-
direction A, a 2D cross-sectional view is shown in the vers. This first step should be performed only once
middle. Along direction B, the other 2D cross section is per process technology. The challenge in this area
shown to the right. Solving the two orthogonal strictly 2D includes the handling of increasingly complex pro-
problems numerically, we obtain CA ¼ C1f1 þ C10 þ C1f2, CB cessing technology, such as low-k dielectric, air-
¼ C2f1 þ C20 þ C2f2 (see Fig. 8). Then, Cm1, m2 ¼ CA  w1 þ bubble dielectric, nonvertical conductor cross sec-
(CB
C20)  w2, where w1, w2 are the widths of wires m1 tions, conformal dielectric (see Fig. 9), and shallow
and m2, respectively. However, this method is still not very trench isolations.
accurate. The error could be more than 10%, especially for 2. Geometric Parameter Extraction. This is also an
coupling capacitance, which is very important for signal integral part of precharacterization. If a geometric
integrity analysis. pattern requires 10 parameters to describe, there is
Obviously, true 3D extraction is a straightforward a corresponding precharacterization of 1  510
method to achieve high precision. However, the 3D elec- (B10,000,000) patterns to simulate. This is assum-
trostatic Laplace equation must be solved numerically ing that five sample points are taken in each of the
within a complicated 3D structure. This consumes exten- 10 parameters, resulting in a 10-dimensional (10D)
sive computational effort. 3D capacitance extraction table of the dimensions given above. This is clearly
(usually called the ‘‘field solver’’) is actually not a trivial not feasible. On the other hand, if a geometric
extension of the 2D case. This aspect is discussed further pattern can be described by very few parameters,
in Section 3.3. then it is difficult for it to be accurate. In a full-chip
For the current task of capacitance extraction in mod- situation, the runtime of geometric parameter ex-
ern IC design, using the 3D extraction method directly is traction can be very time/space-consuming, with
impossible because of its huge expense of memory and millions of interconnect polygons to analyze. Time/
CPU time. To obtain a good tradeoff between accuracy and space-efficient geometric processing algorithms are
efficiency, modern capacitance extraction tools utilize spe-
cial techniques for the full-chip extraction task, which is
usually divided into three major steps: Conformal dielectric

1. Technology Precharacterization. Given a descrip-

tion of the process cross sections, tens of thousands
of test structures are enumerated and simulated
with 2D and/or 3D field solvers. These structures
are of medium dimensions. The resulting data are

w2
C1f1 C C1f 2 C2f1 C2o C2f 2
1o
B w1
m1
Figure 9. A realistic vertical cross section of IC interconnect. We
m2 see that conductors on layers 1–5 are trapezoidal, and there is a
conformal dielectric on top of the top layer metal (passivation).
Top view Cross section view A Cross section view B
(SEM photograph courtesy of IBM Corp. r Copyright IBM Corp.
Figure 8. 2.5D capacitance for a crossover structure. 1994, 1996.)
 Shankar bhaktha / Art No. eme573 1^12

CAPACITANCE EXTRACTION 5

very important. Habitz and Wemple [5] present a region [7]:

geometric parameter reduction technique in which
geometric parameters can be dramatically reduced
@2 u @2 u @2 u
by taking advantage of the shielding effect. Conduc- r2 u ¼ þ 2 þ 2 ¼0 ð3Þ
@x2 @y @z
tors two layers away from the main conductor of
interest do not require a precise description. This is
particularly useful for the very-deep-sub-micro- where u is the electric potential. This equation can be
meter geometry, where a very distant conductor transformed into different mathematical formulations.
mesh behaves like a large airplane. Then, various numerical methods are employed to solve
3. Calculation of Capacitance from Geometric Parame- it with different levels of efficiency.
ters. Here, the geometric parameters are matched to According to the domain of the above Laplace equation
some entries in the pattern library. Usually a full- (3), there are two models for capacitance extraction: (1) the
chip or full-path extraction task involves at least infinite-domain model, in which the electrostatic field
thousands of conductors. The whole structure is spreads to the infinite, resulting in an infinite problem
chopped into medium-size pieces first, which are space; and (2) the finite-domain model, where the electro-
then calculated with the pattern-matching approach static field is restricted within a finite domain, with the
described above. Finally, the capacitance values Neumann condition on the outer boundary [8]:
must be combined to get the desired result. ð@u=@nÞ ¼ 0. This means that electric field is not able to
spread out of the finite problem domain. The Neumann
condition is also called the reflective boundary condition,
One major source of error is called the pattern mis- and is introduced as the ‘‘magnetic wall’’ in Ref. 9. It
match, where extracted geometry parameters do not have should be pointed out that the infinite-domain model is
an exact match in the pattern library. At this time, there ideal for simulating isolated structures, but for the on-chip
are two remedies to perform the capacitance calculations. application it is not accurate because of the influence of
One method is to enhance the pattern library by running neighboring conductors. On the other hand, the finite-
field solvers at the full-chip extraction time. The other domain model considers a part cut from actual layout of
method is to employ heuristics to synthesize a solution VLSI circuit; it is suitable for the realistic capacitance
from closely matched precharacterization patterns. Even extraction of VLSI interconnects [8]. Now, both models of
if all the geometric patterns match the library completely, capacitance extraction are used in different applications,
there could still be discontinuities in the layout pattern and accordingly the numerical methods are also different.
decomposition, which is another source of error. This error The problems a numerical algorithm usually encountered
is analyzed in Ref. 6, where the error bound was obtained in modeling are discussed below.
by utilizing the ‘‘empty’’ and ‘‘full’’ boundary conditions. Classifications of the 3D field solver methods include
the domain discretization method, the boundary integral
3.3. Algorithms for 3D Field Solver equation method, semianalytical approaches, and the
stochastic method. The domain discretization method
The 3D method can be used model the actual geometry includes the finite-difference method (FDM) [10], finite-
accurately, so it behaves with the highest precision. 3D element method (FEM) [11], and the method of the
capacitance extraction becomes increasingly important measured equation of invariance (MEI) [13,14]. The
under the DSM technology of VLSI circuit, although boundary integral equation method includes the method
presently it is used widely only as a library-building tool of moment [15], indirect boundary element method (BEM)
in the industry. More recently, much research work has [8,17–27], and direct boundary element method [28–34].
been devoted to improve the efficiency of the 3D extraction The semianalytical approaches combine the analytical
method. Related papers are published on the annually formulas and some traditional numerical methods [9,35–
held conferences (Design Automation Conf., Int. Conf. 37]. The stochastic method is based on statistical theory
Computer-Aided Design, etc.) and many academic journals [38].
(IEEE Trans. Microwave Theory Tech., IEEE Trans. Com- FDM and FEM discretize the entire 3D domain, thus
put. Aided Design, etc.). To date, some 3D extraction producing a linear algebra system with large order; hence
algorithms have been developed to integrate with the the computational speed of these methods is greatly
commercial software of some electronic design automation limited. However, since both methods are relatively well
(EDA) companies in the Silicon Valley (in California). established, they are still used in the industry as a
Research on 3D capacitance extraction is still advancing reference tool with accurate values calculated under fine
very rapidly. grids. For example, the famous software of 23D capacitance
In this section, the principles and mainstream techni- extraction ‘‘Raphael’’ utilizes FDM, and the ‘‘SpiceLink’’ of AU : 5
ques of the 3D field solver are introduced. More cutting- Ansoft Corp. is based on FEM.
edge techniques are mentioned with related references. Since the mid-1990s, the boundary integral equation
method has begun to replace the domain discretization
3.3.1. Overview. For a system involving multiple con- method because of its high performance. In both indirect
ductors (see Fig. 5), with one conductor setting 1 V and and direct BEM, only the 3D domain boundary is discre-
others 0 V, the electrostatic equation (called the Laplace tized, and a smaller system of linear equations is obtained.
equation) need to be solved with a homogenous dielectric Problems encountered with the complex boundary can be
 Shankar bhaktha / Art No. eme573 1^12

6 CAPACITANCE EXTRACTION

effectively handled with BEM, whose accuracy is superior conductor panel, the normal derivative of the potential
to that of FEM as well. Thus, the BEM with rapid satisfies
computating techniques has become the focus of research
on the 3D field solver. @u þ ðxÞ @u
ðxÞ
ea ¼ eb ð7Þ
@na @na
3.3.2. Indirect Boundary-Element Method. The indirect
boundary method can be regarded as a variation of the with xAinterface of ea and eb at any point x on a dielectric
method of moments (MoM). Because only the domain interface. Here na is the normal to the dielectric interface
boundary needs to be discretized, the indirect BEM in- at x that points into dielectric a and ea and eb are the
volves much fewer unknowns than does FDM or FEM. permittivities of the corresponding homogenous dielectric
However, it leads to a dense coefficient matrix, whose region; u þ (x) is the potential at x approached from the
formation and solution introduce many difficulties. The side of the interface ea , and u
(x) is the analogous
innovation of the multipole acceleration method, the potential for the b side.
singular-value decomposition (SVD) method, and the hier- For the multidielectric problem, the so-called total-
archical method has made the indirect BEM more applic- charge Green function approach presented above involves
able. Now, indirect BEM combined with a fast more unknowns at the interfaces. Another choice to deal
computational technique has become a main choice for with the problem is to employ the multilayered Green
the 3D field solver. function. Then, only the free charge density on the con-
The indirect BEM method is also called the equivalent ductor surfaces needs to be considered as an unknown
charge method, whose boundary integral equation in- function. However, to evaluate the Green function for the
volves the surface charge density sðx0 Þ as an unknown multilayered medium, infinite summations are involved,
function which is very time-consuming. Oh et al. [20] derived a
Z closed-form expression of Green’s function for the multi-
uðxÞ ¼ Gðx; x0 Þsðx0 Þda0 ðx 2 GÞ ð4Þ layered medium by approximating the Green function
G using a finite number of images in the spectral domain.
This greatly reduces the computational task. Li et al. [22]
where Gðx; x0 Þ is Green’s function. For free space, presented for the first time the general analytical formu-
Gðx; x0 Þ ¼ 1=jjx
x0 jj; G is the boundary surface. After sol- las for the static Green functions for shielded and open
ving the surface charge density sðx0 Þ, the charge on con- arbitrarily multilayered media. Zhao et al. [21] an efficient
ductor i can be calculated with scheme for the generation of multilayered Green functions
Z using a generalized image method presented. The multi-
layered Green function is much more complicated than
Qi ¼ sðx0 Þda0 ð5Þ
Sd ðiÞ the free-space Green function; it is applicable only to the
simple stratified structure of multiple dielectrics, while for
where Sd(i) is the surface of conductor i. We discretize the more complex structures, such as the conformal dielectric,
surfaces of m conductors into n constant elements (or the deduction of Green’s function may be impossible.
panels); then the potential at the center of the kth panel More research work has been undertaken to accelerate
xk can be expressed as a sum of the contributions of all the the capacitance extraction using the total-charge Green’s
panels function approach. In 1991, Nabors et al. applied the
multipole accelerated (MPA) method successfully, pro-
n Z
X posed earlier by Greengard and Rokhlin [16], to 3D
sj ðx0 Þ
uk ¼ 0
da0 capacitance extraction with the indirect BEM. In the
j¼1 Gj kx
xk k
MPA method, calculation of the interaction between
charges [i.e., the coefficients in (6)] is divided into two
where sj ðx0 Þ is the surface charge density of panel j (Gj ). parts: the near-field computation and the far-field compu-
Substituting the known boundary conditions, we obtain a
dense linear algebra equation.

Pq ¼ b ð6Þ
n2 charge points
where the coefficient matrix P is dense and nonsymmetric. r
R
The Krylov subspace iterative method, such as the gen- i
eralized minimal residual algorithm (GMRES) [2], is
usually used to solve this equation. ri
For a problem involving multiple dielectrics, the polar-
ization charge density on the dielectric interface needs to
be introduced, which contributes to the potential distribu-
tion together with the free charge density on conductor n1 evaluation points
surfaces. Therefore, the problem becomes equivalent to
that in the free space and the simple free-space Green Figure 10. Evaluation point potentials are approximated with a
function is used to form Eq. (4). Except for Eq. (4) on each multipole expansion [17].
 Shankar bhaktha / Art No. eme573 1^12

CAPACITANCE EXTRACTION 7

tation. For the near-field computation, the coefficients are BEM method is generally used to deal with the finite-
calculated directly; for the far-field computation, the domain model of capacitance extraction.
multipole expansion and local expansion are used to Within the finite domain that is involved in capacitance
expedite the computation. Therefore, the CPU time of extraction (see Fig. 11), the electric potential u satisfies
forming and solving (6) with the iterative equation solver the following Laplace equation with mixed boundary
is greatly reduced. Figure 10 illustrates of the multipole conditions [32]
expansion. Nabors and White [18], developed the adap-
8
tive, preconditioned MPA method. The corresponding soft- > e r2 u ¼ 0; in Oi ði ¼ 1; . . . ; MÞ
>
< i
ware prototype FastCap is shared on the MIT Website,
and has become a popular tool of capacitance extraction u ¼ u0 ; on Gu ð8Þ
>
>
for relevant researchers. To date, the capacitance extrac- :
q ¼ @u=@n ¼ q0 ¼ 0; on Gq
tion using the MPA indirect BEM is still undergoing
M
research [25]. where the whole domain O ¼ [ Oi , where Oi stands for the
In 1998, a fast hierarchical algorithm for 3D capaci- space possessed by the ith dielectric. Gu represents the
tance extraction was proposed at the Design Automation Dirichlet boundary (conductor surfaces), where u is
Conference, and was reprinted in a journal article [24]. known as the bias voltages; Gq represents the Neumann
Similar to the multipole algorithm, it is also based on fast boundary (outer boundary of the simulated region), where
computation of the ‘‘N-body’’ problem. For the singular the electric flux q is supposed to be zero. Here n denotes
integral kernel of 1=jjx
x0 jj, it can achieve high accelera- the unit vector outward normal to the boundary. At the
tion of computation, and only O(N) operations are needed dielectric interface, the compatibility equation (7) holds.
for each iteration. For other weaker-singular kernels, the With the fundamental solution as the weighting func-
efficiency of this method may be reduced. In 1997, Kapur tion, the Laplace equations in (8) are transformed into the
et al. and Long [19] proposed an accelerated method based following direct BIEs by the Green identity [12]
on the singular-value decomposition (SVD) method that is
independent of the kernel and based on the Galerkin Z Z
method using the pulse function as the basis function. It cs uis þ q ui dG ¼ u qi dG ði ¼ 1; . . . ; MÞ
@Oi @Oi
requires an O(N) times operation to construct the coeffi-
cient matrix and O(N log N) operations to perform an
iteration. The precorrected fast Fourier transform (FFT) where uis is the electric potential at collocation point s (in
algorithm [23] has the same computational complexity, dielectric region i) and cs is a constant dependent on the
while it is based on the collocation method for discretiza- boundary geometry near to the point s. u ¼ 1=4pr is the
tion. fundamental solution of the 3D Laplace equation, whose
These studies on capacitance extraction with indirect derivative along the outward normal direction n is
BEM all handle the infinite-domain model. In 1996, Wang q ¼ @u =@n ¼
ðr; nÞ=4pr3 , r is the distance from the
et al. [8] improved the multipole accelerated indirect collocation point to the point on G, and qOi is the boundary
BEM, enabling it to handle the finite-domain problem that surrounds dielectric region i.
and also proposed a parallel multipole accelerated 3D Employing the collocation method after discretizing the
capacitance simulation method based on nonuniformed boundary, such as that in the indirect BEM, we obtain
cube partition. system of linear equations [32]:
Other fast computational methods for indirect BEM
include those based on wavelets [26] and the multiscale Ax ¼ f ð9Þ
method [27].
Finally, with the preconditioned Krylov iterative equation
solver, such as the GMRES algorithm [2], the normal
electric field intensity on the conductor surface is obtained
3.3.3. Direct Boundary-Element Method. The direct [32].
BEM is based on the direct boundary integral equation In direct BEM, variables of both potential and field
(BIE), and is suitable for solving the 3D Laplace equation intensity are involved; thus two kinds of integral kernels
with varied boundary conditions [12]. However, the direct are found. Although this is more complex than the indirect
BEM method, direct BEM has its own advantages: (1) it is
suitable for capacitance extraction within the finite do-
Conductor Neumann boundary main since two variables are included, and (2) because the
variables in each BIE are within the same dielectric
3 region, it has a ‘‘localization’’ characteristic, which leads
to a sparse linear system for problem with multiple di-
2 electrics.
1 In direct BEM, a great deal of time and memory are
consumed in forming and solving the system of discretized
Substrate BEM equations. Wang et al. continued the research work
Figure 11. A structure with three dielectrics (cross-sectional of Fukuda [28] on 2D capacitance extraction using direct
view). BEM, extending it to the 3D structure of VLSI intercon-
 Shankar bhaktha / Art No. eme573 1^12

8 CAPACITANCE EXTRACTION

nects [32]. An efficient analytical/semianalytical integra- 3.3.4. Semianalytical Approaches. Semianalytical ap-
tion scheme was used to accurately calculate the boundary proaches have been proposed as a solution for 3D capaci-
integrals under the VLSI planar process. This method tance extraction. Basically, they take certain special
achieves high computational speed and accuracy when procedures and reduce the original problem by one dimen-
forming Eq. (9) [32]. In 1996, Bachtold et al. [29] extended sion, such as using domain decomposition. Since some
the multipole method to handle the ‘‘potential boundary subdomains with specific geometry symmetry can be
integral’’ (whose kernel is 1/r3) in the direct BEM. They handled using the analytical formula, these approaches
discussed the model of multiple dielectrics within the have very high computational speed as well as much less
infinite domain. In 1999, Gu et al. extended the fast memory usage. Another characteristic of these approaches
hierarchical method used in the indirect BEM and made is that the FDM is often used for the general and compli-
it feasible to apply it for direct-BEM-based capacitance cated subdomain. That is why these approaches are some-
extraction [30]. times considered as improvements over the finite-
In 2000, Yu et al. proposed a quasimultimedium (QMM) difference method.
method, based on the localization characteristic of direct The semianalytical approaches include the dimension-
BEM [32]. The QMM method exploits the sparsity of the reduction technique (DRT) [9] and techniques based on
resulting coefficient matrix when handling the multidi- the domain decomposition method [35–37]. The principles
electric problem. Together with the efficient equation of the latter two techniques will be briefly discussed as
organization and iterative solving technology, the QMM follows.
accelerated method has greatly reduced the computing
time and memory usage. Figure 12 shows that a typical 3D
interconnect capacitor with five dielectric layers is cut into
3.3.4.1. Dimension Reduction Technique. The DRT at-
5  3  2 fictitious medium regions. The QMM method
tempts to solve problems within the finite domain. Most
has been successfully applied to actual 3D multidielectric
VLSI interconnects have stratified structures, and every
capacitance extraction [32,34]. For the finite-domain mul-
layer is homogeneous along the direction perpendicular to
tidielectric problem, the QMM-based method has shown a
the interfaces of the layers (denoted as the z direction; see
10  higher computation speed and memory saving over
Fig. 13). The DRT takes full advantage of this fact. It first
the multipole approach (FastCap 2.0) with comparable
partitions the whole structure according to these homo-
accuracy [34].
geneous layers. Then, for each layer the 3D Laplace
Another kind of field solver, called the ‘‘global ap-
equation can be reduced to a 2D Helmholtz equation,
proach,’’ does not solve the resulting linear system in the
which is solved with the most efficient method (including
usual way. The global approach discretizes the field equa-
the analytical formula) according to the arrangement of
tions and converts them to a circuit network of resistors or
the conductors. Finally, the solutions for these cascading
capacitors. Finally, with circuit reduction or matrix com-
2D problems are combined together to yield the final
putation, the whole resistance or capacitance matrix can
result.
be obtained directly. In 1997, Dengi of Carnegie Mellon
For the finite-domain problem of the ith layer with Eq.
University proposed a global approach (called ‘‘macromo-
(8), denote W ðiÞ ðx; y; Vc Þ as a linear function of x, y and the
del’’ method) for 2D interconnect capacitance extraction
bias voltage setting on conductors (denoted by vector Vc ),
based on direct BEM [31]. More recently, Lu et al. success-
and let
fully extended the concept of boundary element macro-
model to the 3D case, and developed a rapid hierarchical
block boundary element method (HBBEM) for intercon-
nect capacitance extraction [33]. uðiÞ ¼ vðiÞ þ W ðiÞ ðx; y; Vc Þ:

If there exists a function such as W ðiÞ ðx; y; Vc Þ, that

Neumann boundaries,
where electrical flux is 0
y
Dielectric layers
z
z

Master conductor, 1 V x
(Other conductors are with 0V)
Conductor Dielectric
Figure 12. A typical 3D interconnect capacitor with five di-
electric layers is cut into 3  2 structure. Figure 13. A 3D interconnect capacitor and the stratified layers.
 Shankar bhaktha / Art No. eme573 1^12

CAPACITANCE EXTRACTION 9

function vðiÞ satisfies lapped subdomains. Then, a global iteration is used for the
solution. Its principles are discussed below [35].
8 2 ðiÞ Consider a 3D finite domain Laplace problem with the
>
> r v ðx; y; zÞ ¼ 0 Dirichlet boundary condition
<
vðiÞ ðx; y; zÞ ¼ 0; ðx;yÞ 2 GðiÞ
u (
>
>
r2 u ¼ 0; ðx; y; zÞ 2 O
: ðiÞ
@v ðx; y; zÞ @n ¼ 0; ðx; yÞ 2 GðiÞ
q 
uG ¼ gðx; y; zÞ

then from the method of separation of variables, the Assume that the problem domain O involves two over-
general solution of v(i) is lapping subdomains O1 and O2 (see Fig. 14), and denote Gj
and Lj as the outer boundary and fictitious boundary of
Oj ðj ¼ 1; 2Þ, respectively. Then, the Schwarz alternating
X
vðiÞ ðx; y; zÞ ¼ ðiÞ
Tm ðx; yÞLðiÞ method is represented as
m ðzÞ
m¼1
8
>
> r2 ui1þ 1 ¼ 0; ðx; y; zÞ 2 O1
<
where Tm ðiÞ
is the mode function fulfilling the Helmholtz ui1þ 1 ¼ ui2 ; ðx; y; zÞ 2 L1
>
>
equation and LðiÞ : iþ1
m can be solved analytically [9]. u1 ¼ gðx; y; zÞ; ðx; y; zÞ 2 G1
L1
According to the conductor arrangement in the layer
and the preceding analysis, the layer slices are classified 8
>
> r2 ui2þ 1 ¼ 0; ðx; y; zÞ 2 O2
as follows: <
ui2þ 1 ¼ ui1þ 1 ; ðx; y; zÞ 2 L2
>
>
: iþ1
u2 ¼ gðx; y; zÞ; ðx; y; zÞ 2 G2
L2
1. An Empty layer or a layer containing some simple
conductors (such as that involving straight lines
with i ¼ 0; 1; 2; . . ., where u0 is the initial value for itera-
penetrating the structure) for which the linear
tion. In each iterative step, the known values of u on L1
function W and the analytical solution of the Helm-
are used to solve the field of subdomain O1 . Then, the field
holtz equation both exist.
of subdomain O2 is resolved with the u obtained on L2 . The
2. The layer for which the linear function W exists, discrepancy of u on L1 between two adjacent iterative
allowing the corresponding 3D problem to be trans- steps is used as the criterion of convergence. A relaxation
ferred into the 2D Helmholtz equation. factor o can be introduced to these formulas to accelerate
3. A complex layer for which the W function does not the convergence. It is also obvious that the convergence
exist. The 3D Laplace equation must be solved, but rate of the Schwarz alternating method is closely related
only the 2D finite-difference grid is utilized because to the size of the overlapping region. Usually the iteration
of the geometry symmetry along the z direction. error decreases exponentially with increase in the ratio of
the overlapping domain over the subdomain [35].
It is straightforward to extend the preceding formulas
The main drawback of the DRT is that the geometry it of two subdomains to the generalized case with more
employs has some limitations; For instance, it is difficult to subdomains. In each iterative step an analysis similar to
apply DRT to nonplanarized structures. So, for general- that used in DRT can be employed to achieve high
ized and complicated interconnect structures using the efficiency. In the actual application to capacitance extrac-
DSM technology, the efficiency of DRT is not guaranteed. tion, the iteration sequence and selection of relaxation
factor need to be considered. Figure 15 shows a cross-

3.3.4.2. Domain Decomposition Method. The domain

z
decomposition method (DDM) is a newly developed nu-
merical method. It can be subgrouped into the overlapping D9
domain decomposition method (ODDM) and the nonover-
D8
lapping domain decomposition method (NDDM). The for-
mer is also called the Schwarz alternating method and the D7
latter, the Dirichlet–Neumann alternating method. D6
ODDM partitions the whole structures into some over- D5
D4
D3
Γ1 Λ2 Λ1 Γ2
D2
D1
Ω1 Ω2
x
Figure 14. Two overlapping subregions. Figure 15. Four conductors embedded in nine dielectric layers.
 Shankar bhaktha / Art No. eme573 1^12

10 CAPACITANCE EXTRACTION

sectional view of an interconnect capacitor with nine tional performance must be improved. The adaptive
layers, and the domain partition scheme is illustrated. algorithm and stable element partition scheme will
In the NDDM technique, the decomposed subdomains be the focus of research in the future.
do not overlap each other, while the iteration algorithm is 3. Mixed-signal integrated circuits have been demon-
similar to that in ODDM; the difference is that in the strated to provide high-performance system solu-
adjacent subdomains the problem is solved with the tions for various applications such as wireless
Dirichlet boundary condition and the Neumann boundary communications. Also, the silicon-based CMOS tech-
condition, respectively, in the NDDM. In NDDM, there are nology is increasingly widely used because of the
fewer unknowns in the subdomain, and sometimes only fabrication cost advantage. To consider the signifi-
2D discretization is needed for a simple subdomain with cant impact of the lossy nature of the silicon sub-
homogeneous structure. However, the convergence rate of strate on the on-chip interconnects of the mixed-
NDDM is slower than that of ODDM [36]. signal ICs, the frequency-dependent parameters of
Research on capacitance extraction based on the do- interconnects in high-speed circuits must be ex-
main decomposition method is still underway. More recent tracted accurately. Defining the complex permittiv-
progress can be found in Ref. 37. ity of a material, the parasitic capacitance and
conductance in a frequency-dependent model can
3.3.5. Other Methods. The measured equation of invar- be extracted using methods similar to that employed
iance (MEI) method can be considered as a variation of for traditional capacitance extraction. The most
FDM. To solve the infinite-domain model of capacitance efficient algorithms for frequency-dependent capaci-
extraction, the MEI method terminates the meshes very tance extraction should be considered.
close to the object conductors and still preserves the
sparsity of the finite-difference (FD) equations. The geo-
metry-independent measured equation of invariance (GI- Acknowledgment
MEI) is proposed for the capacitance extraction of the The authors would like to thank Prof. W. Hong, Southeast
general 2D and 3D interconnects by using the free-space University, Nanjing, China, for much helpful advice.
Green function only [13]. The MEI method has now been
developed to the on-surface level, where a surface mesh is
used to minimize the number of unknowns [14]. The BIBLIOGRAPHY
stochastic method is based on the random-walk theory
and can effectively handle complex 3D structures. Its most 1. W. H. Kao, C. Lo, M. Basel, and R. Singh, Parasitic extraction:
recent progress can be found in Ref. 38. Current state of the art and future trends, Proc. IEEE
89(5):729–739 (2001).
2. Y. Saad and M. H. Schultz, GMRES: A generalized minimal
4. PERSPECTIVE residual algorithm for solving nonsymmetric linear systems,
SIAM J. Sci. Stat. Comput. 7(3):856–869 (1986).
In this article, we reviewed the state of the art in 3. U. Choudhury and A. Sangiovanni-Vicenelli, Automatic gen-
capacitance extraction techniques. These methods are eration of analytical models for interconnect capacitances,
discussed mainly for the accurate analysis of VLSI inter- IEEE Trans. Comput. Aided Design 14(4):470–480 (1995).
connects. However, they can also be easily to applied to 4. N. D. Arora, K. V. Raol, R. Schumann, and L. M. Richardson,
computer-aided design of microwave ICs. With the devel- Modeling and extraction of interconnect capacitances for
opment of IC technologies, the following issues related to multilayer VLSI circuits, IEEE Trans. Comput. Aided Design
capacitance extraction are important: 15(1): 58–67 (1996).
5. P. A. Habitz and I. L. Wemple, A simpler, faster method of
1. 3D capacitance extraction (i.e., 3D field solution) has parasitic capacitance extraction, Electron. J. 11–15 (Oct.
1997).
the highest computational accuracy, and is suitable
for complex interconnect structure under the DSM 6. E. A. Dengi, A Parasitic Capacitance Extraction Method for
technologies. Many accelerating techniques have VLSI Interconnect Modeling, Ph.D thesis, Carnegie Mellon
Univ., March 1997.
been developed to improve its speed. However, it is
yet not feasible to use the 3D field solver directly in 7. J. D. Jackson, Classical Electrodynamics, Wiley, New York,
1975.
the full-chip extraction task. More effort should be
8. Z. Wang, Y. Yuan, and Q. Wu, A parallel multipole accelerated
devoted to improving the computational speed of the
3-D capacitance simulator based on an improved model, IEEE
3D field solver, or to develop special techniques for
Trans. Comput. Aided Design 15(12):1441–1450 (1996).
the full-chip task. The full-chip extraction method
9. W. Hong, W. Sun, and Z. Zhu, A novel dimension-reduction
employing the 3D field solver would give both high
technique for the capacitance extraction of 3-D VLSI inter-
computational speed and high accuracy. connects, IEEE Trans. Microwave Theory Tech. 46(8):1037–
2. Currently, few 3D capacitance extraction methods 1043 (1998).
can be ‘‘tuned’’ for performance versus accuracy. The 10. A. Seidl, M. Svoboda, et al., CAPCAL-A 3-D capacitance
error estimation of the boundary-element method is solver for support of CAD systems, IEEE Trans. Comput.
also not established for practice. To make the 3D Aided Design 7(5):549–556 (1988).
field solver suitable for various applications, its 11. T. Chou and Z. J. Cendes, Capacitance calculation of IC
flexibility in tradeoff of accuracy versus computa- packages using the finite element method and planes of
 Shankar bhaktha / Art No. eme573 1^12

CAPACITANCE EXTRACTION 11

symmetry, IEEE Trans. Comput. Aided Design 13(9):1159– 27. J. Tausch and J. White, A multiscale method for fast capaci-
1166 (1994). tance extraction, Proc. IEEE/ACM Design Automation Conf.
12. C. A. Brebbia. The Boundary Element Method for Engineers, 36:537–542 (1999).
Pentech Press, London, 1978. 28. S. Fukuda, N. Shigyo, et al., A ULSI 2-D capacitance simu-
13. W. Sun, W. W. Dai, and W. Hong, Fast parameter extraction of lator for complex structures based on actual processes, IEEE
general interconnects using geometry independent measured Trans. Comput. Aided Design 9(1):39–47 (1990).
equation of invariance, IEEE Trans. Microwave Theory Tech. 29. M. Bachtold, J. G. Korvink, and H. Baltes, Enhanced multi-
45(5):827–835 (1997). pole acceleration technique for the solution of large possion
14. Y. W. Liu, K. Lan, and K. K. Mei, Computation of capacitance computations, IEEE Trans. Comput. Aided Design
matrix for integrated circuit interconnects using on-surface 15(12):1541–1546 (1996).
MEI method, IEEE Microwave Guided Wave Lett. 9(8):303– 30. J. Gu, Z. Wang, and X. Hong, Hierarchical computation of 3-D
304 (1999). interconnect capacitance using direct boundary element
15. R. F. Harrington, Field Computation by Moment Methods, method. Proc. IEEE Asia South Pacific Design Automation
Macmillan, New York, 1968. Conf. 2000, Vol. 6, pp. 447–452.
16. L. Greengard and V. Rokhlin, A fast algorithm for particle 31. E. A. Dengi and R. A. Rohrer, Boundary element method
simulations, J. Comput. Phys. 73:325–348 (1987). macromodels for 2-D hierarchical capacitance extraction,
17. K. Nabors and J. White, FastCap: A multipole accelerated 3-D Proc. IEEE/ACM Design Automation Conf. 35:218–223
capacitance extraction program, IEEE Trans. Comput. Aided (1998).
Design 10(11):1447–1459 (1991). 32. W. Yu, Z. Wang, and J. Gu, Fast capacitance extraction of
actual 3-D VLSI interconnects using quasi-multiple medium
18. K. Nabors and J. White, Multipole-accelerated capacitance
extraction algorithms for 3-D structures with multiple di- accelerated BEM, IEEE Trans. Microwave Theory Tech.
electrics, IEEE Trans. Circ. Syst. I: Fund. Theory Appl. 51(1):109–120 (2003).
39(11):946–954 (1992). 33. T. Lu, Z. Wang, and W. Yu, Hierarchical block boundary-
element method (HBBEM): A fast field solver for 3-D capaci-
19. S. Kapur and D. Long, IES3: A fast integral equation solver
tance extraction, IEEE Trans. Microwave Theory Tech.
for efficient 3-dimensional extraction, Proc. IEEE/ACM Int.
Conf. Comput. Aided Design 34:448–455 (1997). 52(1):10–19 (2004).
20. K. S. Oh, D. Kuznetsov, and J. E. Schutt-Aine, Capacitance 34. W. Yu and Z. Wang, Enhanced QMM-BEM solver for three-
computations in a multilayered dielectric medium using dimensional multiple-dielectric capacitance extraction within
the finite domain, IEEE Trans. Microwave Theory Tech.
closed-form spatial green’s functions, IEEE Trans. Microwave
Theory Tech. 42(8):1443–1453 (1994). 52(2):560–566 (2004).
21. J. Zhao, W. W. M. Dai, et al., Efficient three-dimensional 35. Z. Zhu, H. Ji, and W. Hong, An efficient algorithm for the
extraction based on static and full-wave layered Green’s parameter extraction of 3-D interconnect structures in the
VLSI circuits: domain-decomposition method, IEEE Trans.
functions, Proc. IEEE/ACM Design Automation Conf.
35:224–229 (1998). Microwave Theory Tech. 45(7):1179–1184 (1997).
22. K. Li, K. Atsuki, and T. Hasegawa, General analytical solu- 36. Z. Zhu and W. Hong, A generalized algorithm for the capaci-
tion of static Green’s functions for shielded and open arbi- tance extraction of 3-D VLSI interconnects, IEEE Trans.
Microwave Theory Tech. 47(10):2027–2030 (1999).
trarily multilayered media, IEEE Trans. Microwave Theory
Tech. 45(1):2-8 (1997). 37. V. V. Veremey and R. Mittra, Domain decomposition approach
23. J. R. Phillips and J. K. White, A precorrected-FFT method for for capacitance computation of nonorthogonal interconnect
electrostatic analysis of complicated 3-D structures, IEEE structures, IEEE Trans. Microwave Theory Tech. 48(9):1428–
1434 (2000).
Trans. Comput. Aided Design 16(10):1059–1072 (1997).
38. A. Brambilla and P. Maffezzoni, A statistical algorithm for 3D
24. W. Shi, J. Liu, N. Kakani, and T. Yu, A fast hierarchical
algorithm for three-dimensional capacitance extraction, capacitance extraction, IEEE Microwave Guided Wave Lett.
IEEE Trans. Comput. Aided Design 21(3):330–336 (2002). 10(8):304–306 (2000).
25. Y. C. Pan, W. C. Chew, and L. X. Wan, A fast multipole- 39. I. Bahl, Lumped Elements for RF and Microwave Circuits,
Artech House, 2003.
method-based calculation of the capacitance matrix for multi-
ple conductors above stratified dielectric media, IEEE Trans. 40. L. Zhu and K. Wu, Accurate circuit model of interdigital
Microwave Theory Tech. 49(3):480–490 (2001). capacitor and its application to design of new quasi-lumped
26. N. Soveiko and M. S. Nakhla, Efficient capacitance extraction miniaturized filters with suppression of harmonic resonance,
IEEE Trans. Microwave Theory Tech. 48(3):347–356 (2000).
computations in wavelet domain, IEEE Trans. Circ. Syst. I:
Fund. Theory Appl. 47(5):684–701 (2000).