INTERNATIONAL JOURNAL OF CIRCUIT THEORY AND APPLICATIONS
Int. J. Circ. Theor. Appl. 2004; 32:471–486
Published online in Wiley InterScience (www.interscience.wiley.com). DOI: 10.1002/cta.279

A reduction technique of large-scale RCG interconnects in thecomplex frequency domain
Y. Yamagami1 , Y. Tanji2 , A. Hattori1 , Y. Nishio1 and A. Ushida1; ∗; †1 Department of Electrical and Electronic Engineering; Tokushima University; Tokushima 770-8506; Japan
2 Faculty of Engineering; Kagawa University; 761-0396; JapanSUMMARY
High-speed digital LSI chips usually consist of many sub-circuits coupled with multi-conductor interconnects embedded in the substrate. They sometimes cause serious problems of the fault switching
operations due to the time-delays, crosstalks, reections, etc. In order to solve these problems, it is very
important to develop a user-friendly simulator for the analysis of LSIs coupled with interconnects. In
this paper, we consider a large-scale gate-array circuit coupled with multi-conductor RCG interconnects.
At rst, we propose a new method for calculating the dominant poles of the impedance matrix, whichgive the large eects to the transient response. The corresponding residues are estimated by the leastsquares method. Using these poles and residues, the input–output relation of each interconnect can be
described by the partial fractions. After then, the interconnect is replaced by the equivalent circuit realizing the partial fractions. In this way, we can easily develop a user-friendly simulator familiar withSPICE. We found from many examples that the good results can be obtained using only few dominantpoles around the origin. Furthermore, the reduction ratio of our method is very large especially forlarge scale interconnects. Copyright ? 2004 John Wiley & Sons, Ltd.
KEY WORDS:

IC interconnects; exact poles and residues; reduction algorithm; complex frequency
domain; SPICE simulator; asymptotic equivalent circuit; passivity

1. INTRODUCTION
The analysis and design of high-speed LSI chips are becoming more and more important,because the LSI chips coupled with interconnects embedded in the substrate sometimes cause
the fault switching operations due to the signal delays, crosstalks, reections, etc [1–9]. The
Elmore resistance–capacitance (RC) delay metric is popular due to its simple closed-form
expression, computation speed and delity with respect to the simulation [4]. The closed-form
combining the delay and crosstalk is rstly shown in Reference [5]. The improved techniques[6–9] are proposed later for improving the accuracy and the practical applications in thesimulations.
∗ Correspondence

to: Akio Ushida, Department of Electrical and Electronic Engineering, Tokushima University,
Tokushima 770-8506, Japan.
† E-mail: ushida@ee.tokushima-u.ac.jp

Copyright ? 2004 John Wiley & Sons, Ltd.

Received 8 November 2002
Revised 17 February 2004

472

Y. YAMAGAMI ET AL.

On the other hand, there have been published many papers concerning to the analysis oftransient responses of lossy interconnects coupled with non-linear terminations. Their analyticalmethods are roughly classied into 3 groups. The rst is the method of characteristics asshown in Reference [10] which is based on the reection mechanism proposed by Branin[11]. The second is the scattering matrix method as shown in Reference [12, 36], etc. The
third uses the method of inverse Laplace transform as shown in References [13–17]. They
are usefully applied to the linear systems. The responses with non-linear terminations arecalculated by the combination of the recursive convolution methods [14, 18, 19].
Nowadays, asymptotic waveform evaluation (AWE) [20] is widely used as a reduction
technique of large-scale networks coupled with interconnects, whose algorithm is based on
the moment-matching method and the Pade approximation [21, 22]. Unfortunately, one of
the serious problems of the AWE is that the poles far from the origin sometimes become
erroneous, because the admittance or impedance matrix in the AWE is rstly described by
the power series of the complex frequency s using the Maclaurin expansion [20], and after
then, it is transformed into the corresponding rational function by the application of the Padeapproximation.
To overcome the problem, Nakhla et al. have proposed complex frequency hopping (CFH)[23] for calculating the exact poles. The algorithm can nd out the exact poles by properly
hopping the origin of Taylor expansion on the complex axis. The other is based on a multipoint Pade approximation [24]. Both of them need properly to choose some points in thecomplex frequency domain to obtain the exact Taylor series. Thus, it can nd the goodPade approximation. We have also proposed an elegant method in Reference [25]. In these
reduction algorithms, the reduced circuits sometimes become unstable in the time domaineven if all the poles are located in the left-hand side of the complex plane. The ill-condition
can be overcome by Pade via a Lanczos (PVL) process [26]. The passive reduced-orderinterconnect macromodelling algorithm (PRIMA) [2, 27] is an extension of the block Arnoldi
technique to include the guaranteed passivity. In order to apply this algorithm to the circuitswith interconnects, we need two steps such that each interconnect is modelled by a niteorder system, and Arnoldi-based congruence transform is applied to the system to form its
reduced-order model [28].
On the other hand, it is said that a circuit is dened as passive if it satises the law ofconservation of energy. Depending on the denition, it is of general perception that if thefrequency response of the reduced-model is matched with the original response up to thehighest frequency of interest, the passivity can be preserved [29]. Another ecient passive
reduction algorithm satisfying the above passivity condition is given in Reference [30].
In this paper, we consider LSIs such that large-scale gate-array circuits are coupled withinterconnects embedded in the substrate. In this case, the capacitance component of the interconnect is dominant compared to the inductance, and the diusion resistance is very large
compared to those of PCBs [3], so that we can assume them as RCG interconnects insteadof RLCG. We rst derive the impedance matrix at the near and far end of the interconnect[1]. All the poles of the impedance matrix are located on the negative real axis in the complex plane, and they will be easily calculated by a commercial software. Using the poles,
we approximately describe each element of the matrix in a form of partial fraction, where
the residues are calculated by the least squares method in such a manner that the response
curves coincide with those from the impedance matrix in the complex frequency domain ofinterest. We found from the simulation results that the impedance matrix can be approximately
Copyright ? 2004 John Wiley & Sons, Ltd.

