A REDUCTION TECHNIQUE OF LARGE SCALE
RCG INTERCONNECTS IN COMPLEXFREQUENCY DOMAIN
Y.Yamagami†, Y.Nishio†, A.Hattori†, A.Ushida††Department of Electrical and Electronic Engineering,
Tokushima University, Tokushima, 770-8506 JAPAN
Abstract
High frequency digital LSIs usually consist of many subcircuits 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, reﬂections and so on. In order to solve these problems, it is very important to develop a user-friendly simulator for the analysis of LSIs coupled with interconnects.
At the reduction algorithm, we ﬁrst calculate the dominantpoles which give the large eﬀects to the transient response,
and the corresponding residues are estimated by the leastsquares method. Thus, the interconnect is replaced by theequivalent circuit realizing the partial fractions.

1. Introduction
The analysis of high speed LSI chips is becoming more andmore important for their designing. The chips are usuallycoupled with interconnects embedded in the substrate, andinterconnects sometimes cause the fault switching of chips
due to the signal delays, crosstalks and so on [1]-[8]. 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 [3]. The closedform combining the delay and crosstalk is ﬁrstly obtainedin the reference [4]. Improved techniques [5]-[8] are also
proposed later for improving the accuracy and the practicalapplications in the simulations.
Nowadays, AWE(asymptotic waveform evaluation)[9] iswidely used as a reduction technique of large scale networks coupled with interconnects, whose algorithm is basedon the moment-matching method and Padè approximation.
Unfortunately, one of the serious problems of the momentmatching method is that the poles located far from the origin sometimes become erroneous, because the admittance or
impedance matrix via AWE is described in the form of power
series with the complex frequency s based on the Maclaurin
expansion. To overcome the problem, Nakhla et al. haveproposed CFH (complex frequency hopping) [10] 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 multi-point Padè
approximation [10]. Both of them need properly to choosesome points in the complex frequency domain to obtain theexact Taylor series and Padè approximation. PRIMA (passive reduced-order interconnect macromodeling algorithm)[11] is another reduction algorithm which is an extension of
the block Arnoldi technique to include guaranteed passivity.
0-7803-7762-1/03/$17.00 ©2003 IEEE

In order to apply this algorithm to the circuits with interconnects, we need two steps such that the interconnect ismodeled by a ﬁnite order system, and afterward, Arnoldibased congruence transform is applied to the system to form
its reduced order model.
In this paper, we consider LSIs such that large scale gatearray circuits are coupled with interconnects 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 thoseof PCBs [2], so that we assume the interconnect as RCG
interconnect instead of RLCG in this paper. We ﬁrst derive
the impedance matrix at the near and far end ports. We
prove that all the poles of the impedance matrix are locatedon the negative real axis in the complex plane. The residues
are decided by the least-squares method in such manner thatthe response curves coincide with those from the impedance
matrix in the complex frequency domain of interest. We
found from the simulation results that the impedance matrix
can be approximately described by the partial fractions withthe few poles located near the origin. The reduction rate isvery large especially for a large scale interconnect. Hence,each element of the impedance matrix can be described bya series of partial fractions, and the interconnect is easily
synthesized by the asymptotic equivalent circuit satisfying
the partial fractions. Thus, we can easily develop SPICEoriented simulator of LSIs coupled with RCG interconnects.

2. Poles and residues of the impedance
matrixNow, consider a uniform N coupled RCG interconnect.
Assume the telegraph equation can be described bydV(x, s)= −RI(x, s),dx

dI(x, s)= −(G + sC)V(x, s) (1)dx

in the complex frequency domain, where R, C and G are
positive deﬁnite symmetric matrices. Let us introduce thematrices Pv (s) and Pc (s) to transform them into the diagonal forms. Thus, we havediag[λi (s)2 ] = Pv (s)−1 R(G + sC)Pv (s)diag[λi (s)2 ] = Pc (s)−1 (G + sC)RPc (s)(2)where we can choose one of Pc (s)’s in the following relations:
Pc (s) = R−1 Pv (s)Γ(s),Pc (s) = (G + sC)Pv (s)Γ(s)−1 ,Pc (s)−1 = Pv (s)T

