The trend in integrated circuit (IC) design has been to make circuits of unprecedented (high) density of elements and level of complexity, and which operate at very high frequencies. Typical IC's have around 1 million elements, linear and nonlinear. The behavior of the circuit is governed by ordinary differential equations. ODE solvers used for circuit simulation must be accurate. Of particular interest to the circuit designer is the output of the circuit to some inputs. Normally, the number of inputs and the number of outputs are much smaller than the number of elements in the circuits.
In computer aided design (CAD) of IC, the designer adjusts parameters and circuit design until the desired behavior is produced. Even though the number of parameters to adjust may be small, the large number of elements in the IC controls the computational costs of evaluating each design. For design purposes, it is important that simulations can be done rapidly (i.e., in order of seconds, rather than hours, per simulation).
Many IC's have groups of components that can be isolated into subcircuits, each with only a few inputs and outputs. Often, these groups are made up of a large number of linear elements. The present research activities in circuit reduction is focused on reducing the complexity posed by these sets of large number of linear elements. The idea is to find an equivalent circuit (which are often a mathematical representation of a circuit) whose output response to a given set of inputs is nearly identical to that of the original complex circuit.
The linear subcircuits in question can consist of a large number of RLC elements. In cases where a long wire is present, even at the speed of light, we need to consider finite travel time. Here, one needs to consider transmission line models. In some designs, it may be necessary to consider the full electromagnetic effects because of the proximity of a wire to other lines. A schematic diagram of the goal of circuit reduction is given in Figure 1.
Consider a circuit consisting of resistors, capacitors and inductors, which is described mathematically by a system of first order equation. Let x(t) be the state vector describing the states at each node or the circuit; the states could represent the voltage potential at the node of the amount of current leaving a node. The input to the circuit is represented by vector u(t). Then the state of the system is governed by
plus some initial conditions on x, which can be assumed to be null.
For the example in the Figure 2,
We have considered the currents flowing through nodes 1 and 5 as output.
To represent the output from the circuit, we use the vector y(t), where . Typical in these problems is that the dimension of x is much greater than those of y and u.
The circuit behavior (ie blackbox in Figure 1) is captured in the impulse response or transfer function h(t) which maps the inputs u to the outputs y via convolution. A formal representation of the impulse response if its Laplace transform, often refered to as the transfer function
Suppose the circuit has n elements, then H(s) must be of the form
We can think of model reduction as a process of approximating H(s).
In order to be useful, a model reduction method must be
The most basic method for model reduction is called the single frequency expansion (refered to as AWE for Asymptotic Waveform Evaluation). To illustrate this method, suppose H(s) is a scalar function. Next, we perform the Taylor's series expansion of H(s) about s=0. The expansion is matched with a Padé approximation, with the numerator of degree L and denominator of degree M. Thus,
where and are polynomials of degrees L and M. The approximate poles and approximate residues are found from the Padé approximation. Thus we have reduced a system with n elements with one that has only M elements.
The problem with this approach is accuracy. Poles that are far from the point of expansion are poorly estimated. We can move the expansion point, but if a range of frequency response is needed, we would lose out because no matter where we expand, some poles will be poorly approximated, or worse still, altogether missed.
To overcome this obstacle, one can go one of two ways: (1) increase the accuracy of a single point expansion, or (2) use multiple points in making the expansion.
Approaches based on (1) are often refered to as implicit moment matching. Current research activities in this area centers around the Krylov subspace methods and their variants. Simply described, the methods extract the relavant transient modes by examining the eigenvalues and eigenvectors of a matrix associated with the circuit. A Krylov based method, namely the Lanzcos algorithm, is a procedure by which the largest and smallest eigenvalues of a matrix are estimated in an iterative and economical process. We can think of the method as a way of ``weeding out'' unimportant components of the solution to the linear ordinary differential equations describing the IC. Key references in this area of active research include Feldman and Freund (1994), Gallivan et al (1994), and Nguyen et al (1997). While a lot of research effort has been put in this direction, for example, in making the computation more efficient and accurate, there are problems in which this approach has not succeeded in solving. For instance, model reduction for the circuits with frequency dependent transmission lines is a problem where complex frequency hopping has been successfully applied, but still awaits feasible approaches that are based on Krylov subspaces.
In the next section, we will give a brief description of an approach based on (2). The method goes by the name of Complex Frequency Hopping and was introduced by Chiprout and Nakhla. The method is quite powerful and has a wide range of applicability.