Int. J. Circ. Theor. Appl. 2004; 32:471–486

A REDUCTION TECHNIQUE OF LARGE-SCALE RCG INTERCONNECTS

473

described by the partial fractions with few dominant poles located near the origin. Therefore,
our reduction rate will be very large especially for large-scale interconnects. Since each element of the impedance matrix can be approximately described by a series of partial fractions,
it is easily realized by the asymptotic equivalent circuit satisfying the partial fractions. Thus,
we can easily develop SPICE oriented simulators of LSIs coupled with RCG interconnects. In
Section 2, we show how to calculate the exact poles and residues. In Section 3, it is shownthat the impedance matrix of interconnect can be well approximated with few dominant termsof the partial fractions. Thus, we can realize the simple asymptotic equivalent circuit familiar
with SPICE. We can also show that the circuit is always passive. In Section 4, our reduction
algorithm is shown using an example of the large-scale RCG interconnects. We found fromthe results that the reduction rate of our method is very large. In Section 5, some interesting
examples are shown with our SPICE-oriented simulators. We found from the examples that
our asymptotic equivalent method for the interconnects can get the good results even for the
lower order approximation.

2. CALCULATION OF THE EXACT POLES AND RESIDUES OF INTERCONNECTS
Now, consider a uniform N coupled RCG interconnect. Let us assume the telegraph equation
can be described bydV(x; s)= − RI(x; s);dxdI(x; s)= − (G + sC)V(x; s)dx(1)

in the complex frequency domain, where R; C and G are positive denite symmetric matrices.
Let us introduce matrices Pv (s) and Pc (s) to transform the circuit equations into the diagonal
forms, which satisfy
diag[i (s)2 ] = Pv (s)−1 R(G + sC)Pv (s)(2)

diag[i (s)2 ] = Pc (s)−1 (G + sC)RPc (s)Then, the input and output relations at the near and far ends are described by the impedance
matrix as follows [1, 31]:

V(0; s)V(d; s)=

Z11 (s)Z12 (s)Z21 (s)Z22 (s)I(0; s)−I(d; s)

(3)

where
Z11 (s) = Z22 (s) = Pv (s)diag[coth i (s)d]Pc (s)−1Z12 (s) = Z21 (s) = Pv (s)diag[sinh i (s)d]−1 Pc (s)−1(4)

Observe that all the poles of the impedance matrix are found at the locations satisfying
sinh i (s)d = 0. Thus, we have the following theorem for the calculation of the poles.
Copyright ? 2004 John Wiley & Sons, Ltd.

Int. J. Circ. Theor. Appl. 2004; 32:471–486

474

Y. YAMAGAMI ET AL.

Theorem 1
The locations of the poles satisfying relations (3) are found by solving the following equations[25]:
 2 
R(G + sC) + n I = 0; n = 1; 2; : : :
(5)


d
where d is the length of the interconnect. For n = 0, we have |G + sC| = 0.
It can be also proved [32] that if R; C and G are positive denite symmetric matrices,then, all the poles of RCG interconnect are located in the negative real axis. Thus, the poles
satisfying (5) can be obtained by solving the following relation:
 

n 2
−1
|sI − A| = 0 for A = − (RC)I + RG(6)dwhere we can eciently use a commercial software (for example Reference [33]) to calculate
the eigenvalues of A.
To describe the impedance matrix (3) with partial fractions, we need to calculate theresidues corresponding to the above poles.
Theorem 2
For the case of n = 0 in (5), the residues of Z12 (s) and Z21 (s) in (4) at the pole pi are
given byi ···  ···−11
Pc (s) (7)
k12; i = k21; i = Pv (s)diag
···0
0···

cosh(i (s)d)(@i (s)=@s)ds=pi
where @i (s)=@s is obtained as follows [20]:


@Ui

R(G + sC) − i (s)2 I @s =
 @ (s) 
UiT
i
@s

−2i (s)Ui

−1 

−RCUi



0

0

(8)

where Ui is an eigenvector for i (s) given in Equation (2).
Corollary 2.1
The residues of Z11 (s) and Z22 (s) in Equation (4) are given by ··· k12; i = k21; i = Pv (s)diag
0···



i

 ···
−1 
1
Pc (s) ···0(@i (s)=@s) d
s=pi

(9)

