Interconnect model-order reduction method

1. Field of Invention

The present invention relates to an interconnect model-order reduction method. More particularly, the present invention relates to a rapid and accurate interconnect model-order reduction method for reduction of a nano-level semiconductor interconnect network for signal analysis.

2. Related Art

Complemented metal oxide semiconductor (CMOS) technology has heretofore advanced to be measured at a nano-level, and, thus, the parasitic effect to interconnects of the related semiconductor device cannot be neglected. Since the complexity of a circuit associated with the semiconductor device is increased, the order of the corresponding interconnect model is also increased. Consequently, an efficient interconnect model-order reduction has become a necessity of modeling and simulation of the interconnect network. Such methods may be referred to in, for example, U.S. Pat. Nos. 6,023,573, 6,041,170 and 6,687,658. These circuit model-order reduction methods set forth in recent years are herein summarized as follows. 1. Asymptotic waveform evaluation (AWE), which was set forth in an article by L. T. Pillage and R. A. Rohrer, entitled “Asymptotic waveform evaluation for timing analysis,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol. 9, No. 4, pp. 352-366, 1990. 2. Pade via Lanozos (PVL), which was set forth in an article by P. Feldmann and R. W. Freund, entitled “Efficient linear circuit analysis by Pad'e approximation via the Lanczos process,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol. 14 pp. 639-649, 1995. 3. Symmetric Pad'e via Lanczos, which was set forth in an article set forth by P. Feldmann and R. W. Freund, entitled “The SyMPVL algorithm and its applications to interconnect simulation,” Proc. 1997 Int. Conf. on Simulation of Semiconductor Processes and Devices, pp. 113-116, 1997. 4. Block Arnoldi, which may be seen In U.S. Pat. No. 6,810,506. 5. Passive reduced-order interconnect macromodeling (PRIMA) method, which was set forth in an article by A. Odabasioglu, M. Celik and L. T. Pileggi, “PRIMA: passive reduced-order interconnect macromodeling algorithm,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol. 17 pp. 645-653, 1998.

The above methods are performed essentially based on a Krylov Subspace projection method, in which state variables of an original system (original interconnect network for the above and original system will be used through this specification) is projected to obtain state variables of a reduced-order system (reduced interconnect model for the above and reduced-order system will be used through this specification) by use of a projection operand. The required projector may be obtained by performing the iteration-based Krylov algorithm, in which the iteration number required to be conducted is an “order” of the reduce-order system. In this case, the order of the reduced-order system has to be determined in execution of the projection-based interconnect model reduction in such a manner that essential dynamics of the original system may be accurately reflected. The iteration process may be conducted by taking a residual error between transfer functions of the original system and the reduced-order system, respectively, as a reference for an end of such iteration process, wherein the residual error is defined as an error between the transfer functions of the original and reduced-order systems after specific times of iterations.

An example of a deduction of the error E(s) between the transfer functions of the original and reduced-order systems may be seen in an article set forth by Z. Bai, R. D. Slone, W. T. Smith and Q. Ye, entitled “Error bound for reduced system model by Pad'e approximation via the Lanczos process,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol. 18 pp. 133-141, 1999. However, the error E(s) involves complicated computations of a resolvent matrix (I n −sA) −1 of the original system, making it difficult to be used in a real application.

In Light of the above, there are still some shortcomings inherent in the prior art and thus improvements therefor are in an urgent need. In this regard, after looking at the problems encountered in the prior art, an efficient interconnect model-order reduction method was successfully developed in the present invention.

It is, therefore, an object to provide an interconnect model-order reduction method for reduction of a nano-level semiconductor interconnect network as an original interconnect network into a reduced interconnect model for signal analysis by using an iteration-based Arnoldi algorithm, through which transfer functions of the original interconnect network and the reduced interconnect model is exempted from complicated computations and the reduced interconnect model may be achieved in a rapid and accurate manner.

To achieve the above object, the interconnect model-order reduction method for reduction of a nano-level semiconductor interconnect model into a reduced interconnect model for signal analysis by using the iteration-based Arnoldi algorithm comprises the steps of: inputting an interconnect network, inputting a set of frequency expansion points, establishing a state space matrix of the interconnect network and reducing the interconnect network into the reduced interconnect model by estimating a residual error.

