2005 RISP International Workshop on Nonlinear
Circuit and Signal Processing (NCSP'05)
Hawaii, USA, Mar. 4-6, 2005.

Interconnect Modeling Using Numerical Inversion of Laplace Transforms
Junji Kawata1 , Yuichi Tanji2 , Yoshifumi Nishio3 and Akio Ushida1123Tokushima Bunri University
Phone: +81-87-894-5111
Kagawa University
Tokushima University

1314-1 Shido, Sanuki, Japan
Email: kawata@fe.bunri-u.ac.jp2217-20 Hayashi, Takamatsu, Japan
2-1 Mimami-josanjima, Tokushima, Japan

Abstract

2. Calculation of Exact PolesIn this paper, the admittance matrix of RLCG interconnects
is modeled by partial fractions composed of the exact polesof the admittance matrix and the corresponding residues.
The exact poles can be obtained by applying the LeverrierFaddeeva algorithm. In this paper, a new method for calculating the residues is proposed. The residues can be calculated by using numerical inversion of Laplace transforms
and the least squares method so that the impulse or pulse response of the partial fraction is matched with the one of eachelement of the exact admittance matrix in the time-domain.
From the partial fraction representation, asymptotic equivalent circuit models suitable for SPICE-like simulators can besynthesized.

Now, consider a uniform N coupled RLCG interconnect
described by the following telegrapher’s 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 matrix 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)
1. Introduction= Pc (s)diag[coth γi (s)d]Pv (s)−1The analysis and design of high speed LSI chips are beY12 (s) = Y21 (s) ·(3)¸coming more and more important, because the sub-circuits1
= −Pc (s)diag
Pv (s)−1 
coupled with interconnects embedded in the substrate somesinh γi (s)dtimes cause the fault switching operations due to the signal
delays, crosstalks, reflections and so on [1]-[5]. One of the where¾
requirements for the detailed analysis of these effects (i.e.
diag[γi (s)2 ] = Pv (s)−1 (R + sL)(G + sC)Pv (s)signal integrity analysis) is to provide high-speed intercondiag[γi (s)2 ] = Pc (s)−1 (G + sC)(R + sL)Pc (s)nect models suitable for general-purpose circuit simulators.
(4)
The purpose of this study is to provide a passive macromodel Thus, we havefor RLCG interconnects.
Pc (s) = (R + sL)−1 Pv (s)Γ(s)(5)
From the telegrapher’s equation of the interconnect, weT−1
Pc (s) = Pv (s)(6)
first derive the admittance matrix at the near and far ends [1].
Next, each of the elements of the admittance matrix is approximated by partial fraction using some dominant poles around Observe that all the poles of admittance matrix can be foundthe origin and corresponding residues. The poles can be cal- at the locations satisfying sinh γi (s)d = 0, i = 1, 2, . . . , N .
culated by a computational method proposed in our previous Thus, we have the following theorem for calculation of thestudy [18]. The residues can be subsequently evaluated by exact poles.
using the numerical inversion of Laplace transforms and the Theorem 1: The locations of poles satisfying the relations
least squares method so that the time-domain response of the (3) are found by solving the following equation:
partial fraction matches with the one of each element of the¯³ ´2 ¯¯¯
exact admittance matrix. We show the numerical methods for¯(R + sL)(G + sC) + nπ I¯ = 0, n = 1, 2, . . . (7)¯¯calculating the exact poles and the corresponding residues indSect. 2 and Sect. 3, respectively. Section 4 gives illustrative
where d is the length of the interconnect.
examples.

- 511 -

Proof: In the case of n 6= 0, we have from (3) that the poles element of the exact admittance matrix. In this paper, wesatisfy the following relations:
propose an another method to compute the residues by using
the numerical inversion of Laplace transforms and the least−1|Pv (s)diag[sinh γi (s)d]Pc (s) | = 0(8)squares method.
|Pv (s)diag[tanh γi (s)d]Pc (s)−1 | = 0(9)Given a Laplace transform V (s), the time domain responsev(t) can be calculated by the following formula:
Since the transfer matrices Pv (s) and Pc (s) are nonsingulareat
for the nonzero eigenvalues, the poles satisfying the above×v(tn ) =T" (K−1#)
two relations are given by
(13)
´
X ³
jkπ j2k(π/K)n1

Proof: We have γi = 0 at n = 0. Thus, using the relationof (5), we have the following relation;·¸
lim Pc (s)diag==

1
Pv (s)−1sinh γi (s)d(R + sL)−1 Pv (s)diag[γi (s)]1
(R + sL)−1
d