Observe that the residues given by Equations (7) and (9) are the same except for the signs,
because the denominator of (7) has the factor cosh(i (s)d) which takes the value ‘1’ or ‘−1’
depending on i (s)d|s=pi = jn; i = 1; 2; : : : ; N; n = 1; 2; : : : .
Now, let us calculate the poles p0i and the residues k011; i = k022; i ; k012; i = k021; i at n = 0.
Copyright ? 2004 John Wiley & Sons, Ltd.

Int. J. Circ. Theor. Appl. 2004; 32:471–486

A REDUCTION TECHNIQUE OF LARGE-SCALE RCG INTERCONNECTS

475

Corollary 2.2
Since the poles s = p0i at n = 0 correspond to i → 0, we have the following relation:
lim Pv (s)diag[sinh i (s)d]−1 Pc (s)−1 = (G + sC)−1 =d(10)

(s)→0It can be transformed into the diagonal form [32]. Furthermore, we can show from Equation(10) that k012; i = k021; i are equal to k011; i = k022; i .
Thus, the impedance matrix given by Equation (4) is described by the partial fractions withthe poles and the corresponding residues in the following form:
Z11; ij (s) = Z22; ij (s) =k0; ijk1; ijk2; ijk3; ij++++ ···s − p0 s − p1 s − p2 s − p3(11)Z12; ij (s) = Z21; ij (s) =k0; ijk2; ijk1; ijk3; ij−+−+ ···s − p0 s − p1 s − p2 s − p3

(12)

It is very important to estimate the number of terms in Equations (11) and (12) whichshould be chosen to approximate the impedance matrix given by Equation (4). We consider
here the special case of single line interconnect, where the input and output of an interconnect
are described by the impedance matrix as follows:

V (0; s)V (d; s)

= Z0 (s)Z0 (s) =coth (s)d(sinh (s)d)−1(sinh (s)d)−1R=(G + sC);

coth (s)d
(s) = R(G + sC)



I (0; s)−I (d; s)

(13)
(14)

We assumed the parameters as follows: R = 5 = m; C = 6:28 fF= m; G = 10 mS= m,d = 5 m.
The frequency responses of Z11 (s) = Z22 (s) and Z12 (s) = Z21 (s) for the 20th order approximation‡ are shown in Figure 1(a) and 1(b), respectively. We found from the example thatboth frequency response curves are good agreement on the whole frequency-domain. Thus,
we can expect to have the good result of the transient response with the asymptotic equivalentcircuit realized by relation (11) and (12), whose algorithm is shown in the next section.§
3. ASYMPTOTIC EQUIVALENT CIRCUIT AND ITS PASSIVITY
Now, consider the equivalent circuit for realizing the impedance matrix given by Equation (4).
We have already shown in Section 2 that all the poles are located on the negative real axis.
Furthermore, only the poles located near the origin will give large eect to the transient
response. Therefore, we need to choose the few dominant poles around the origin. For simplicity, we consider the asymptotic equivalent circuit for the single line interconnect given‡ The nth order approximation means that we take rst n terms of Equations (11) and (12).

§ You can see the same result in Reference [25] for RLCG interconnect.

Copyright ? 2004 John Wiley & Sons, Ltd.

Int. J. Circ. Theor. Appl. 2004; 32:471–486

476

Y. YAMAGAMI ET AL.

30

20

25

Frequency response Z11=Z22

20

10

Impedance (Ω)

Impedance (Ω)

15Frequency response Z12=Z21

15:Exact(Real):Approximation(Real):Exact(Imag):Approximation(Imag)

50:Exact(Real):Approximation(Real):Exact(Imag):Approximation(Imag)

10
5
0

-5
-5
-10
-15

(a)

0

5

10

15

20 25 30
(x1012 )Hz

35

40

45

-10

50

0

5

10

15

(b)

20 25 30
(x1012 )Hz

35

40

45

50

Figure 1. Approximation of partial fraction (Order = 20).

by Equations (13) and (14). Of course, the method can be easily extended to an N -coupledinterconnect. We have from Equations (11) and (12) the following relations:

M

k0
k2i
k2i−1
+
+
Z11 (s) = Z22 (s) =s − p0 i=1 s − p2i−1 s − p2i

M

k0
k2i
k2i−1
−
+
+
Z12 (s) = Z21 (s) =s − p0 i=1
s − p2i−1 s − p2i

(15)
(16)

where M is the number of dominant terms. Equations (15) and (16) consist of the same termswith the dierent signs. Therefore, let us set them as follows:
Z1 (s) =

M


k2i
;
s
−
p2i
i=0

Z2 (s) =

M


k2i−1
s
−
p2i−1
i=1

(17)

where the poles and the residues are calculated from Equations (5), (7), (9) and (10) as
follows:G
p0 = − ;
C
k0 =

1
;
Cd

pi = −
ki =

2
;
Cd

RG + (i=d)2;
RC

i = 1; 2; : : : ; 2M

i = 1; 2; : : : ; 2M

(18)
(19)

Then, Equations (13) and (14) can be approximately written in the following form:

 


V (0; s)Z1 (s) + Z2 (s) Z1 (s) − Z2 (s)I (0; s)=(20)
−I (d; s)V (d; s)Z1 (s) − Z2 (s) Z1 (s) + Z2 (s)Copyright ? 2004 John Wiley & Sons, Ltd.

Int. J. Circ. Theor. Appl. 2004; 32:471–486