III-490
(3)

for Γ(s) = diag[λi (s)]. Then, the input and output relations
at the near and far ends are described by the impedance
matrix as follows:V(0, s)V(d, s)=

Z11 (s)Z21 (s)Z12 (s)Z22 (s)I(0, s)−I(d, s)(4)

satisfying (13) are negative real numbers.
Q.E.D.
Now, consider the numerical technique for calculating thepoles satisfying (6). Let us rewrite (11) in the followingform;|sI − A| = 0
(14)
where

where

A = −(RC)−1−1

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

Observe that all the poles of impedance matrix are found at
the locations satisfying sinh λi (s)d = 0. Thus, we have thefollowing theorem for the calculation of poles.
Theorem 1: The locations of poles satisfying relations (5)are found by solving the following equation: 2 
R(G + sC) + nπ I = 0, n = 0, 1, 2, . . .


d

d

I + RG(15)

The relation (14) corresponds to the characteristic equationof a matrix A. Then, we can apply the Bocher formula asfollows:
Bocher formular [13]: For an n × n matrix A, set|sI − A| = α0 + sα1 + · · · + sn−1 αn−1 + sn = 0
Then, α0 , α1 , . . . , αn−1 are given by(6)αn−1 = −trace(A)1αn−2 = − αn−1 trace(A) + trace(A2 )2..........................................
1
α0 = −
α1 trace(A) + α2 trace(A2 ) + · · ·n+αn−1 trace(An−1 ) + trace(An )where d is the length of the interconnect.
Proof In the case of n = 0, we have from (5) that the poles
satisfy the following relation:|Pc (s)diag[sinh λi (s)d]Pv (s)−1 | = 0

 
nπ 2

(7)

(16)















(17)

Since Pv (s) and Pc (s) are nonsingular for the nonzero eigenvalues, the poles satisfying the above two relations are givenby(9)sinh λi (s)d = 0, i = 1, 2, . . . , N

Thus, the poles satisfying algebraic equation (16) can becalculated by the application of standard numerical methods for solving the algebraic equation such as Bairstow algorithm.
Now, if we can estimate the residues corresponding to thepoles, the impedance matrix given by (5) can be describedby the partial fractions as follows:

where N shows a number of the multi-conductors. Namely,
we have

Z11,ij (s) = Z22,ij (s) =and|Pc (s)diag[tanh λi (s)d]Pv (s)λi (s)d = jnπ,

−1

|=0

(8)

i = 1, 2, . . . , N, n = 1, 2, . . .

(10)Therefore, the characteristic equation obtained from (2)needs to satisfy the relations (6). On the other hand, we
have from (2) that the zero eigenvalue satisﬁes |G+sC| = 0,
which corresponds to n = 0 in (6).
Q.E.D.
Theorem 2: Let R, C and G be positive definite symmetric matrices. Then, all the poles of RCG interconnect arelocated on the negative real axis.
Proof The poles satisfying relation (6) are given by



 2


(G + sC) + nπ R−1  = 0, n = 0, 1, 2, . . .


d

(11)

For simplicity, we will rewrite the matrix given by (11) as
follows:|sC + Hn | = 0,

where Hn =



nπ
d

2

R−1 + G

1

3. Large scale RCG interconnects
Now, let us discuss the reduction algorithm of a large scale
RCG interconnect and the asymptotic equivalent circuit
model. To understand our algorithm, we consider an example of N coupled interconnect whose parameters are given
as follows:



(12)

Observe that Hn is still a positive deﬁnite symmetric matrix.
Thus, it can be transformed into the following diagonal form:
SQT (Hn + sC)QS = SQT Hn QS + sI = 0

k0,ij
k1,ij
k2,ij
k3,ij
+
+
+
+· · ·
s + p0 s + p1 s + p2 s + p3
(18.1)
k0,ij
k1,ij
k2,ij
k3,ij
Z12,ij (s) = Z21,ij (s) =−+−+· · ·
s + p0 s + p1 s + p2 s + p3
(18.2)
for i, j = 1, 2, . . . , N . The residues can be calculated by
the least squares method in such manner that the frequency
responses of (18) are well approximated by those of the
impedance matrices (5).

