2004 RISP International Workshop on Nonlinear
Circuit and Signal Processing (NCSP'04)
Hawaii, USA, Mar. 5-7, 2004.

A Reduction Technique for RLCG Interconnects Using Least Squares Method
Junji Kawata1 , Yuichi Tanji2 , Yoshifumi Nishio3 and Akio Ushida1
1 Tokushima Bunri University,
1314-1 Shido, Sanuki-shi, Japan
2 Kagawa University,
3 Tokushima University,{kawata,ushida}@fe.bunri-u.ac.jp
Phone/FAX:+81-87-894-5111/+81-87-894-4201
tanji@eng.kagawa-u.ac.jp
nishio@ee.tokushima-u.ac.jp

1. Introduction
The analysis and design of high speed LSI chips are becoming more and more important, because the sub-circuits
coupled with interconnects embedded in the substrate sometimes cause the fault switching operations due to the signal
delays, crosstalks, reflections and so on [1]-[5]. The Elmore
resistance-capacitance (RC) delay metric is popular due toits simple closed-form expression, computation speed and fidelity with respect to the simulation [4]. The closed-form
combining with the delay and crosstalk is firstly presented in
the reference [5]. The modified algorithms are proposed later
for the improvement of the accuracy and the practical applications in the simulations [6]-[9].
Nowadays, AWE (asymptotic waveform evaluation
method) [10] is widely used as a reduction technique of thelarge scale networks coupled with interconnects, the algorithm is based on a moment-matching technique and Padé
approximation. However, the method sometimes become
erroneous, if there exist the poles far from the origin. To
overcome the problem, CFH (complex frequency hopping)[11] and multi-point Padé approximation [12] methods areproposed. In these reduction algorithms, the reduced circuits
sometimes become unstable in the time domain even if all
the poles are located in the left hand side of the complex
plane. The ill-condition can be overcome by PVL (Padé via
Lanczos process) [13], and PRIMA (passive reduced-orderinterconnect macromodeling algorithm) [2,14]. In order toapply these algorithms to the interconnects, we need two
steps such that each interconnect is firstly modeled by a finite
order system, and Arnoldi-based congruence transformation
is applied to the system to form its reduced order model.
In this paper, we consider LSIs such as ASIC or SoC (System on a Chip) are coupled with interconnects embedded in
the substrate. In this case, the diffusion resistance components of the interconnects are generally assumed to be verylarge compared to those of PCBs [3] and the lengths are very
short. From the telegraph equation to interconnect, The admittance matrices can be derived from the relations at thenear and far ends [1]. We propose here a new computational algorithm for calculating the exact poles in the complex

plane. Next, each of the elements of the admittance matrices is approximated by partial fraction using a few dominantpoles around the origin, where the corresponding residues areevaluated by either a theoretical method or the least squares
method. The latter method will be useful for relatively large
scale multi-conductor interconnects. Thus, the admittancematrices are reduced as the partial fractions by which it ispossible to derive asymptotic equivalent circuits. We show
the numerical methods for calculating the poles and residues
in section 2. Illustrative examples are given in section 3.
2. Calculation of exact poles and residues
Now, consider a uniform N coupled RLCG interconnect
described by the following telegraph equations;dV(x, s)= −(R + sL)I(x, s) dx
(1)dI(x, s)= −(G + sC)V(x, s) dx
The input and output relations at the near and far ends aredescribed by the admittance matrices as follows [1]:
·
¸ ·
¸·
¸
I(0, s)Y11 (s) Y12 (s)V(0, s)=(2)−I(d, s)Y21 (s) Y22 (s)V(d, s)where, using the eigenvalues Γ(s) = diag[γi (s)], we havethe following relations;¾
Y11 (s) = Y22 (s) = Pc (s)diag[coth γi (s)d]Pv (s)−1Y12 (s) = Y21 (s) = Pc (s)diag[sinh γi (s)d]−1 Pv (s)−1
(3)
where
¾
diag[γi (s)2 ] = Pv (s)−1 (R + sL)(G + sC)Pv (s)diag[γi (s)2 ] = Pc (s)−1 (G + sC)(R + sL)Pc (s)Thus, we have

- 371 -Pc (s) = (R + sL)−1 Pv (s)Γ(s)(4.1)

PTc (s) = Pv (s)−1(4.2)

Observe that all the poles of admittance matrices can be found where αk (s) is given by the following relations:at the locations satisfying sinh γi (s) = 0, i = 1, 2, . . . , N .
BN −1 = I,
Thus, we have the following theorem for calculations of the⇒ αN −1 (s) = −tr(A(s))
exact poles.
BN −2 (s) = A(s)BN −1 + αN −1 (s)I,
Theorem 1: The locations of poles satisfying relations (3)1
tr(B(s)A(s))
⇒
α
(s)
=
−
N −2
N −2
(12)
are found by solving the following equation:2............................................
¯
³ ´2 ¯¯¯
B0 (s) = A(s)B1 (s) + α1 (s)I,¯(R + sL)(G + sC) + nπ I¯ = 0, n = 1, 2, . . . (5)


¯
¯

1
d

⇒ α0 (s) = − tr(B0 (s)A(s))
N
where d is the length of interconnect.
Note that the maximum degree of (11) eventually becomes
Proof: In the case of n 6= 0, we have from (3) that the poles 2N , because αk (s) is polynomial with s. This algebraic
satisfy the following relation:
equation can be numerically solved by the use of Bairstow
method and so on. In this way, we can calculate the exact|Pv (s)diag[sinh γi (s)d]Pc (s)−1 | = 0(6.1) poles of the admittance matrices (3).
Then the corresponding residues are calculated by either
andtheleast squares method or a theoretical method. The detail|Pv (s)diag[tanh γi (s)d]Pc (s)−1 | = 0(6.2) of the theoretical method can be found in [17].
We choose the dominant poles located around the origin ofSince the transfer matrices Pv (s) and Pc (s) are nonsingularcomplexplane, because such poles will have a great effect onfor the nonzero eigenvalues, the poles satisfying the abovethetransient
response. On the contrary, the poles stay away
two relations are given by
from the origin will give only small effect. Thus, the admitγi (s)d = jnπ, i = 1, 2, . . . , N, n = 1, 2, . . . (7) tance matrices given by (3) are approximated by the partial
fractions, which consist of the dominant poles and the correTherefore, the characteristic equation from the telegraph sponding residues, in the following form:
equation (1) has to satisfy the relation (5).
Y11,ij (s) = Y22,ij (s) =Q.E.D.
MX
k1,ij
skC1,k,1,ij + kC0,k,1,ij(13.1)
Corollary 1.1: The poles at n = 0 satisfy the following+
2s + p0s + aC,k s + bC,krelation;
k=1|R + sL| = 0(8)

Proof: We have γi = 0 at n = 0. Thus, using the relationsof (4), we have the following relation;
lim Pc (s)diag[sinh γi (s)d]−1 Pv (s)−1γi →01= (R + sL)−1 Pv (s)diag[γi (s)]Pv (s)−1diag[γi (s)d]1= (R + sL)−1d(9)
Q.E.D.

Y12,ij (s) = Y21,ij (s) =
M
X
k2,ij
skC1,k,2,ij + kC0,k,2,ij+
s + p0s2 + aC,k s + bC,k(13.2)

k=1

where M shows the number of complex conjugate pairs. As
shown in [17], the absolute values of k2,ij , kC1,k,2,ij andkC0,k,2,ij are equal to k1,ij , kC1,k,1,ij and kC0,k,1,ij , respectively, but they alternately contain negative sign. Therefore,
the relation (2) can be written as follows;·¸
I(0, s)=−I(d, s)In generally, it is not easy to calculate the poles using the·¸·¸
Ya (s) + Yb (s) Ya (s) − Yb (s)V(0, s)relation (5). Hence, we apply Leverrier-Faddeeva algorithm
Ya (s) − Yb (s) Ya (s) + Yb (s)V(d, s)[16] for getting the characteristic equation of |sI − A| = 0 to
(14)
the relation (5). We set in (5)Wecanderiveasymptotic
equivalentcircuitmodelsthat
sat¸·³ nπ ´2isfy
therelations
(13)
and
(14),
but
omit
in
this
paper
due
to
I + s2 LC
A(s) = −(RC + LG)−1 RG +space limitation (refer to [17] for detail).
d(10)Then, we have
3. Illustrative example|sI − A(s)| = α0 (s) + sα1 (s) + · · · + sN −1 αN −1 (s) + sN
At first, we investigate the distribution of poles in the com(11) plex plane. The parameters of interconnects are set as fol-

- 372 -

Imag[γι]

25
20
15
10

35

n=0
n=1
n=2
n=3
n=4
n=5
n=6
n=7
n=8
n=9
n=10

30
25
20
15
10

5

5

0
-0.7

0
-0.7

-0.6

-0.5

-0.4
-0.3
Re[γι]

-0.2

-0.1

0

35

n=0
n=1
n=2
n=3
n=4
n=5
n=6
n=7
n=8
n=9
n=10

30
25
Imag[γι]30

Imag[γι]

35

20
15
10

n=0
n=1
n=2
n=3
n=4
n=5
n=6
n=7
n=8
n=9
n=10

5
-0.6

-0.5

-0.4
-0.3
Re[γι]

-0.2

-0.1

0
-0.7

0

-0.6

-0.5

-0.4
-0.3
Re[γι]

-0.2

-0.1

0

(a)
(b)
(c)
Fig. 1 Distribution of poles for 4-conductor interconnects. Poles with negative imaginary part are not included.
(a) r = 0.5[Ω/mm], d = 5.0[mm], (b) r = 0.5[Ω/mm], d = 1.0[mm], (c) r = 5.0[Ω/mm], d = 5.0[mm].
0.5
0.4

exact
least square

0.4

0.3

|Y12|

|Y11|

0.5

exact
least square

0.2
0.1

0.3
0.2
0.1

0

0
0

1

2

3

4

5

6

7

8

0

1

2

3

f [GHz]

4

5

6

7

8

f [GHz](a) |Y11 (jω)|(b) |Y12 (jω)|

Fig. 2 Frequency response curves for single conductor interconnect. M = 10

lows:
Ri,i = r[Ω/mm], other elements of R are 0.
Li,i = 10[nH/mm], Li,i+1 = Li−1,i = 1[nH/mm],
Li,i+2 = Li−2,i = 0.1[nH/mm], other elements of L are 0.
Ci,i = 4[pF/mm], Ci,i+1 = Ci−1,i = −0.21[pF/mm],
Ci,i+2 = Ci−2,i = −0.01[pF/mm], other elements of C are 0.
Gi,i = 0.5[mS/mm], Gi,i+1 = Gi−1,i = −0.05[mS/mm],
Gi,i+2 = Gi−2,i = −0.01[mS/mm], other elements of G are 0.

Both curves have relatively good agreement up to 11-th peakaround 5 [GHz], because we took a real pole and 10 pairs ofcomplex conjugate poles. For multi-conductor interconnects,
we confirmed that the approximated curves are relatively consistent with the exact one, although due to the effects of coupling the shapes of the curves become more complicated thanthose of single conductor interconnect.
1 ns

Fig. 1 shows the distribution of poles for 4-conductor interconnects. Observe that they consist of N real poles and thecomplex conjugate poles for each n in (5). As shown in Fig.
1 the imaginary parts of the complex conjugate poles increase
monotonically as n in (5). We found that the imaginary partsof the poles for short length interconnect become quickly
large for n, Also the real parts of the poles become large, as
the resistance component r of interconnect increases. Therefore, we will need to take into account only a few dominantpoles for either short-length interconnects or high-resistanceone, such as ASIC, SoC and so on.
It is also found that the poles for N = 1 always locate
around the center position of pole distributions for anotherN . This means that the reduction technique for RCG interconnects [18] may be applicable to RLCG interconnects.
Using these exact poles, we calculated the residues by theleast squares method. The frequency response curves approximated by substituting the obtained residues and poles to thepartial fraction (13) and the exact curves obtained from (3) for
single conductor interconnect are shown in Fig. 2. As foundform this figure, the frequency response curves of the admittance matrices have many peaks correspond to the poles.

RS
5V

1 .2 ns+−v(0,t)v(d,t)

RL

Fig. 3 Simple linear circuit with single conductor interconnect.
r = 0.5[Ω/mm], d = 5.0[mm], RS = 10[Ω], RL = 10[Ω]Next, by using the numerical inverse Laplace transformation [19], a simple linear circuit with a single conductor interconnect shown in Fig. 3 is simulated for both the exact admittance matrices (3) and the approximated partial fractions (13).
The parameters of the method are a = 0.2, K = 512. Notethat the numerical inverse Laplace transformation method canbe applied to only linear circuits, but we use this method inorder to investigate the effects of the reduction approximating the admittance matrices (3) with the partial fractions (13).
Fig. 4 shows the transient response waveforms. We foundthat the more the number of poles increases, the more both
waveforms are well in agreement.
4. Conclusions and remarks- 373 -

0.5

exact
M=25

0.4

0.3

0.3

v(0,t) [V]v(0,t) [V]

0.5

exact
M=5

0.4

0.2
0.1

0.2
0.1

0

0

-0.1

-0.1
0

2

4

6
t [nsec]

8

10

12

0

2

(a) near end. M = 56t [nsec]

8

10

12

(b) near end. M = 25

0.2

0.2

exact
M=5

exact
M=25

0.15
v(d,t) [V]

0.15v(d,t) [V]

4

0.1
0.05

0.1
0.05

0

0

-0.05

-0.05
0

2

4

6

8

10

12

0

2

4

t [nsec]

6

8

10

12

t [nsec](c) far end. M = 5(d) far end. M = 25

Fig. 4 Transient response for simple linear circuit of Fig. 3.

In this paper, we have proposed an algorithm for calculat- [7] R. Gupta, B. Tutuianu and L. T. Pileggi, “The Elmore delay
as a bound for RC trees with generalized input signals,” IEEEing the exact poles, the corresponding residues are estimatedTrans. Computer-Aided Design, vol. 16, pp. 95–104, 1997.
by the least squares method. Using the poles and residues,[8] C. J. Alpert, A. Devgan and C. V. Kashap, “RC delay metrics
each element of the admittance matrices of interconnects isfor performance optimization,” IEEE Trans. Computer-Aided
approximated by partial fraction.
Design, vol. 20, pp. 571–582, 2001.
In our simulations, it has been shown that the exact fre- [9] T. Kimura and M. Okumura, “An efficient reduction method ofa substrate RC network model,” IEICE Trans. Fundamentals,
quency response curves and the curves approximated by parvol. E84-A, pp. 698–704, 2001.
tial fractions have relatively good agreement. Further from [10] E. Chiprout and M. S. Nakhla, Asymptotic Waveform Evaluatransient simulation making use of the numerical inverse oftion and Moment Matching for Interconnect Analysis, Kluwer
Academic Pub., 1994.
Lapalace transforms, the response waveforms obtained by our
method become more accurate, as the number M of the com- [11] E. Chiprout and M. S. Nakhla, “ Analysis of interconnect networks using complex frequency hopping(CHF),” IEEE Trans.
plex conjugate pairs increases.
Computer Aided Design, vol. CAD-14, pp. 186–200, 1995.
In future, we intend to find analytically the residues and [12] Q. Yu, J. Meiling and E. S. Kuh, “Passive multipoint moment matching model order reduction algorithm on multiportcompare the results obtained in this paper.
References[1] J. A. Brandao Faria, Multiconductor Transmission-Line Structures: Modal Analysis Techniques, John Wiley and Sons, Inc.,
1993.
[2] M. Celik, L. Pileggi and A. Odabasioglu, IC Interconnect
Analysis, Kluwer Academic Pub., 2002.
[3] J. L. Wyatt, Jr.,“Signal propagation delay in RC models forinterconnect,” Circuit Analysis, Simulation and Design, A.
E. Ruehli(Editor), Elsevier Science Pub. B.V.(North-Holland),pp. 254–291, 1987.
[4] W. C. Elmore, “The transient response of damped linear networks with particular regard to wideband amplifiers,” J. Appl.
Phys., vol. 19, pp. 55–63, Jan. 1948.
[5] T. Sakurai, “Closed-form expressions for interconnection delay, coupling, and crosstalk in VLSI’s,” IEEE Trans. Electron
Devices, vol. 40, pp. 118–124, 1991.
[6] 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.

distributed interconnect networks,” IEEE Trans. Circuits andSystems-I, vol. 46, pp. 140–160, 1999.
[13] P. Feldmann and R. W. Freund, “Efficient linear analysis byPadé approximation via the Lanczos process,” IEEE Trans.
Computer Aided Design, vol. CAD-14, pp. 639–649, 1995.
[14] 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.
[15] A. Ushida, K. Urabe, Y. Yamagami and Y. Nishio, “Asymptotic equivalent circuits of interconnects based on complex frequency method,” ECCTD’01, vol. 3, pp.29–32, 2001.
[16] D. K. Faddeeva and V. N. Faddeeva Computational Methodsof Linear Algebra, W. H. Freeman and Co., 1963.
[17] J. Kawata, Y. Tanji, Y. Nishio and A. Ushida, “Asymptotic
equivalent circuits of interconnects and the passivity,” Tech.
Rep. of IEICE, no.NLP2003-134, pp.43–48, 2003.
[18] Y. Yamagami, Y. Nishio, A. Hattori and A. Ushida, n“A reduction technique of large scale RCG interconnects in complex
frequency domain,” ISCAS’03, vol. 3, pp.490–493, 2003.
[19] A. Yonemoto, T. Hisakado, and K. Okumura, “An improvement of convergence of FFT-based numerical inversion of
Laplace transforms”, ISCAS’02, vol. V, pp. 769–772, 2002.

- 374 -