In this method, the residual error between the original interconnect network and the reduced interconnect model is derived and the reduced interconnect model is deduced by the iteration-based Arnoldi algorithm. Further, the relationship between the residual error and the original interconnect network is presented.

In addition, the transfer function of the reduced interconnect model may be represented simply by adding some perturbations to the transfer function of the original interconnect network, in which a perturbation matrix is only related to resultant vectors obtained in the Arnoldi algorithm.

The derived error may efficiently provide a reference for an order of the reduced interconnect model selected by the Krylov subspace model reduction algorithm.

The following description is presented to enable one of ordinary skill in the art to make and use the present invention as provided within the context of a particular application and its requirements. Various modifications to the preferred embodiment will, however, be apparent to one skilled in the art, and the general principles defined herein may be applied to other embodiments. Therefore, the present invention is not intended to be limited to the particular embodiments shown and described herein, but is to be accorded the widest scope consistent with the principles and novel features herein disclosed.

FIG. 1 shows a simple interconnect network according to an embodiment of the present invention;

FIG. 2 shows a comparison between H q+1,q and μ q after different iteration times q performed according to the present invention; and

FIG. 3 shows a comparison of three systems H(s), Ĥ(s) and H Δ (s), after q times of iteration performed, according to the present invention.

In analyzing a linear RLC interconnect network in an ultra-large semiconductor circuit (ULSI), modified nodal analysis (MNA) technology is generally utilized. In performing the MNA technology, the interconnect network may be first represented as the following state space-based equation:

M ⁢ ⅆ x ⁡ ( t ) ⅆ t = - Nx ⁡ ( t ) + bu ⁡ ( t ) , y ⁡ ( t ) = c T ⁢ x ⁡ ( t ) , Eq . ⁢ ( 1 )

wherein M,N∈R n×n ,x,b,c∈R″ and y(t)∈R; and wherein M is a matrix including capacitances and inductances therein, N is a matrix including electric conductivities and resistances therein, x(t) is a state matrix including node voltages and branch currents of an inductor therein, u(t) is an input signal and y(t) is an output signal.

Now, assuming A=N −1 M and r=N −1 b, Eq. (1) may be represented as the following equation:

Now, the original interconnect network is to be reduced so as to obtain a reduced interconnect network so that essential dynamics of the original interconnect network may be accurately reflected in a lower order. A state space matrix of the reduced interconnect model is given as the following equation:

A ^ ⁢ ⅆ x ^ ⁡ ( t ) ⅆ t = x ^ ⁡ ( t ) - r ^ ⁢ u ⁡ ( t ) , y ^ ⁡ ( t ) = c ^ T ⁢ x ^ ⁡ ( t ) , ( Eq . ⁢ 3 )

wherein {circumflex over (x)}(t)∈R q ,Â∈R q×q ,{circumflex over (r)},ĉ∈R q and q<<n.

Now letting X(s)=L[x(t)] and {circumflex over (X)}(s)=L[{circumflex over (x)}(t)] be impulse responses of the original interconnect network and the reduced interconnect model, respectively, in Lapalace domain then, X(s) and {circumflex over (x)}(s) may be represented as the following equation:

X ( s )=( I n −sA ) −1 r and {circumflex over (X)} ( s )=( I n −s ) −1 {circumflex over (r)}   (Eq. 4)

wherein I n is an n×n unit matrix and I q is a q×q unit matrix.

A transfer function H(s) of the original interconnect network and a transfer function Ĥ(s) of the reduced interconnect model are represented, respectively, as H(s)=c T X(s) and Ĥ(s)=ĉ T {circumflex over (X)}(s).

A projection-based method is employed to project the state variables of the original interconnect network by use of a projector into the state variables of the reduced interconnect model, the orthogonal projector being generated by the iteration-based Krylov subspace algorithm.

In the above, the Krylov subspace K q (A,r) is generated by a combination of matrix A and r and represented by the following equation:

K q ( A,r )≡span( r,Ar,Λ,A q−1 r ).  (Eq. 5)