A REDUCTION TECHNIQUE OF LARGE-SCALE RCG INTERCONNECTS

Vd =-Z 2I(d,s) Vs =Z 2 I(0,s)

I(0,s)Z2

I(0,s)-I(d,s)477-I(d,s)
2Z2

Z2

2Z 1

Z1

V(0,s)

V(0,s)

V(d,s)2Z 1

V(d,s)

2Z2

(a)

(b)

Z1

R0

R2

R4

R 2M

C0

C2

C4

C2M

Z2

(c)

R1

R3

R 2M-1

C1

C3

C 2M-1(d)Figure 2. Asymptotic equivalent circuit.

The impedance matrix (20) contains the terms −Z2 (s)I (d; s) and Z2 (s)I (0; s), which can besynthesized by the use of the current-controlled voltage sources
Vd (s) = − Z2 (s)I (d; s);Vs (s) = Z2 (s)I (0; s)(21)

as shown in Figure 2(a). The controlled voltage sources play the important role of the reections from both ends. We can also realize (20) by a lattice circuit as shown in Figure 2(b).
The impedances Z1 and Z2 in Figure 2(a) and (b) are synthesized by the series connectionof R–C circuits as shown in Figure 2(c) and (d), where
Ci =

1
;
ki

Ri = −ki;pi

for pi ¡ 0

i = 0; 1; 2; : : : ; 2M

(22)

Observe that these asymptotic equivalent circuits are very simple and familiar with SPICE.
Thus, we can easily develop the user-friendly simulator. The equivalent circuits for the multiconductor interconnects can be realized in the same way as shown in the next section.
Remark that the asymptotic equivalent circuit is realized in two dierent ways as shown in
Figure 2(a) and 2(b). Since all the resistive and capacitive elements in Z1 and Z2 are always
positive as shown by Equation (22), the circuit (b) is passive because it does not contain any
controlled source. Thus, the circuit (a) is also passive because they are equivalent in eachother. Although both circuits will have the same v–i characteristics, the applications of thelatter may be somewhat limited because the lower terminals are connected through 2Z2 . See
References [25, 34] for the other circuit structures of RLCG interconnects.

4. LARGE-SCALE RCG INTERCONNECTS
Let us consider the reduction algorithm of large-scale RCG interconnects and the asymptotic
equivalent circuit models. To understand our algorithm, we consider an example of N coupledinterconnect whose parameters [35] are given as follows:[Ri; i = 5 = m;i = 1; 2; : : : ; N; Other elements of R are zeros]

Copyright ? 2004 John Wiley & Sons, Ltd.

(23)

Int. J. Circ. Theor. Appl. 2004; 32:471–486

478

Y. YAMAGAMI ET AL.

Table I. Poles for N = 1 (|pmax |¡400).
No.

n=0

n=1

n=2

n=3

n=4

n=5

1

−1:5924−14:165−51:883−114:75−202:76−315:92

Table II. Poles for N = 2 (|pmax |¡400).
No.

n=0

n=1

n=2

n=3

n=4

n=5

1
2

−1:5544−1:6248−13:288−15:191−48:276−56:101−106:59−124:28−188:23−219:72−293:21−342:48

Table III. Poles for N = 10 (|pmax |¡400).
No.

n=0

n=1

n=2

n=3

n=4

n=5

1
2
3
4
5
6
7
8
9
10

−1:4957−1:5151−1:5419−1:5702−1:5953−1:6146−1:6275−1:6347−1:6379−1:6387−12:652−12:795−13:038−13:381−13:825−14:356−14:946−15:540−16:063−16:426−45:693−46:269−47:264−48:643−50:456−52:640−55:073−57:537−59:707−61:217−100:76−102:06−104:26−107:41−111:51−116:45−121:95−127:53−132:45−135:87−177:86−180:16−184:08−189:69−196:98−205:77−215:58−225:52−234:28−240:03−276:98−280:58−286:71−295:48−306:88−320:62−335:96−352:72−362:01−374:76Gi; i = 10 mS= m; Gi; i−1 = Gi; i+1 = − 1 mS= m; Gi; i−2 = Gi; i+2 = − 0:1 mS= m







(24)

i = 1; 2; : : : ; N; Other elements of G are zerosCi; i = 6:28 fF= m; Ci; i−1 = Ci; i+1 = − 0:49 fF= m; Ci; i−2 = Ci; i+2 = − 0:03 fF= m







(25)

i = 1; 2; : : : ; N; Other elements of C are zeros
and assume the length d = 5 m. Using relation (5), we found the poles as shown in Tables
I–III where the poles less than −400 are neglected, because they will give only small eect
to the transient response, where N = 1; 2; 10 means a single line, 2-coupled and 10-coupledinterconnects, respectively. It is remarkable that the number of poles for N -coupled interconnect is given by N × (M + 1) if we take into account until n = 0; 1; : : : ; M in Equation (5) for
Copyright ? 2004 John Wiley & Sons, Ltd.

Int. J. Circ. Theor. Appl. 2004; 32:471–486

479

A REDUCTION TECHNIQUE OF LARGE-SCALE RCG INTERCONNECTS

30

20

25

