Method for generating a reduced order model of an electronic circuit

A method for model reduction (48) for electronic circuit simulation (52) of an electronic circuit using multipoint matrix Pade approximation is provided herein. Using the method, state equations are generated from a linear circuit to be analyzed. One or more expansion frequencies and a number of moments for each of the one or more expansion frequencies are provided. Starting block Lanczos vectors using a first expansion frequency of the one or more expansion frequencies and the state equations are generated. New block Lanczos vectors are generated from the starting block Lanczos vectors. The new block Lanczos vectors are scaled and normalized. Breakdowns in the new block Lanczos vectors are detected and treated to generate new starting block Lanczos vectors.

FIELD OF THE INVENTION 
The present invention generally relates to electronic circuit modeling, and 
more specifically to a method for generating a reduced order model of an 
electronic circuit. 
BACKGROUND OF THE INVENTION 
The problem addressed here is the accurate and efficient computation of 
reduced order macromodels for large and complex linear circuit models to 
be used in circuit simulation and/or timing verification. Interconnect and 
parasitic effects are pervasive in all types of designs including digital, 
analog, and mixed signal designs. The computational costs due to the size 
and complexity of these circuit models is a major bottleneck in the 
verification of these designs. Therefore, a technique to provide accurate 
and compact macromodels of these linear circuits will have a significant 
impact on overall design cycle time. 
In the early 80's as clock rates steadily increased to the point where 
interconnect effects could no longer be ignored in digital designs, the RC 
tree method was developed to provide quick delay estimation for timing 
verification. This technique has limited applicability because of its 
specific nature. The need was ripe for a general method of efficient delay 
estimation for linear interconnect circuits, and the Asymptotic Waveform 
Evaluation (AWE) technique was developed to address that need. The trends 
in electronic circuit and system designs have continued to accentuate that 
need as well as other needs. 
Two recent trends in integrated circuit designs have brought out the 
importance of interconnect and parasitic effects in design verification: 
the evolution towards submicron designs and the rapid growth of 
telecommunication/RF circuit designs. The combination of high frequencies 
and high packaging densities in these designs has quickly increased the 
size as well as the complexity of the linear circuit models for circuit 
simulation and timing verification. 
Therefore, there is a need for a general tool to provide accurate and 
compact reduced order macromodeling of these linear circuit models to 
significantly improve the throughput of circuit simulation as well as 
timing verification, which in turn will improve the total design cycle 
time. In order to facilitate the discussion of different innovations that 
have been developed and applied to the problem of model reduction for 
circuit simulation and timing verification, various issue and problems are 
listed below: 
1. Generality: The method must be able to handle general linear multiport 
circuits or networks. 
2. Flexibility: The method must be able to provide models of variable 
accuracy as required by a given problem. 
3. Accuracy: The method must be able to provide accurate approximations or 
reduced order models over a wide range of frequency both in frequency and 
in the time domain if necessary. 
4. Efficiency: The method needs to provide as compact a reduced model as 
possible for simulation/verification efficiency. 
Three different prior art approaches are discussed below. The first include 
explicit moment matching techniques. The AWE technique was developed 
initially as a general technique to compute reduced order models of linear 
lumped circuits. This technique was later improved to handle distributed 
circuits. Two different implementations of the AWE technique have been 
patented (see U.S. Pat. No. 5,313,398 and U.S. Pat. No. 5,379,231). AWE 
was the first major application of explicit moment matching techniques for 
computing partial Pade approximations to the simulation of large 
interconnect circuits. One problem with this type of technique is the loss 
of numerical precision as the order of the approximation is increased. 
This problem limits the applicability of AWE in terms of approximations 
such as pole/zero analysis of analog circuits and transmission line 
modeling where high accuracy, i.e., high order approximation, is required. 
Complex Frequency Hopping (CFH) and multipoint Pade techniques have been 
developed to address the numerical precision problems of AWE. These 
techniques alleviate the numerical precision problem of AWE and allow 
higher order approximations to be computed. However, these problems are 
not completely solved by CFH and multipoint Pade techniques because both 
are still explicit moment matching methods. The loss of numerical 
precision for high order approximations is inherent in explicit moment 
matching techniques. In addition, these two techniques also incur 
significantly more computational cost than AWE, thus losing the key 
efficiency advantage of AWE. 
The second approach includes the use of scaler Lanczos base algorithms. 
Scaler Lanczos techniques address the numerical precision problem 
described above. They are as efficient as AWE while allowing very high 
order approximations to be computed accurately. The remaining problems 
that affect the overall efficiency and accuracy of simulation and 
verification are enumerated below for the convenience of discussion: 
(a) Unnecessary high order approximations (loss of compactness) due to the 
scalar nature of the underlying algorithm (one port at a time), 
(b) Unnecessary high order approximations due to expansion about a single 
frequency, and 
(c) stability of the reduced model. 
Problem (a) is also inherent in the techniques described in AWE above. The 
scalar Lanczos based techniques have been extended to the block version to 
address this problem. These techniques are described in the Block Lanczos 
algorithms below. No block (multiport) version of the techniques described 
in AWE have been developed or reported. Problem (c) is related to problem 
(b) in the sense that too high an approximation around one expansion 
frequency may not ensure the stability of the reduced model. Rational 
Lanczos algorithms are developed to compute multipoint partial Pade 
approximations, i.e., approximations about multiple expansion frequency 
points. These techniques address problems (b) and (c), but do not address 
problem (a). 
The third potential solution is the use of Block Lanczos algorithms. These 
techniques have been used to address problem (a) above by taking into 
account the interaction among ports to improve compactness of the reduced 
model. The scalar algorithm just processes one port at a time and does not 
take into account their interaction, thus not allowing common information 
to be shared by the approximation for each port. Problems (b) and (c) are 
not addressed by the Block Lanczos algorithms.

DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT 
The method described in this patent application can be called "Rational 
Block Lanczos" to be consistent with the literature in numerical linear 
algebra. It is an algorithm used in model reduction of an electronic 
circuit. One feature of this method is that it computes multipoint matrix 
Pade approximations of a linear system. It can improve the efficiency of 
generating a reduced model by approximately 20%-300% compared to existing 
techniques based on the results obtained so far. The application of this 
technique in a circuit simulator such as Motorola's MC-SPICE circuit 
simulator has the potential for improving simulation efficiency by many 
orders of magnitude while maintaining excellent accuracy. This technique 
can also be applied to timing verification of electronic circuits and 
systems where path delays must be computed efficiently and accurately. 
FIG. 1 illustrates how the rational block Lanczos method can be used in 
circuit simulation or timing verification. 
FIG. 1 is a block diagram illustrating a system in accordance with the 
present invention. A user supplied netlist 40 is split by splitter 42 into 
nonlinear subcircuits model 44 and linear subcircuits model 46. At a 
fairly basic level, nonlinear subcircuit elements in the netlist 40 are 
primarily transistors, while the linear subcircuit elements are the wires, 
or conductors, connecting the transistors. Traditionally, nonlinear 
elements have been of primary concern, but with submicron designs, linear 
subcircuit elements are becoming significantly more important. For designs 
implemented in a 0.35 micron process technology, it is estimated that over 
50% of the delay in a circuit can be attributed to linear subcircuit 
elements. 
The linear subcircuits model 46 is reduced by model reduction block 48 into 
a reduced order macromodel 50. The model reduction block 48 comprises a 
multipoint matrix Pade approximation as described below. The reduced order 
macromodel 50, combined with the nonlinear subcircuits model 44, can be 
used in a circuit simulator 52 and timing verifier 54. 
FIG. 2 is a flow diagram illustrating a model reduction method implemented 
in model reduction block 48 (FIG. 1). The Block Lanczos model reduction 
method of model reduction block 48 is illustrated in four basic steps. At 
step 60, starting block vectors are generated. Then, at step 62, new 
Lanczos block vectors are generated from the starting block vectors. At 
step 64, scaling/normalization of the new Lanczos block vectors is 
accomplished. At step 66, breakdowns are detected in the new block Lanczos 
vectors, and if necessary, the breakdowns are treated. 
FIG. 3 is a flow diagram illustrating the model reduction method of FIG. 2 
in more detail. The method is for generating a multipoint Pade 
approximation of a linear circuit. The linear circuit is an interconnect 
between at least two circuit elements or circuit blocks of an electronic 
circuit. The linear circuit may also be an analog portion of the 
electronic circuit. In FIG. 3, step 60 is illustrated as steps 68, 70, 72, 
74, and 76. At step 68, state equations of the linear circuits to be 
analyzed are generated. At step 70, expansion frequencies and number of 
moments per frequency are provided. At step 72, the first expansion 
frequency of one or more expansion frequencies are provided. At step 74, a 
set of starting block Lanczos vectors are generated using a first 
expansion frequency of the one or more expansion frequencies and the state 
equations provided at step 68. At step 76, the starting block Lanczos 
vectors are orthogonalized. Note that in the illustrated embodiment, the 
sets of block Lanczos vectors consist of pairs of block Lanczos vectors. 
Step 62 of FIG. 2 is illustrated as steps 80 and 82 in FIG. 3. At step 80, 
new block Lanczos vectors are generated from the previous block Lanczos 
vectors. Then, at step 82, the new block Lanczos vectors are 
orthogonalized with respect to the previous block Lanczos vectors. 
At step 64, scaling and normalizing of the new block Lanczos vectors is 
accomplished to produce a new set of scaled and normalized block Lanczos 
vectors. At step 66, breakdowns are detected in the new set of scaled and 
normalized block Lanczos vectors, and the detected breakdowns are treated. 
At decision step 84, it is determined if all moments of the first expansion 
frequency have been used. If all of the moments have not been used, the NO 
path is taken to step 62, and a new sets of block Lanczos vectors is 
generated from the previous new block Lanczos vectors. If all of the 
moments have been used, then the YES path is taken to decision step 86 and 
it is determined if all of the expansion frequencies of the one or more 
expansion frequencies have been used. At decision step 86, if all of the 
expansion frequencies of the one or more expansion frequencies have not 
been used, then the NO path is taken to step 88 where the next expansion 
frequency is retrieved. At step 90, new starting block Lanczos vectors are 
generated and the flow continues at step 62. However, if at decision step 
86, all of the expansion frequencies have been used, the flow is complete, 
and provides a reduced order model of the linear components of an 
electronic circuit. The accuracy of the model can be determined by 
comparing state equations generated from the reduced order model to the 
state equations of the circuit that were generated at step 68 of FIG. 3. 
FIG. 4 is a flow diagram illustrating the scaling/normalization method of 
step 64 of FIG. 3. At step 92, a set of orthogonal factorizations 
corresponding to the set of new block Lanczos vectors are generated from 
the new block Lanczos vectors. At step 94, a singular value decomposition 
of the set of new block Lanczos vectors is generated. The singular value 
decomposition is used to detect breakdowns. At step 96, the set of new 
block Lanczos vectors are scaled and normalized using the generated set of 
orthogonal factorizations and the singular value decomposition. After step 
96, the flow continues at step 66 of FIG. 3. 
FIG. 5 is a flow diagram further illustrating the breakdown treatment 
illustrated in at step 66 of FIG. 3. At decision step 100, it is 
determined if a breakdown has occurred by checking whether the new set of 
scaled and normalized block Lanczos vectors has a singular matrix product. 
If yes, then the YES path is taken to decision step 102. If no, the NO 
path is taken and the flow continues to decision step 84 of FIG. 3. At 
decision step 102, it is determined if the breakdown is simple. That is, a 
breakdown is simple when the block Lanczos vector being considered is rank 
deficient. The breakdown is serious when the block Lanczos vector being 
considered is not rank deficient. If the breakdown is simple, the YES path 
is taken to step 104, and a first new set of random block Lanczos vectors 
are generated to become a new set of starting block Lanczos vectors. If it 
is determined that the breakdown is not simple, the NO path is taken to 
step 108 and the new set of scaled and normalized block Lanczos vectors 
are patched with a second new set of random block Lanczos vectors to form 
a new set of starting block Lanczos vectors. At step 106, the new set of 
starting block Lanczos vectors are orthogonalized with respect to all 
previously generated sets of block Lanczos vectors, and the flow is 
continued at step 100. 
The basic steps of the Rational Block Lanczos algorithm are described 
below. Consider the general multiple input and output system: 
EQU Fx=Ax+Bu y=Cx (1) 
where x is the state vector of size n, and u and y are the input and output 
vectors of size p..F and A are n.times.n square matrices. B and C.sup.T 
are matrices of size n.times.p. The matrix transfer function of the system 
in equation (1) can be written as: 
EQU H(s)=C(sF-A).sup.-1 B=-C I-.sigma.(A-.sigma..sub.i F).sup.-1 F!.sup.-1 
(A-.sigma..sub.i F).sup.-1 B (2) 
where .sigma.,=s+s.sub.i, with s.sub.i being the expansion frequency. The 
I.sup.th moment of the transfer function can be defined as: 
EQU M.sub.il =C(A-.sigma..sub.i F).sup.-1 F!.sup.1 (A-.sigma..sub.i F).sup.- 
B(3) 
In order to simplify the discussion of the basic algorithm, the same number 
of moments is assumed at each expansion frequency. Let .tau. be the total 
number of expansion frequencies, .eta. be the number of moments at each 
frequency, and .upsilon. be the total number of frequencies at all 
frequency. Then .upsilon.=.tau..eta.. Also, the frequency index is denoted 
by 1.ltoreq.i.ltoreq..tau.; the moment index at each frequency is denoted 
by 1.ltoreq.j.ltoreq..eta.; and the global moment index is denoted by k. 
The basic steps of the Rational Block Lanczos algorithm follow: 
##EQU1## 
In the above algorithm, step 3(b) generates the new Lanczos vector. Step 
3(c) performs the back-orthogonalization with respect to previous Lanczos 
vectors. Step 3(d) performs scaling to ensure that P.sub.k+1.sup.T 
Q.sub.k+1 =I. The singular value decomposition is also used to detect 
breakdowns. Note that the basic algorithm described above assumes no 
breakdowns. The actual implementation has adopted the strategy for 
breakdown treatment described in the prior art. The algorithm will produce 
the following reduced systems in the right Krylov subspace, K.sub.R 
={Q.sub.1,Q.sub.2 . . . ,Q.sub.v }, as 
EQU F.sub.R X.sub.R =A.sub.R X.sub.R 30 B.sub.R u y=C.sub.R X.sub.R(4) 
where F.sub.R =H.sub.vv,A.sub.R =L.sub.vv +.sigma..sub.1 H.sub.vv,B.sub.R 
=P.sub.v.sup.T (A-.sigma..sub.1 F).sup.-1 B and C.sub.R =CQ.sub.V 
L.sub.vv. H.sub.vv, and L.sub.vv contain the coefficients for 
back-orthogonalization and normalization. Similarly, the reduced system in 
the left Krylov subspace, K.sub.L ={P.sub.1,P.sub.2, . . . ,P.sub.V } can 
be written as: 
EQU F.sub.L X.sub.L =A.sub.L X.sub.L +B.sub.L U Y=C.sub.L X.sub.L(5) 
where F.sub.L =G.sub.vv.sup.T, A.sub.L =K.sub.vv.sup.T +.sigma..sub.1 
G.sub.vv, B.sub.L =K.sub.vv.sup.T P.sub.V.sup.T (A-.sigma..sub.1 F).sup.-1 
B, and C.sub.L =CQ.sub.V. Again, G.sub.vv, and K.sub.vv contain the 
coefficients for back-orthogonalization and normalization. The moments of 
these reduced systems are the same, and thus only one system needs to be 
considered. 
FIG. 6 is a block diagram showing a general purpose computer 20. The 
general purpose computer 20 has a computer processor 22, and memory 24, 
connected by a bus 26. Memory 24 includes relatively high speed machine 
readable media such as DRAM (dynamic random access memory), SRAM (static 
random access memory), ROM (read only memory), EEPROM (electrically 
erasable programmable read only memory), flash EEPROM, and bubble memory. 
Also connected to the bus are secondary storage 30, external storage 32, 
output devices such as a monitor 34, input devices such as a keyboard 
(with mouse) 36, and printers 38. Secondary storage 30 includes machine 
readable media such as hard disk drives, magnetic drum, and bubble memory. 
External storage 32 includes machine :readable media such as floppy disks, 
removable hard drives, magnetic tape, CD-ROM, and even other computers, 
possibly connected via a communications line. The distinction drawn here 
between secondary storage 30 and external storage 32 is primarily for 
convenience in describing the invention. As such, it should be appreciated 
that there is substantial functional overlap between these elements. 
Executable versions of computer software 33, such as model reduction 
software 48 can be read from the external storage 32 and loaded for 
execution directly into the memory 24, or stored on the secondary storage 
30 prior to loading into memory 24 for execution. 
As can be seen, the described method generates rational block Lanczos 
vectors for model reduction of linear electronic circuitry. The method 
includes an adaptive scheme for breakdown treatment that addresses two 
problems of the single Pade approximation: poor approximation of the 
transfer function in the frequency domain far away from the expansion 
point and the instability of the reduced model when the original system is 
stable. Also, the described method alleviates the breakdown problems due 
to smaller Krylov subspace corresponding to each frequency point. The cost 
of full backward orthogonalization with respect to all previous Lanczos 
vectors is offset by more accurate and smaller order approximations. 
While the invention has been described in the context of a preferred 
embodiment, it will be apparent to those skilled in the art that the 
present invention may be modified in numerous ways and may assume many 
embodiments other than that specifically set out and described above. 
Accordingly, it is intended by the appended claims to cover all 
modifications of the invention which fall within the true spirit and scope 
of the invention.