Next, the Krylov subspace K q (A,r) is subject to a modified Gram-Schmidt orthogonal iteration process through the Arnoldi algorithm to generate a unit orthonormal basis, which is represented as the following equation:

V q =[v 1 ,v 2 ,Λ,v q ],  (Eq. 6)

wherein V q T V q =I q . By performing the Arnoldi algorithm with q times of iteration, the following equation may be obtained:

AV q =V q H q +h q+1,q v q+1 e q T ,  (Eq. 7)

wherein H q ∈R q×q is an upper Hessenberg matrix H q , which is represented as follows.

H

q

=

After q times of iteration performed in the Arnoldi algorithm, a residual vector h q+1,q v q+1 is obtained, which has a relationship with the last unit orthogonal vector, given as the following equation:

Av q =h 1q v 1 +h 2q v 2 +Λ+h qq v q +h q+1,q v q+1 ,  (Eq. 9)

The newly generated vector v q+1 is orthogonal to the unit orthogonal matrix v q+1 V q obtained in the last iteration, i.e. V q T v q+1 =0. A vector e q is the q th column vector of the unit matrix I q . From this viewpoint, between the state variables of the original interconnect network and the reduced interconnect model exists the following relationship:

x ( t )= V q {circumflex over (x)} ( t ),  (Eq. 10)

wherein x(t) is a state variable in n dimensions for the original interconnect network and {circumflex over (x)}(t) is a state variable in q dimensions for the reduced interconnect model.

Substituting Eq. 7 into Eq. 2, the following transformation relationship may be obtained with Eq. 3 through derivations and computations:

Â=V q T AV q =H q , {circumflex over (r)}=V q T r and ĉ=V q T c   (Eq. 11)

Reducing the original interconnect network by such projection-based model-order reduction method has the advantages that dynamics of the original interconnect network may be maintained and stability and passiveness may be achieved.

Error Analysis

To estimate the error between transfer functions of the original interconnect network (Eq. 2) and the reduced interconnect model (Eq. 3), an analytical expression of an residual error E r (s) has to be first defined:

E r ( s )=( I n −sA ) {tilde over (X)} ( s )− r,   (Eq. 12)

wherein {tilde over (X)}(s) is an approximate solution of X(s). If {tilde over (X)}(s)=X(s), then E r (s)=0.

When the Arnoldi algorithm begins to be performed, the approximate solution {tilde over (X)}(s) of Eq. 4 has to fall within the Krylov subspace and {tilde over (X)}(s)=V q {circumflex over (X)}(s) in this case. The following discussion will be devoted to an ideal approximate solution of Eq. 4.

Now, assume the orthogonal matrix V q and the corresponding upper Hessenberg matrix H q in Eq. 6 are obtained after q times of iteration in performing the Arnoldi algorithm.

Next, assuming {tilde over (X)}(s) is an approximate solution of X(s), {circumflex over (X)}(s) is an approximate solution of X(s) after q times of iteration in performing the Arnoldi algorithm, i.e. {tilde over (X)}(s)=V q {circumflex over (X)}(s) and E r (s) is the residual error, then, the following statements are valid.

(a) If {tilde over (X)}(s)=V q {circumflex over (X)}(s)=V q (I q −sH q ) −1 V q T r, then a Galerkin condition is valid.

V q T E r ( s )= V q T {( I n −sA ) {tilde over (X)} ( s )− r }=0.  (Eq. 13)

(b) When the Galerkin condition is valid, the residual error E r (s) may be represented as:

E r ( s )=− sh q+1,q v q+1 e q T ( I q −sH q ) −1 {circumflex over (r)}.   (Eq. 14)

The valid statements above mentioned will be explained as follows.

After q times of iteration in performing the Arnoldi algorithm, the original interconnect network may be deduced to the reduced interconnect model as shown in Eq. 11.

(a) Since {tilde over (X)}(s)∈K q (A,r), {tilde over (X)}(s) may be obtained through a linear combination of column vectors of V q , i.e. {tilde over (X)}(s)=V q X q (s), wherein X q (s) is a coefficient. Herein, it is expected that X q (s)={circumflex over (X)}(s). The residual error E r (s) is represented as:

E r ( s )=( I n −sA ) V q X q ( s )− r.   (Eq. 15)

