An Efficiency Choice of Frequency Expansion Point in RLC ...



A Criterion on Selecting the Expansion Point in RCL Model Reduction by Using Krylov-subspace Methods

Abstract

Large RC(L) subcircuits generated by automatic parasitic-extraction tools are used as the typical models for interconnect of integrated circuits in recent years. In order to simulate this large-scale subcircuits easily, being an efficient choice, Krylov-subspace methods have been widely used to reduce them to a lower order circuit with less elements and internal nodes. What is more, many algorithms based on Krylov-subspace can also preserve the stability and passivity of the reduced subcircuit very well. But the selection of [pic], i.e., the expansion point, which is very important for reduced-order modeling of interconnect, still remains inefficient. This paper puts forward a very simple and efficient criterion on the selection of [pic] whose robustness and efficiency have been confirmed by the results of numerical experiments with some real interconnects.

Ⅰ. Introduction

A time-invariant multi-input multi-output linear dynamical system can be represented as,

[pic] (1)

where [pic] represents admittance matrix of the RCL circuit, [pic] represents capacitance and inductance matrix, and input and output ports characteristics are represented by [pic] and [pic] respectively. [pic] is the state variables, [pic] is the output vector, [pic] is the input vector, m is the number of input ports, and p is the number of output ports.

By Laplace transformation, the transfer function of (1) can be easily gotten as:

[pic], (2)

where G and C are often singular, but [pic] is regular, i.e., there exists a point [pic] which makes matrix [pic] nonsingular.

A reduced-order system, whose number of state variables is much smaller than the original one, has the same type as (1). The corresponding transfer function is:

[pic]. (3)

From the matrix theory we have known that the reduced network should be applied to approximate the preference of the original system if [pic] keeps all the main eigenvalues of [pic]. And at the same time it satisfies the “moment-matching” property.

Many algorithms can implement this reducing process, e.g., AWE[1], PACT[2], and so on. But AWE cannot produce high accurate reduced-order model. Although frequency scaling[1], CFH[3] and RICE[4] act as the remedies to AWE, the improvements are not good enough. PACT, whose accuracy is not determined by itself, has to resort to other algorithm, e.g., Lanczos process, to calculate the eigenvalues.

Techniques based on Krylov-subspace, where Padé approximation[5] is used, have shown obvious advantage on efficiency and accuracy. MPVL[6][7], which uses Lanczos process, is the most efficient algorithm for model reduction. PRIMA[8], into which Block Arnoldi Algorithm is built, can produce passive reduced order model for RCL network. But in these techniques, a frequency expansion point, which can affect the accuracy

of the reduced model dramatically, must be determined, especially when processing the RCL circuits. In this paper, we will derive a criterion by which the frequency expansion point can be determined much easier.

The remainder of the paper is organized as follows. In Section Ⅱ a criterion on the determination of frequency expansion point is discussed in detail. Numerical results are presented in section Ⅲ to demonstrate the feasibility of our criterion. In section Ⅳ the concluding remarks are followed.

Ⅱ. About frequency expansion point

First, we point out the relationship between the frequency expansion point and the accuracy of the reduced-order model. Look at the following expansion form of [pic] about [pic]:

[pic]

The difference between [pic] and [pic], which determines the accuracy of reduced-order model, is [pic]. For a particular Q(n), a proper [pic] means that [pic] will be much more accuracy; and for a particular accuracy, a proper [pic] means that a smaller Q(n) will be needed. What is more, in order to invert the matrix [pic], [pic] must be a value that can ensure the nonsingularity of [pic], which can be seen from the below process.

For discussing conveniently, by setting [pic] and [pic], from (2) we get,

[pic] (4)

where [pic]

By expanding (4) about [pic], we get,

[pic](5)

From (5) we define,

[pic], (6)

where [pic], and

[pic] (7)

So, [pic]. (8)

In the following, we use [pic] to represent the i-th row and j-th column element in matrix [pic], while [pic] means the n-th power of [pic]. Then from (7) we get,

[pic]. (9)

Matrix [pic] is diagonal under the condition that there are no coupling capacitors and no mutual inductors, so the equivalent form of (9) is:

[pic] where [pic] and [pic],

then we get

[pic] (10)

The diagonal elements in matrix [pic], i.e., i=j in (10), can be deduced as,

[pic] (11)

From (11), we can see that there are N series in (8), each of which is given by,

[pic] (12)

where [pic] and [pic].

It is necessary that in order to ensure the convergence of [pic] in (8), each [pic] in (12) must be convergent. And by RATIO TEST[9], we have known that the convergence range of [pic] will become smaller with the increasing of the absolute value of [pic]. In the following, we will point out that the larger elements of matrix P will usually appear at the diagonal positions.