a+

k=0

Therefore, the characteristic equation from the telegrapher’sequation (1) needs to satisfy the relation (7).
Q.E.D.
Corollary 1.1: The poles at n = 0 satisfy the following
relation:|R + sL| = 0
(10)

γi →0

V

Re

γi (s)d = jnπ, i = 1, 2, . . . , N, n = 1, 2, . . .

T

e

−

2

V (a)

In this section, a novel algorithm for the residues evaluation
using the time-domain responses of the admittance matrix ispresented. With simplified notation for the partial fraction(12), the frequency-domain response of the partial fraction
for an external input E(s) is given byˆ = Ŷ (s)E(s)
I(s)
( N
)
N
M
X k0,mX
b1,m s + b0,mE(s)=+s − p0,m m=1 s2 + a1,m s + a0,m
m=1

1
Pv (s)−1diag[γi (s)d]
(11)

=

N
X
m=1

Iˆ0,m (s) +N
M
XIˆ1,m (s)

(14)

m=1

Then the time-domain response for (14) can be obtained by
Q.E.D.
N
M
N
X
X
The exact poles for (7) can be calculated by using theî1,m (t)(15)
î0,m (t) +î(t) =
Leverrier-Faddeeva algorithm [17]. The detail has been
m=1
m=1
shown in [18].
We choose the dominant poles located around the origin of wherenothe complex plane, because the poles have large impact onî0,m (t) = L−1 Iˆ0,m (s) ,the transient responses. Thus, an arbitrary (i, j)-element ofnothe admittance matrix given by (3) is approximated by partialî1,m (t) = L−1 Iˆ1,m (s)fraction composed of the dominant poles and the corresponding residues, in the following form:
and these responses in (15) are calculated by the numerical inversion of Laplace transforms (13). If a suitŶ (s) =(
)
N
M
X
X
(12) able set of residues is found, the time-domain responsek0,ib1,i,n s + b0,i,n+î(t) coincides with one of the exact admittance matrix2s − p0,i n=1 s + a1,i,n s + a0,i,ni=1i(t) = L−1 {Y (s)E(s)}. Thus, assigning Iˆ1,m (s) andˆ
where N is the number of conductors and M shows the num- I0,m (s) into (13), rearranging with respect to the residues
ber of complex conjugate pairs for each γi (s). We can derive {k0,m , b1,m , b0,m }, and considering the condition i(tn ) =asymptotic equivalent circuit models that satisfy the relation î(tn ) to be satisfied for any sampled time tn (n = 1, . . . , K −(12), but omit in this paper due to space limitation (refer to 1), we have
AX = B(16)[18] for detail).
where X is unknown vector containing the residues and B
3. Calculation of Residues with Numerical Inversion of is column vector consists of the time-domain responses for
Laplace Transforms
each element of the exact admittance matrix, which have to be
The residues have to be evaluated in order to approximate calculated by the numerical inversion of Laplace transforms
each element of the exact admittance matrix (3) with partial (13) in advance.
£¤Tfraction (12). In our previous study [18], the residues are
k0,1 · · · k0,N b1,1 b0,1 · · · b1,N M b0,N M
X =calculated in the frequency-domain so that the frequency re£¤Ti(t0 ) i(t1 ) · · · i(tK−1 )Y =sponse curve of the partial fraction matches to the one of each

- 512 -

0.03

0.03

exact Y11
M=10

i11(t)

0.02

i11(t)

0.02

exact Y11
M=20

0.01

0.01

0

0
0

2

4

6

8

10

12

0

2

4

6

t [nsec]t [nsec](a) M = 10(b) M = 20

8

10

12

Figure 1: Pulse response waveforms i11 (t) and î11 (t) for single conductor interconnect.
1.0

exact Y11
M=50

0.8

0.6

0.6

0.4

0.4

i11(t)

i11(t)

1.0

exact Y11
M=40

0.8

0.2

0.2

0.0

0.0

-0.2

-0.2

-0.4

-0.4
0

2

4

6
t [nsec]

8

10

12

0

2

4

(a) M = 40

6t [nsec]

8

10

12

(b) M = 50

Figure 2: Impulse response waveforms i11 (t) and î11 (t) for single conductor interconnect.
Each element of A is given as:

1 ns

RS

atn

e
An,m =
T
" (
)
#
K−1
X E(sk )ej2k(π/K)n1 E(a)× Re− ·,sk − p0,m2 a − p0,mk=0
m = 1, · · · , N

5V