By multifying Eq. 15 with a matrix V q T− proceeding thereto, the following equation is obtained:

V q T ⁡ [ ( I n - sA ) ⁢ V q ⁢ X q ⁡ ( s ) - r ] = V q T ⁡ [ V q ⁢ X q ⁡ ( s ) - s ⁡ ( V q ⁢ H q + h q + 1 , q ⁢ v q + 1 ⁢ e q T ) ⁢ X q ⁡ ( s ) - r ] = ( I q - sH q ) ⁢ X q ⁡ ( s ) - r ^ . ( Eq . ⁢ 16 )

Since the unit orthogonality inherent in the Arnoldi algorithm is used, the Galerkin condition is valid when X q (s)={circumflex over (X)}(s).

(b) When the residual error is represented as the following equation:

E r ⁡ ( s ) = ⁢ ( I n - sA ) ⁢ V q ⁡ ( I q - sH q ) - 1 ⁢ r ^ - r = ⁢ [ V q ⁡ ( I q - sH q ) - ⁢ sh q + 1 , q ⁢ v q + 1 ⁢ e q T ] ⁢ ( I q - sH q ) - 1 ⁢ V q T ⁢ r - r , ( Eq . ⁢ 17 )

the following equation may be obtained after algebraic operations:

E r ( s )=− sh q+1,q v q+1 e q T ( I q −sH q ) −1 {circumflex over (r)},   (Eq. 18)

wherein r∈span{V q } and V q V q T r=r.

Hitherto, the valid statements (a) and (b) have been explained completely.

Range of the error may be derived from the following equations. Assuming each eigenvalue of H q is simple and may be decomposed as H q =S q Λ q S q −1 , Eq. 14 may be simplified as:

E r ⁡ ( s ) = - sh q + 1 , q ⁢ v q + 1 ⁢ e q T ⁢ S q ⁡ ( I q - s ⁢ ⁢ Λ q ) - 1 ⁢ S q - 1 ⁢ r ^ = - h q + 1 , q ⁢ v q + 1 ⁢ e q T ⁢ S q ⁢ Z ⁡ ( s ) ⁢ S q - 1 ⁢ r ^ , ( Eq . ⁢ 19 )

wherein

Z ⁡ ( s ) = diag ⁡ [ s 1 - s ⁢ ⁢ λ i ] i = 1 q .

Since Z(s) is a high-pass matrix,

=

Now, a norm form is obtained with respect to Eq. 19, and the following equation is obtained:

 E r ⁡ ( s )  ∞ ≤ κ ⁡ ( S q ) ⁢ 1 min ⁢  λ i  1 ≤ i ≤ q ⁢  h q + 1 , q  ⁢  r ^  2 , ( Eq . ⁢ 20 )

wherein κ(·) is a condition number of a subject matrix.

As can be known in the above, the error estimation is only related to κ(S q ), {circumflex over (r)} and h q+1,q . As compared to the error expressions set forth in the prior art, few of them take cost of the required computations into consideration. Since although κ(S q ) may reflect perturbations existed in the MNA formula, computations therefor are quite time consuming. In this regard, only h q+1,q is taken as a reference for order selection of the reduced interconnect model. In fact, h q+1,q is not directly employed but

μ q =  h q + 1 , q h q , q - 1 

is otherwise used as a reference for an end of the iteration process. If μ q is sufficiently small, the reduced interconnect model is very similar to the original interconnect.

The operation of the iteration-based Arnoldi algorithm according to the present invention is described in detail below. At first, an initial value is given. Then, the iteration process is performed during which the order of the reduced interconnect model is incremented. In each iteration performed, a new unit orthogonal vector v q is generated, and a corresponding value

μ q =  h q + 1 , q h q , q - 1 

according to the present invention is computed. When μ q is sufficiently small, the iteration process in the Arnoldi algorithm will end, and the corresponding iteration times q is taken as an optimal order number of the reduced model.

The advantages of the present invention will be demonstrated and simulation results thereof will be presented through a simple embodiment provided below.

Additive Perturbations System

In the following, a reduced-order system comparable to Eq. 11 will be deduced by adding perturbations to the original system.