(13)

with an orthogonal matrix Q and S = diag[Cii ]− 2 , where
Cii , i = 1, . . . , N are the eigenvalues of C. Here, SQT Hn QS
is a positive real symmetric matrix, so that all the poles

Ri,i = 5Ω/µm, Ri,i−1 = Ri,i+1 = 1Ω/µm,
Ri,i−2 = Ri,i+2 = 0.1Ω/µm,
i = 1, 2, . . . , N, Other elements of R are zeros

(19.1)
Gi,i = 10mS/µm, Gi,i−1 = Gi,i+1 = −1mS/µm,
Gi,i−2 = Gi,i+2 = −0.1mS/µm
i = 1, 2, . . . , N, Other elements of G are zeros(19.2)

Ci,i = 6.28fF/µm, Ci,i−1 = Ci,i+1 = −0.49fF/µm,
Ci,i−2 = Ci,i+2 = −0.03fF/µm
i = 1, 2, . . . , N, Other elements of C are zeros(19.3)



III-49130

Impedance (Ω)

Impedance(Ω)

We also assume the length d = 5 µm. We ﬁrst calculate
the poles using the relation (6), and have gotten the tables
3.1, 3.2 and 3.3, where we have neglected the poles with thevalue less than −400, because the poles far from the origin
will have only small eﬀects to the transient response.

25
Least squares with 6 poles(Z11,11)
20: Exact: Approximation

15

No.
1

16
14

Least squares with 6 poles(Z12,11)

12
10: Exact

8: Approximation

6

10

Table 3.1 Poles for N = 1 (|pmax | < 400)
n=0
n=1
n=2
n=3
n=4
-1.592-14.17 -51.88-114.8-202.8

18

4
5

n=5
-315.9

0

2
0

5

10

15

20

25

30

35

40

45

0

50

12

(x10 ) Hz

(a)

0

5

10

15

20

25 30
(b)

35

40

45

50

12

(x10 ) Hz

Fig.1: Least squares method with 6 poles (a) Z11,11 , (b) Z12,11
No.
1
2

Table 3.2 Poles for N = 2 (|pmax | < 400)
n=0
n=1
n=2
n=3
n=4
-1.554-12.92 -47.01-103.8-183.4-1.625-16.20 -59.94-132.8-234.9

No.
1
2
3
4
5
6
7
8
9
10

Table 3.3 Poles for N = 10 (|pmax | < 400)
n=0
n=1
n=2
n=3
n=4
-1.496-12.02 -43.61-96.25-169.9-1.515-12.25 -44.45-98.12-173.3-1.542-12.65 -45.96-101.5-179.2-1.570-13.24 -48.25-106.6-188.3-1.595-14.04 -51.36-113.6-200.7-1.615-15.01 -55.18-122.1-215.9-1.628-16.08 -59.42-131.7-232.8-1.635-17.12 -63.58-141.0-249.4-1.638-18.00 -67.07-148.9-263.4-1.639-18.57 -69.38-154.1-272.6n=5-285.7-366.1
n=5-256.5-261.4-279.2-293.3-312.6-336.4-362.9-388.8-394.9-425.0where N = 1, 2, 10 means single line, 2-coupled and 10coupled interconnects, respectively. It is remarkable thatthe number of poles for N -coupled interconnect is given by
N × (M + 1) if we consider up to n = 0, 1, . . . , M in (6).
Therefore, the number rapidly increases as M and N , andthe resulting asymptotic equivalent circuit of the interconnect will become very complicate and large scale network if
we consider all the N × (M + 1) poles.
We found from the tables that the poles for N = 1 arealways located around the center position for every nth polegroup; i.e. between No.1 and No.2 for N = 2 as shownby the table 3.2, and between No.5 and No.6 for N = 10
as shown by the table 3.3, respectively. Hence, we always
assume the 6 poles of N = 1 given by the table 3.1 in our
reduction algorithm as the approximate representative poles
in all the cases of N even if N = 100, 1000 or more.
In this case, each element given by (5) can be written withthe 6 terms in the following form;
Zkl,ij =Therefore, it is enough to choose only few elements aroundthe diagonal element in each row as the dominant elements.
Hence, each sub-matrix in (5) can be written as follows:
Zij,11