[pic]Fig.1. An interconnect example

Recall one interconnect model in the form of RCL circuit before beginning our discussion, as shown in figure 1. Look at the circuit in the circle Ⅰ first. We call it an ORIC, which means that only One Resistor, One Inductor, and One Capacitor are connected at One node. However, the similar part in the circle Ⅱ is not an ORIC because there are two resistors connected at the same node. And as the resistor and the capacitor in circle Ⅰ as concerned, we can form the matrix [pic] and [pic] by modified nodal analysis (MNA) method,

[pic] and [pic].

Then,

[pic], (13)

So,

[pic] . (14)

From (13) and (14), we can see that the smaller one between [pic] and [pic] in matrix [pic] will determine the larger element in matrix [pic], i.e., [pic] or [pic]. We assume that there is at least one ORIC in the circuit, which means that the similar matrix structure [pic] will appear in matrix [pic] in (7), and the process of getting inverse of [pic] as in (14) will surely be included in the process of getting [pic], i.e.,[pic], in (7). So we conclude that the larger elements in matrix [pic] are determined by the smaller one between [pic] and [pic] that come from ORIC in matrix [pic]. What’s more, even if there is only one ORIC in the circuit, usually it will result in many large elements that are in diagonal and nondiagonal positions in matrix [pic], which can be understood from the process of getting the inverse of one matrix.

In order to ensure the convergence of [pic] in (8), we will choose the series that is the most difficult one to converge to discuss the convergence range. The series is given by

[pic] (15)

where [pic] [pic] and [pic] are from ORIC. By the RATIO TEST[9], it is easy to get the convergence range of series [pic] in (15),

[pic] . (16)

The length of convergence range is [pic].

We will discuss it in three cases before giving out our criterion.

CASE Ⅰ: [pic] in matrix [pic] in (7).

As we have mentioned above, the element [pic] in

matrix [pic] will be determined by [pic] in [pic] and on the magnitude of [pic], i.e., [pic]～[pic], by which the convergence range (16) can be approximated as: [pic]. It is noticeable that in order to satisfy the condition of this case, i.e., [pic] [pic] must be a very large value, e.g., [pic], because the capacitance [pic] is usually very small and [pic] is usually less than one. What is more, we are not interested in all the frequencies but a finite frequency range in the general simulations, e.g., [pic], where [pic]. So the frequencies in the convergence range now are the ones that seldom can be met during the simulations, as shown in figure 2. So when [pic], the series [pic] usually cannot converge, which leads to the simulation failure of the reduced-order model.

[pic]

Case Ⅱ: [pic]in matrix [pic] in (7).

Opposite to that in case Ⅰ, [pic] is a very small value in this second case, e.g., less than 103. Now it is [pic]in [pic] which will determine [pic] in matrix [pic], i.e., [pic]～[pic]. The convergence range (16) can be approximated as [pic]. The convergence range length [pic], which is determined by [pic], now is too small, e.g., [pic]. From the frequency axis in figure 3, we can see that it is usually located at the range of low frequencies. So in the range between [pic] and [pic], series [pic] still cannot converge. On the other hand, if there exists many similar elements as [pic] in matrix [pic], where [pic], errors caused by finite precision computation will be apparent during the process of getting the inverse of matrix. So the accuracy of the reduced-order model usually is too bad because of these two reasons.

[pic]

Case Ⅲ: [pic] in matrix [pic] in (7).

During our research, we found that when [pic], but not [pic], the simulation results of the reduced-order model are usually perfect. Similar to that in case Ⅱ, the convergence range now has the same approximation, i.e., [pic].

[pic]

But now, we prefer that the length of convergence range should be large enough, i.e., [pic] should be near [pic], as in figure 4. To satisfy this condition, it is required that [pic] be comparable to [pic] in matrix [pic]. On the other hand, the error caused by truncation in computation will be much smaller than that in case Ⅱ. So we put forward that the expansion point should be selected according to this case, as the criterion given in (17), in order to get the right reduced-order model.

Criterion: If [pic] belongs to the following range,

[pic], (17)

where [pic] and [pic] come from ORIC of the circuit, the accuracy of the reduced-order model is usually good enough.

Although the criterion (17) is given out by assuming that there are no coupling capacitors and no mutual inductors in the circuit, it is actually an unnecessary condition. As long as there is at least one ORIC in the circuit, which is often satisfied in the real interconnect model, the similar matrix form (13) will appear in matrix [pic], and the range (17) will surely come into existence. So our criterion can also be applied to the circuits having coupling capacitors and mutual inductors.