Least squares with 6 poles ( Z 11,11 )15
10Least squares with 6 poles ( Z 12,11 )15:Exact(Real):Approximation(Real):Exact(Imag):Approximation(Imag)

50:Exact(Real):Approximation(Real):Exact(Imag):Approximation(Imag)

10

Impedance (Ω)

Impedance (Ω)

20

5
0

-5
-5
-10
-15

0

5

10

15

20

25

30

35

40

12

(a)

(x10 )Hz

45

50

-10

(b)

0

5

10

15

20

25

30

35

40

45

50

12

(x10 )Hz

Figure 3. Least squares method with 6 poles: (a) Z11; 11 ; (b) Z12; 11 .

the pole calculation. Thus, the number of poles rapidly increases with M and N , which causes
the asymptotic equivalent circuit to complicate, especially for the large-scale interconnects.
We found from the tables that the poles for N = 1 are always located around the central
position for every nth pole groups; i.e. they are located between No.1 and No.2 for N = 2,
and between No.5 and No.6 for N = 10 as shown in Tables II and III. Hence, in our reduction
algorithm, we shall use the 6 poles for N = 1 given in Table I, as the dominant poles for all
the cases of N even if N = 100; 1000 or more.
In this case, each matrix element given by Equation (4) can be described by the 6 terms
in the following form:

Zkl; ij =k2; kl; ij
k3; kl; ij
k4; kl; ij
k5; kl; ij
k6; kl; ij
k1; kl; ij
+
+
+
+
+
s + 1:5924 s + 14:165 s + 51:883 s + 114:75 s + 202:76 s + 315:92
k; l = 1; 2;

i; j = 1; 2; : : : ; N(26)

Note that we cannot any more apply the methods given by Theorem 2 and Corollary 2.1 toestimate the residues k1; kl; ij ; : : : ; k6; kl; ij .
Therefore, we propose here to apply the least squares method to estimate the approximate
residues, in such a manner that the deviations between the frequency response curves from theimpedance matrix given by Equation (4) and those from Equation (26) become the smallest
in all the frequency domain of interest.¶ The frequency response curves using the 6 poles areshown in Figure 3(a) and 3(b). We also found from the numerical results that the residues far
from the diagonal elements in Zij ; i; j = 1; 2 become smaller and smaller. Thus, it is enoughto choose at most seven elements including the diagonal element in each row. Hence, each

¶ In this calculation, we eciently used a widely distributed computer software Lapack [33].

Copyright ? 2004 John Wiley & Sons, Ltd.

Int. J. Circ. Theor. Appl. 2004; 32:471–486

480

Y. YAMAGAMI ET AL.

sub-matrix in Equation (4) can be written as follows:
Zij; 11 Zij; 12 Zij; 13 Zij; 14 0
0
0
0
0
0
0


 Zij; 21 Zij; 22 Zij; 23 Zij; 24 Zij; 25 0
0
0
0
0
0 





 Zij; 31 Zij; 32 Zij; 33 Zij; 34 Zij; 35 Zij; 36 0
0
0
0
0




 Zij; 41 Zij; 42 Zij; 43 Zij; 44 Zij; 45 Zij; 46 Zij; 47
0
0
0
0 


Zij (s)   (27)

 0 Zij; 52 Zij; 53 Zij; 54 Zij; 55 Zij; 56 Zij; 57 Zij; 58
0
0
0




 0
Zij; 69
00 
0 Zij; 63 Zij; 64 Zij; 65 Zij; 66 Zij; 67 Zij; 68 ..................................................................... 


0

0

0

0

0

0

0

Zij; NN −3 Zij; NN −2 Zij; NN −1 Zij; NNfor i; j = 1; 2. We also found from the results that the diagonal terms in Z11 (s) = Z22 (s) andZ12 (s) = Z21 (s) are most dominant. Furthermore, we have the following relations:
Zij; 11 ≈ · · · ≈ Zij; NN ; for diagonal elements(28)
Zij; kk+1 ≈ Zij; kk−1 ; Zij; kk+2 ≈ Zij; kk−2 ; Zij; kk+3 ≈ Zij; kk−3 ; for nonzero kth terms
Using relations (3) and (28), the terminal voltages at the near and far ends can be written as
follows:
Vk (0; s) ≈ Z11; kk Ik (0; s) + Z11; kk+1 (Ik−1 (0; s) + Ik+1 (0; s))+Z11; kk+2 (Ik−2 (0; s) + Ik+2 (0; s)) + Z11; kk+3 (Ik−3 (0; s) + Ik+3 (0; s))+Z12; kk Ik (d; s) + Z12; kk+1 (Ik−1 (d; s) + Ik+1 (d; s))+Z12; kk+2 (Ik−2 (d; s) + Ik+2 (d; s)) + Z12; kk+3 (Ik−3 (d; s) + Ik+3 (d; s))(29)

Vk (d; s) ≈ Z12; kk Ik (0; s) + Z12; kk+1 (Ik−1 (0; s) + Ik+1 (0; s))+Z12; kk+2 (Ik−2 (0; s) + Ik+2 (0; s)) + Z12; kk+3 (Ik−3 (0; s) + Ik+3 (0; s))+Z11; kk Ik (d; s) + Z11; kk+1 (Ik−1 (d; s) + Ik+1 (d; s))+Z11; kk+2 (Ik−2 (d; s) + Ik+2 (d; s)) + Z11; kk+3 (Ik−3 (d; s) + Ik+3 (d; s))k = 1; 2; : : : ; N(30)