Zij,12 Zij,13 Zij,1400Zij,22 Zij,23 Zij,24 Zij,250
Zij,32 Zij,33 Zij,34 Zij,35 Zij,36
Zij,42 Zij,43 Zij,44 Zij,45 Zij,46
Zij,52 Zij,53 Zij,54 Zij,55 Zij,56
0
Zij,63 Zij,64 Zij,65 Zij,66............................................
0
0
0
0
0
0

 Zij,21
 Zij,31
 Zij,41
Zij (s)  
 0

 0


0
0
0

k6,kl,ij
k5,kl,ij+s + 202.8
s + 315.9(20)

for k, l = 1, 2, i, j = 1, 2, . . . , N .
Now, let us calculate the residues k1,kl,ij , . . . , k6,kl,ij by theapplication of the least squares method, in such a mannerthat the errors between the frequency response curve fromthe impedance matrix given by (5) and the response curve
satisfying (20) become the smallest in the frequency of interesting. The frequency response curves using the 6 poles
are shown in Fig.1 (a) and (b). They are good agreementin each other. We also found from the numerical resultsthat the value of residues far from the diagonal elements in
Zij , i, j = 1, 2 become smaller and smaller.

0
0
0
0
0

Zij,11 ≈ · · · ≈ Zij,NN , for diagonal elements
Zij,kk+1 ≈ Zij,kk−1 , Zij,kk+2 ≈ Zij,kk−2 ,Zij,kk+3 ≈ Zij,kk−3 , for nonzeo kth terms

(22)

Now, consider the asymptotic equivalent circuit model of (4)as shown in Fig.2.1(a). Using the relations (22), the terminal
voltages at the near and far ends can be written as follows:
Vk (0, s)≈k2,kl,ij
k3,kl,ij
k4,kl,ij
k1,kl,ij+++s + 1.592
s + 14.17
s + 51.88
s + 114.8
+



0
0
0
0


0
0


0
0
Zij,47
Zij,5800
Zij,57

Zij,68
Zij,6900
Zij,67
................................................
0
Zij,NN−3 Zij,NN−2 Zij,NN−1 Zij,NN(21)
for i, j = 1, 2. Furthermore, we have approximately thefollowing relations:



0
0
0
0

Vk (d, 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))(23.1)

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))(23.2)

k = 1, 2, . . . , N Z11,kk in the ﬁrst term of (23.1) andthe 5th term of (23.2) correspond to the self impedance
Z11 , Z22 , . . . , ZNN shown in Fig.2.1 (b) and Fig.2.2(b).
Other terms consist of the current controlled voltage sources
as shown Fig.2.2(a).

III-492I1(0,s)sponses without the interconnects. Observe that the response coupled with interconnects has the complicated response due to the time-delays, crosstalks, reﬂections and soon.

I1(d,s)V1(d,s)V1(0,s)I2(0,s)I2(d,s)T1

V2(0,s)V2(d,s)T2

Sub-circuit
No.1

TN

IN(0,s)Sub-circuit
No.2

5. Conclusions and remarks

VN(d,s)We proposed a reduction algorithm for large scale RCG interconnects, where they are replaced by simple asymptotic
equivalent circuits with current controlled voltage sources.
The reduction rate will be very large especially for the large
scale interconnects. Therefore, we can easily get the transient responses with the SPICE simulator. The algorithm
will be eﬃciently applied to the large scale circuits such as
gate-arrays coupled with interconnects in the substrate.

IN(d,s)VN(0,s)(a) Multi-conductor interconnect
V11,1(s) I1(0,s) I1(d,s) V12,1(s)Z 11
V11,2(s) I2(0,s) I2(d,s)V12,2(s)V1(0,s)Z 11

V2(0,s)Z22

Z22

V1(d,s)V2(d,s)Sub-circuit
No.2