In fact, the accuracy of the reduced-order model can be improved by increasing the iterative times in the algorithm even if the expansion point is poorly selected, however it will not only loses the reduction ratio of elements and internal nodes, but expenses much more running time and memory.

On the other hand, there do exist many cases that the simulation results of reduced-order model are perfect although [pic] is not determined by our criterion. The reason of this is that the series we constructed in (15) is corresponding to the most terrible case. In many circuits, [pic] will be never multiplied with [pic], so the range in (17) will be a subset of the real convergence range. Our experience shows that the convergence usually can be ensured if the expansion point is selected by the criterion in (17). What’s more, only one [pic] is needed in the reduction, so the range (17) we gave out is already a much relaxant one.

Ⅲ. Experimental results and discussion

To show the correctness and robustness of our criterion, we will give out one example in this section.

The circuit structure in this example is a tree made up of R, C and L, e.g., Figure.5, where each segment represents a transmission line and contains several nodes and elements. For example, segment AB is composed of 32 nodes and 41 elements. There are 247 elements, including one additional capacitance added at A, and 187 nodes altogether in the circuit.

The value of each element is from the real case. By the criterion in (17), the proper expansion point should be in [pic]. So, we tried to reduce the network at three different points, i.e.,[pic], [pic] and [pic] All the reduced [pic]

[pic]

Fig.6. AC analysis of original model and reduced-order models.

[pic]

Fig.7. Transient analysis of original model and reduced-order models.

networks have 7 nodes and 56 elements, but their accuracy is quite different.

The AC and transient response of the two reduced circuits ([pic] and [pic]) and the original one are depicted in Fig.6 and Fig.7, respectively. For transient analysis, all the three circuits are excited by a same sine voltage source whose frequency is 1000MEG. As we has anticipated, the satisfying reduced order model whose error bound is only about 0.02% is gotten. when we set [pic] to [pic] which is in our range, while the error begins to be apparent when [pic] In our simulations, the results are unacceptable and wrong thoroughly if continue increasing [pic], e.g. [pic] It is noticeable that if [pic] is much smaller than the lower bound, i.e., [pic], the accuracy of the reduced network is also acceptable, which is the case that we have anticipated and discussed in section Ⅱ, but this is not the case in other circuits. However, the criterion we gave out works well for all the circuits we have tested.

Ⅳ. Concluding remarks

In this paper, a criterion is presented for the choice of the frequency expansion point used in the model-reduction techniques based on the Krylov subspace, which is a very important problem but has not been addressed in the previous work. By the proposed criterion, a proper frequency expansion point can be determined much easier than before, and the accuracy and convergence of the Krylov-subspace methods for reducing RCL network are improved because of the saving of iterative times.

References

[1] L.T.Pillage and R.A.Rohrer, “Asymptotic waveform evaluation for timing analysis”, IEEE Trans. Computer-Aided Design, 1990, 9, pp.352-366

[2] K.J.Kerns and A.T.Yang, “Stable and Efficient Reduction of Large, Multiport RC Networks by Pole Analysis via Congruence Transformations”, IEEE Trans. Computer-Aided Design, 1997, 16,No.7, pp.734-744

[3] E.Chiprout and M.S.Nakhla, “Analysis of Interconnect Networks Using Complex Frequency Hopping(CFH)”, IEEE Trans. Computer-Aided Design, 1995, 14, pp. 186-200

[4] C.L.Ratzlaff and L.T.Pillage, “RICE: Rapid Interconnect Circuit Evaluation Using AWE”, IEEE Trans. Computer-Aided Design, 1994, 13, pp.763-776

[5] P.Feldmann and R.W.Freund, “Efficient linear circuit analysis by Padé approximation via the Lanczos process”, IEEE Trans. Computer-Aided Design, 1995, 14, pp.639-649

[6] J.I.Aliaga, D.L.Boley, R.W.Freund, and V.Hernandez, “A Lanczos-type Method For Multiple Starting Vectors””,

[7] J.I.Aliaga, D.L.Boley, R.W.Freund, and V.Hernandez, “A Lanczos-type Method For Multiple Starting Vectors”,

[8] A.Odabasioglu, M.Celik, L.T.Pileggi, “PRIMA: passive reduced-order interconnect macromodeling algorithm”, in Tech.Dig. 1997 IEEE/ACM ICCAD, Nov.1997

[9] W.Kaplan, “Advanced Mathematics for Engineers”, Reading, Mass: Addison-Wesley, 1981, pp.85

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download