Z11; kk in the rst term of Equation (29) and the fth term of Equation (30) correspond to theself-impedances Z11 ; Z22 ; : : : ; ZNN as shown in Figures 4(b) and 5(b). Other terms consist of
the current-controlled voltage sources as shown Figure 5(a).
We found from the example that the reduction rate is very large, because the impedance
matrix can be approximated with few dominant elements around the diagonals as shown inEquation (27). If the coupling coecients between the multi-conductors ((23)–(25)) become
stronger, we may take into account some more o-diagonal elements of Zij (s); i; j = 1; 2.
Copyright ? 2004 John Wiley & Sons, Ltd.

Int. J. Circ. Theor. Appl. 2004; 32:471–486

481

A REDUCTION TECHNIQUE OF LARGE-SCALE RCG INTERCONNECTS

I 1(0,s)V11,1(s) I (0,s) I (d,s) V12,1(s)11
Z 11
V11,2(s) I2(0,s) I2(d,s)V12,2(s)
Z 22
Z22

I 1(d,s)V1 (0,s)I 2 (0,s)T2Sub-circuit
No.1

V1 (0,s)V2 (d,s)V2 (0,s)Z 11

I 2(d,s)T1

V2 (0,s)V1 (d,s)I N (0,s)

I N(d,s)VN (0,s)VN (d,s)(a)V2 (d,s)Sub-circuit
No.2

Sub-circuit
No.1

Sub-circuit
No.2

TN

V1 (d,s)

V11,N(s) IN(0,s) IN(d,s) V12,N(s)
Z NN
Z NN

VN (0,s)VN (d,s)(b)

Figure 4. (a) Multi-conductor interconnect coupled with LSIs; and (b) SPICE modelof the multi-conductor interconnect.

Vij,knZij,kk+n
Ik+n

Cij,1

Cij,2

Cij,6

Rij,1

Rij,2

Rij,6

Z11

C11,1

C11,2

C11,6

R11,1

R11,2

R11,6

Ik-n

(a)

(b)

Figure 5. (a) Current-controlled voltage source; and (b) self-impedance.

5. ILLUSTRATIVE EXAMPLES
5.1. Crosstalk
In order to investigate the crosstalks, we consider a 4 coupled interconnect as shown in
Figure 6(a), whose parameters are given by Equations (23)–(25). The transient responses
at near and far ends of 4 coupled lines are shown in Figure 6. They have relatively large
crosstalk.
5.2. Inverter circuit
Now, we consider inverter circuit coupled by interconnects as shown in Figure 7(a). Let us
assume the parameters as follows [3]:[Ri; i = 50 = m; i = 1; 2; : : : ; N; Other elements of R are zeros]Gi; i = 0:01 mS= m; Gi; i−1 = Gi; i+1 = − 0:002 mS= m; Gi; i−2 = Gi; i+2 = − 0:0004 mS= m








i = 1; 2; : : : ; N; Other elements of G are zeros
Copyright ? 2004 John Wiley & Sons, Ltd.

Int. J. Circ. Theor. Appl. 2004; 32:471–486

482

Y. YAMAGAMI ET AL.

10Ω

10MΩ
T1

10MΩ

10Ω

1.0ps

T2

10MΩ

10Ω

Input waveform

5V

T3

10MΩ

10Ω

1.2ps

T4

(a)
4.0

(V)

25.0
near end
far end

3.0

T3

T1

near end
far end

15.0

2.0
1.0

10.0
5.0
0.0

0.0
0.0

0.5

1.0

1.5

2.0

2.5

0.5
near end
far end

120.0

0.5

1.0

1.5

2.0

2.5

3.0

ps

(mV)

0.0
-0.5
T4

80.0

-1.0
near end
far end

-1.5

40.0

-2.0

0.0
0.0

-5.0
0.0

3.0

ps

(mV)
160.0

T2

(mV)

20.0

0.5

1.0

1.5

(b)

2.0

2.5

3.0

-2.5
0.0

0.5

1.0

1.5

2.0

2.5

3.0

ps

ps

Figure 6. (a) 4-coupled interconnects; and (b) crosstalks.

10Ω

1MΩ
T1

1MΩ

10Ω
T2

10Ω

0.4ns

1MΩ
T3

Input waveform

5V
0.44ns

10Ω

1MΩ
TN

Figure 7. Inverter circuit, d = 20 m.

Ci; i = 1:0 fF= m; Ci; i−1 = Ci; i+1 = − 0:2 fF= m; Ci; i−2 = Ci; i+2 = − 0:04 fF= m







i = 1; 2; : : : ; N; Other elements of C are zeros
Copyright ? 2004 John Wiley & Sons, Ltd.

Int. J. Circ. Theor. Appl. 2004; 32:471–486

A REDUCTION TECHNIQUE OF LARGE-SCALE RCG INTERCONNECTS

6.0
5.0

input

4.0
3.0

(V)

483

output

2.0
1.0
0.0

(a)

-1.0
0.0

0.2

0.4

0.6

0.8

1.0

ns
6.0
5.0

input