Sub-circuit
No.1
V11,N(s) IN(0,s) IN(d,s) V12,N(s)ZNN

VN(0,s)ZNN

References

VN(d,s)(b) SPICE model of interconnect

Fig.2.1: SPICE model of multi-conductor interconnect

Vij,knIk+nZij,kk+n
Ik-n

Cij,1

Cij,2

Cij,6

Rij,1

Rij,2

Rij,6

Zii

(a) Current controlled voltage source

Cii,1

Cii,2

Cij,6

Rii,1

Rii,2

Rij,6

(b) Synthesis of impedance

Fig.2.2: (a) Current controlled voltage source, (b)Self-impedance

4. Illustrative examples
Consider a fulladder circuit coupled with interconnects asshown in Fig.3(a).
Half Adder 2

Half Adder 1

V1

V2

T1

T4

T2

T5

T3

T6

S

V3
C

Fig.3(a): Fulladder coupled with interconnects
d = 20 µm
(V)
6.0
4.0
V1 2.00.0
6.0
4.0
V2 2.00.0
6.0
4.0
V3 2.00.0
6.0
4.0
VS 2.00.0
6.0
4.0
VC 2.0
0.0
0.0

5.0

10.0

15.0

20.0

25.0

30.0

ps

Fig.3(b): Transient response of the fulladder circuit.
The solid lines show the responses with interconnects,
and the dotted lines the responses without the interconnects

The transient responses at the output stages are shown bysolid lines in Fig.3(b), where the dotted lines show the re-[1] M.Celik, L.Pileggi and A.Odabasioglu, IC Interconnect
Analysis, Kluwer Academic Pub., 2002.
[2] J.L.Wyatt,Jr.,“Signal propergation delay in RC models for interconnect,” Circuit Analysis, Simulation
and Design, A.E.Ruehli(Editor), Elsevier Science Pub.
B.V.(North-Holland), pp.254-291, 1987.
[3] W.C.Elmore, “The transient response of damped linear
networks with particular regard to wideband ampliﬁers,” J. Appl. Phys., vol.19, pp.55-63, Jan. 1948.
[4] T.Sakurai, “Closed-form expressions for interconnection delay, coupling, and crosstalk in VLSI’s,” IEEE
Trans. Electron Devices, vol.40, pp.118-124, 1991.
[5] S-Y.Kim, N.Gopal and L.T.Pillage, “Time-domain
macromodels for VLSI interconnect analysis,” IEEE
Trans. Computer-Aided Design, vol.13, pp.1257-1270,
1994.
[6] R.Gupta, B.Tutuianu and L.T.Pileggi, “The Elmore
delay as a bound for RC trees with generalized input
signals,” IEEE Trans. Computer-Aided Design, vol.16,
pp.95-104, 1997.
[7] C.J.Alpert, A.Devgan and C.V.Kashap, “RC delay
metrics for performance optimization,” IEEE Trans.
Computer-Aided Design, vol.20, pp.571-582, 2001.
[8] T.Kimura and M.Okumura, “An eﬃcient reduction
method of a substrate RC network model,” IEICE
Trans. Fundamentals, vol.E84-A, pp.698-704, 2001.
[9] E.Chiprout and M.S.Nakhla, Asymptotic Waveform
Evaluation and Moment Matching for Interconnect
Analysis, Kluwer Academic Pub., 1994.
[10] M.Celik, O.Ocali, M.A.Tan and A.Atalar, “Pole-zerocomputation in microwave circuits using multipoint
Padè approximation,” IEEE Trans. Circuits and Systems, vol.42, pp.6-13, 1995.
[11] A.Odabasioglu, M.Celik and L.T.Pileggi, “PRIMA:
Passive reduced-order interconnect macromodeling algorithm,” IEEE Trans. Computer Aided Design, vol.17,
pp.645-654, 1998.
[12] A.Ushida, K.Urabe, Y.Yamagami and Y.Nishio,“Asymptotic equivalent circuits of interconnects basedon complex frequency method,” ECCTD’01, vol.3,
pp.29-32, 2001.
[13] M.Bocher, Introduction to Higher Algebra, Dover, New
York, 1964.

III-493