Adding some perturbations into a transfer function of the original system may present a transfer function Ĥ(s) after approximation, as shown in FIG. 14 . Under the condition shown in Eq. 21, a transfer function H Δ (s) of the perturbation system is comparable to the transfer function Ĥ(s) of the reduced system.

Δ= h q+1,q v q+1,q v q T .  (Eq. 22)

This result will be explained in principle as follows.

Assuming X Δ (s)=V q {circumflex over (X)}(s), the following equation may be derived:

( I n −s ( A −Δ)) −1 r=V q ( I q −s ) −1 {circumflex over (r)}.   (Eq. 23)

Next, (I n −s(A−Δ)) is multified at the right and left sides of Eq. 23 and the following equation is obtained:

r = ⁢ ( I n - s ⁡ ( A - Δ ) ) ⁢ V q ⁡ ( I q - s ⁢ ⁢ A ^ ) - 1 ⁢ r ^ = ⁢ [ V q - s ⁡ ( V q ⁢ H q + h q + 1 , q ⁢ v q + 1 ⁢ e q T ) + s ⁢ ⁢ Δ ⁢ ⁢ V q ] ⁢ ( I q - s ⁢ ⁢ A ^ ) - 1 ⁢ V q T ⁢ r . ( Eq . ⁢ 24 )

Then, Eq. 24 is multified with V q T and then rearranged as:

( I q −s )= I q −s ( H q +h q+1,q V q T v q+1 e q T )+ sV q T ΔV q .  (Eq. 25)

Finally, the following equation is obtained:

V q T ⁢ Δ ⁢ ⁢ V q = ⁢ h q + 1 , q ⁢ V q T ⁢ v q + 1 ⁢ e q T = ⁢ h q + 1 , q ⁢ V q T ⁢ v q + 1 ⁢ e q T ⁢ V q T ⁢ V q , ( Eq . ⁢ 26 )

and may be further simplified as X Δ (s)=V q {circumflex over (X)}(s) with the assumption of Δ=h q+1,q v q+1 v q T .

The Simple Embodiment of the Present Invention

In the following, the simple embodiment is provided for test and demonstration of the Arnold algorithm, which will be described with reference to FIG. 1 corresponding to an examplary RLC interconnect network having twelve wires therein.

Parameters of the wires are given as follows: resistor: 1.0 O/cm, capacitor: 5.0 pF/cm, inductor: 1.5 nH/cm; drive resistor: 3O and load capacitor: 1.0 pF. Further, each of the wires is 30 mm long and separated into 50 sub-wires. In this embodiment, a frequency range of 0-12 GHz is selected and a frequency response voltage V out of the RLC interconnect network is determined.

When the Arnoldi algorithm begins to be performed, values of h q+1,q and μ q are recorded in sequence. The simulation results of the Arnoldi algorithm are shown in FIG. 2 . As shown, it may be seen that when iteration number q in the Arnoldi algorithm is greater than 31, μ q is relatively smaller. Accordingly, it is suggested that the order of the reduced interconnect model be set as 31. H(s), Ĥ(s) and H Δ (s) represent the transfer function of the original interconnect model, the transfer function of the reduced interconnect model after being subject to the Arnoldi algorithm and the transfer function of the perturbation system of the original interconnect network.

Referring to FIG. 3 , a comparison of the three systems H(s), Ĥ(s) and H Δ (s), after q times of iteration performed, according to the present invention is shown therein. It may be ascertained that H Δ (s) is equal to Ĥ(s).

In the present invention, the residual error between the original RLC interconnect network and the reduced interconnect model is deduced and the perturbation is demonstrated as capable of representing the transfer function after approximation when being added into the transfer function of the original interconnect network. Herein, since the perturbation matrix is only related to the resultant vectors obtained in a last iteration in the Arnoldi algorithm, the amount of computation required therefor is very small. With respect to the thus generated residual error, a reference for order selection may be provided in the projection-based model reduction method.

While embodiments and applications of this invention have been shown and described, it would be apparent to those skilled in the art having the benefit of this disclosure that many more modifications than mentioned above are possible without departing from the inventive concepts herein. The invention, therefore, is not to be restricted except in the spirit of the appended claims and their equivalents.