4.0

output

(V)

3.0
2.0
1.0
0.0
-1.0
0.0

(b)

0.2

0.4

0.6

0.8

1.0

ns

(V)

6.0
5.0

input

4.0

output

3.0
2.0
1.0
0.0

(c)

-1.0
0.0

0.2

0.4

0.6

0.8

1.0

ns

Figure 8. Transient responses: (a) N = 1; (b) N = 4; and (c) N = 10.

We always used the 6 poles from N = 1 as the dominant poles for the coupled interconnect,
and the residues are estimated by the least squares method as shown in Section 4. The
responses for N = 1, 4 and 10 are shown in Figure 8(a), (b) and (c), respectively. Observethat the response of the central line of the interconnect has the largest time-delay. Their
phenomena are caused by both interconnects and inverters.
5.3. A fulladder circuit coupled with interconnects
Consider a fulladder circuit coupled with interconnects as shown in Figure 9(a). The coupling
parameters are the same as those of the inverter circuit in example 5.2. The transient responses
at the output stages are shown by solid lines in Figure 9(b), where the dotted lines show the
responses without the interconnects. Observe that the responses with the coupled interconnects
show complicated phenomena combining the time-delays, crosstalks, reections, etc.
6. CONCLUSIONS AND REMARKSIn this paper, we have proposed a reduction algorithm for large-scale RCG interconnects,
where the interconnects are replaced by simple asymptotic equivalent circuits familiar with
Copyright ? 2004 John Wiley & Sons, Ltd.

Int. J. Circ. Theor. Appl. 2004; 32:471–486

484

Y. YAMAGAMI ET AL.

Half Adder 2

Half Adder 1

v1

v2

T1

T4

T2

T5

T3

T6

vs

v3
vc

(a)
6.0

(V)

v1

4.0
2.0
0.0
6.0

v2

4.0
2.0
0.0
6.0

v3

4.0
2.0
0.0
6.0

vs

4.0
2.0
0.0
6.0

vc

4.0
2.0
0.0
0.0

5.0

(b)

10.0

15.0
ns

20.0

25.0

30.0

Figure 9. (a) Fulladder coupled with interconnects d = 20 m; and (b) transient response of the fulladdercircuit, v1 ; v2 ; v3 : inputs, vs ; vc : outputs. The solid lines show the responses with coupled interconnects,
and the dotted lines show the responses without the interconnects.

SPICE. The algorithm will be eciently applied to such a large-scale circuit coupled withinterconnects in the substrate.
In Section 2, we showed that a numerical algorithm for computing the exact poles and theresidues given by the impedance matrix. Thus, the impedance matrix is described in the form
Copyright ? 2004 John Wiley & Sons, Ltd.

Int. J. Circ. Theor. Appl. 2004; 32:471–486

A REDUCTION TECHNIQUE OF LARGE-SCALE RCG INTERCONNECTS

485

of partial fractions. The partial fractions are realized by the asymptotic equivalent circuits asshown in Section 3. In Section 4, we have applied it to large-scale interconnects, where theresidues are estimated by the least squares method instead of the analytical method. We foundfrom the numerical examples that the impedance matrices are approximated by very simple
sparse matrices, whose dominant elements are distributed around the diagonal elements. Thus,
the reduction rate is very large especially for large-scale interconnects.
For the future work, we want to extend the algorithm to the large-scale RLCG interconnects.
ACKNOWLEDGEMENTS