1 .2 ns

where sk = a + jπk/T . The least squares solution X canbe found by using QR factorization so that ||B − AX||2 isminimized.
4. Illustrative Examples
First, we compute the exact poles by means of the method
described in Sect. 2. The parameters of interconnects are set
as follows:
L = 10[nH/mm],
d = 5.0[m]C = 4[pF/mm],v(0,t)v(d,t)

RL

Figure 3: Simple linear circuit with single conductor interconnect. (RS = 10[Ω], RL = 10[Ω])


eatn


An,(N +2m−1) =" (K−1 T) 
X E(sk )ej2k(π/K)n sk



× Re


s2k + a1,m sk + a0,m


k=0

¸


1
E(a)a


− · 2

2 a + a1,m a + a0,m
,
atn
e


An,(N +2m) =" (K−1T) X E(sk )ej2k(π/K)n



× Re

2

sk + a1,m sk + a0,m


k=0
¸



E(a)
1


− · 2
2 a + a1,m a + a0,mm = 1, · · · , N M

R = 0.5[Ω/mm],
G = 0.5[mS/mm],+−

and the parameters of the numerical inversion of Laplacetransforms are fixed as a = 0.2, K = 500 throughout thispaper. Using the exact poles, we calculated the residues with
our proposed method. As the external input E(s), both casesof pulse and impulse are considered. It is assumed that the
input pulse and the period for calculating the time-domain
responses are the same as those used in the transient simulation. The pulse response waveforms for the partial fraction
and the exact admittance matrix with varying the value of
M are shown in Fig. 1. Where, the time-domain responsesof the partial fractions are computed by (12) after evaluating
the residues. The pulse response waveforms of the partial
fractions approach those of exact admittance matrix as M increases, and the former almost matches to the latter for thecase of M = 20. While on the other hand, the impulse responses of the partial fractions do not match to the one ofexact admittance matrix until M = 50, as shown in Fig. 2. It
can be expected that this is due to the bandwidth of input signal. Thus it is reasonable to employ the pulse input from theviewpoint of computational costs and hereinafter we focus on
only the pulse responses.
Next the transient simulations are carried out. As an ex-- 513 -

0.5

0.20

exact
M=20

0.4

exact
M=20

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

0.3
0.2
0.1

0.10
0.05

0.0
0.00

-0.1
-0.2

-0.05
0

2

4

6

8

10

12

0

t [nsec]

2

4

6

8

10

12

t [nsec](a) near end. M = 20(b) far end. M = 20

Figure 4: Transient responses for example circuit shown in Fig. 5.

ample, a simple linear circuit with a single conductor interconnect shown in Fig. 5 is simulated by using the numerical inversion of Laplace transforms for the exact admittancematrix (3) and the approximated partial fractions (12). Notethat the numerical inversion of Laplace transforms can be applied to only linear circuits, but we use this method in order
to investigate the effects of the reduction approximating theadmittance matrix with the partial fractions. Fig. 6 shows thetransient response waveforms, where the pulse input shownin Fig. 5 is applied for the residues calculations. We foundthat the transient responses for the partial fractions with theresidues obtained by our proposed method approximately coincide with those of the exact admittance matrix.
5. Conclusions
In this paper, we have proposed an algorithm for calculating the residues which are required for partial fraction approximation of the admittance matrix of interconnects. The
residues can be calculated by means of the numerical inversion of Laplace transforms and the least squares method sothat the time-domain responses of the partial fraction match
to those of the exact admittance matrix. In our simulations, it
has been shown that lower order of approximation is possible
fitting by pulse response waveforms.
In future, we will carry out the transient simulations bymaking use of the asymptotic equivalent circuits and comparewith the results obtained using the SPICE simulator.
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.
[7] 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.
[8] 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.
[9] T. Kimura and M. Okumura, “An efficient reduction method ofa substrate RC network model,” IEICE Trans. Fundamentals,
vol. E84-A, pp. 698–704, 2001.
[10] E. Chiprout and M. S. Nakhla, Asymptotic Waveform Evaluation and Moment Matching for Interconnect Analysis, Kluwer
Academic Pub., 1994.
[11] E. Chiprout and M. S. Nakhla, “ Analysis of interconnect networks using complex frequency hopping(CHF),” IEEE Trans.
Computer Aided Design, vol. CAD-14, pp. 186–200, 1995.
[12] Q. Yu, J. Meiling and E. S. Kuh, “Passive multipoint moment matching model order reduction algorithm on multiport
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] 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.
[18] 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.
[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.

- 514 -