The authors would like to thank a manager of Sony Co. Mr K. Ogawa for giving us important suggestions, and ME student of Tokushima University Mr H. Sakaguchi for his help to the numericalexperiments.
REFERENCES
1. Brandao Faria JA. Multiconductor Transmission-Line Structures: Modal Analysis Techniques. Wiley: New
York, 1993.
2. Celik M, Pileggi L, Odabasioglu A. IC Interconnect Analysis. Kluwer Academic Publishers: Dordrecht, 2002.
3. Wyatt Jr JL. Signal propagation delay in RC models for interconnect. In Circuit Analysis, Simulation and
Design, Ruehli AE (ed.). Elsevier, North-Holland: Amsterdam, 1987; 254 –291.
4. Elmore WC. The transient response of damped linear networks with particular regard to wideband ampliers.
Journal of Applied Physics 1948; 19:55 – 63.
5. Sakurai T. Closed-form expressions for interconnection delay, coupling, and crosstalk in VLSI’s. IEEE
Transactions on Electron Devices 1991; 40:118 –124.
6. Kim S-Y, Gopal N, Pillage LT. Time-domain macromodels for VLSI interconnect analysis. IEEE Transactions
on Computer-Aided Design 1994; 13:1257–1270.
7. Gupta R, Tutuianu B, Pileggi LT. The Elmore delay as a bound for RC trees with generalized input signals.
IEEE Transactions on Computer-Aided Design 1997; 16:95 –104.
8. Alpert CJ, Devgan A, Kashap CV. RC delay metrics for performance optimization. IEEE Transactions on
Computer-Aided Design 2001; 20:571–582.
9. Kimura T, Okumura M. An ecient reduction method of a substrate RC network model. IEICE Transactions
on Fundamentals 2001; E84-A:698 –704.
10. Chang FY. Waveform relaxation analysis of RLCG transmission lines. IEEE Transactions on Circuits andSystems 1990; 37:1394 –1415.
11. Branin FH Jr. Transient analysis of lossless transmission line. Proceedings of IEEE 1967; 55:2012–2013.
12. Dhaene T, Martens L, Zutter DD. Transient simulation of arbitrary nonuniform interconnection structurescharacterized by scattering parameters. IEEE Transactions on Circuits and Systems 1992; 39:928 –937.
13. Chang EC, Kang SM. Computationally ecient simulation of a lossy transmission line with skin eect by using
numerical inversion of Laplace transform. IEEE Transactions on Circuits and Systems 1992; 39:861– 868.
14. Roychowdhury JS, Newton AR, Pederson DO. Algorithms for the transient simulation of lossy interconnects.
IEEE Transactions on Computer-Aided Design 1994; 13:96 –104.
15. Hosono T. High Speed Laplace Transformation with BASIC. Kyouritsu: Japan, 1984 (Japanese).
16. Manney SL, Nakhla MS, Zhang Q-J. Analysis of nonuniform, frequency-dependent high-speed interconnects
using numerical inversion of Laplace transform. IEEE Transactions on Computer-Aided Design 1994; 13:1513–1525.
17. Ichikawa S. Numerical analysis of traveling waves in transmission networks by numerical inversion of Laplacetransform. IEE of Japan 1982; 102(12):785–792 (Japanese).
18. Lin S, Kuh ES. Transient simulation of lossy interconnects based on the recursive convolution formulation.
IEEE Transactions on Circuits and Systems-I 1992; 39:879 –892.
19. Lawrence YL, Pileggi T, Strojwas AJ. ftd:Frequency to time domain conversion for reduced-order interconnect
simulation. IEEE Transactions on Circuits and Systems-I 2001; 48:500 –506.
20. Chiprout E, Nakhla MS. Asymptotic Waveform Evaluation and Moment Matching for Interconnect Analysis.
Kluwer Academic Publishers: Dordrecht, 1994.
21. Pillage LT, Rohrer RA. Asymptotic waveform evaluation for timing analysis. IEEE Transactions on ComputerAided Design 1990; 9:352–355.
Copyright ? 2004 John Wiley & Sons, Ltd.

Int. J. Circ. Theor. Appl. 2004; 32:471–486

486

Y. YAMAGAMI ET AL.

22. Lee JY, Huang X, Rohrer RA. Pole and zero sensitivity calculation in asymptotic waveform evaluation. IEEE
Transactions on Computer-Aided Design 1992; 11:586 –597.
23. Chiprout E, Nakhla MS. Analysis of interconnect networks using complex frequency hopping(CHF). IEEE
Transactions on Computer-Aided Design 1995; 14:186 –200.
24. Celik M, Ocali O, Tan MA, Atalar A. Pole-zero computation in microwave circuits using multipoint Padeapproximation. IEEE Transactions on Circuits and Systems 1995; 42:6 –13.
25. Ushida A, Urabe K, Yamagami Y, Nishio Y. Asymptotic equivalent circuits of interconnects based on complex
frequency method. ECCTD’01 2001; 3:29 –32.
26. Feldmann P, Freund RW. Ecient linear analysis by Pade approximation via the Lanczos process. IEEE
Transactions on Computer-Aided Design 1995; 14:639 – 649.
27. Odabasioglu A, Celik M, Pileggi LT. PRIMA: passive reduced-order interconnect macromodeling algorithm.
IEEE Transactions on Computer-Aided Design 1998; 17:645 – 654.
28. Yu Q, Meiling J, Kuh ES. Passive multipoint moment matching model order reduction algorithm on multiport
distributed interconnect networks. IEEE Transactions on Circuits and Systems-I 1999; 46:140 –160.
29. Winklestein D, Steer BB, Pomerleau R. Simulation of arbitrary transmission line networks with nonlinear
terminations. IEEE Transactions on Circuits and Systems-I 1991; 38:418 – 422.
30. Achar R, Gunupudi PK, Nakhla MS, Chiprout E. Passive interconnect reduction algorithm for
distributed/measured networks. IEEE Transactions on Circuits and Systems-II 2000; 47:287–301.
31. Tanji Y, Jiang L, Ushida A. Analysis of pulse response of multi-conductor transmission lines by a partitioning
technique. IEICE Transactions on Fundamentals 1994; E77-A(12):2017–2027.
32. Chirlian PM. Integrated and Active Network Analysis and Synthesis. Prentice-Hall: Englewood Clis, NJ,
1967.
33. http://www.netlib.org/lapack.
34. Dhaene T, Zutter DD. Selection of lumped element models for coupled lossy transmission lines. IEEE
Transactions on Computer-Aided Design 1992; 11:805 – 815.
35. Weeks WT, Wu LL, McAllister MF, Singh A. Resistive and inductive skin eect in rectangular conductors.
IBM Journal on Research and Development 1979; 23(6):652– 660.
36. Corey SD, Yang AT. Interconnect characterization using time-domain reectometry. IEEE Transactions on
Microwave Theory and Techniques 1995; 43(9):2151–2156.

Copyright ? 2004 John Wiley & Sons, Ltd.

Int. J. Circ. Theor. Appl. 2004; 32:471–486