Method for determining the steady state behavior of a circuit using an iterative technique

• US 6,636,839 B1
• Filed: 09/05/2000
• Issued: 10/21/2003
• Est. Priority Date: 04/30/1996
• Status: Expired due to Term

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Kundert, Kenneth S., Telichevesky, Ricardo, White, Jacob K.
• Primary Examiner(s): Siek, Vuthe
• Assistant Examiner(s): LIN, SUN J
• Application Number:
  US09/654,685
• Time in Patent Office: 1,141 Days
• Field of Search: 716/1-14, 703/1-14
• US Class Current: 706/1
• CPC Class Codes: G06F 30/367 Design verification, e.g. using simulation, simulation program with integrated circuit emphasis [SPICE], direct methods or relaxation methods

Abstract

An efficient method for determining the periodic steady state response of a circuit driven by a periodic signal, the method including the steps of 1) using a shooting method to form a non-linear system of equations for initial conditions of the circuit that directly result in the periodic steady state response; 2) solving the non-linear system via a Newton iterative method, where each iteration of the Newton method involves solution of a respective linear system of equations; and 3) for each iteration of the Newton method, solving the respective linear system of equations associated with the iteration of the Newton method via an iterative technique. The iterative technique may be a matrix-implicit application of a Krylov subspace technique, resulting in a computational cost that grows approximately in a linear fashion with the number of nodes in the circuit.

Claims

1. In a circuit simulation tool, a method for determining a periodic steady state output response of a circuit driven by a periodic input signal, the periodic steady state output response covering a plurality of timepoints that span a period of the periodic input signal, the plurality of timepoints including a last timepoint, the method comprising:

using a finite-difference method to form a non-linear system of equations for the periodic steady state output response of the circuit;

solving the non-linear system of equations via a Newton iterative method to produce the periodic steady state output response of the circuit, each iteration of the Newton method associated with a respective linear system of equations;

for each iteration of the Newton method, using a matrix-implicit iterative technique to solve for nodal voltages of the circuit at a particular one of the timepoints, the nodal voltages satisfying the respective linear system of equations associated with the iteration of the Newton method, wherein use of the matrix-implicit iterative technique avoids computation of a matrix to produce a solution of the respective linear system of equations; and

providing the periodic steady state output response to the circuit simulation tool.

2. The method of claim 1, wherein the particular timepoint is the last timepoint.

3. The method of claim 1, wherein the matrix-implicit technique is a Krylov-subspace technique.

4. The method of claim 3, wherein the matrix-implicit technique uses a generalized minimal residual (GMRES) algorithm.

5. The method of claim 3, wherein the matrix-implicit technique uses a generalized conjugated residual (GCR) algorithm.

6. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method of simulating a circuit, the method comprising:

generating a plurality of search direction vectors in accordance with a Krylov-subspace technique, the plurality of search direction vectors being generated using a recurrence relation; and

processing the plurality of search direction vectors iteratively in accordance with the Krylov-subspace technique to produce a solution vector satisfying a system of linear equations.

7. The method of claim 6, wherein the recurrence relation is derived from the initial conditions of a non-linear equation.

8. The method of claim 7, further comprising iteratively solving the system of linear equations to produce a solution to the non-linear equation, the non-linear equation corresponding to a periodic steady state solution for the node voltages of a circuit.

9. The method of claim 6, wherein the system of linear equations corresponds to a backward-Euler discretization of a linearized system of differential equations that represents the behavior of a circuit, and wherein the solution vector corresponds to an approximation of the effect on an output vector in response to a perturbation of an input vector to the circuit.

10. The method of claim 9, further comprising storing the plurality of search direction vectors during a first execution of the Krylov-subspace technique corresponding to the analysis of a first frequency, and reusing the plurality of search direction vectors during a second execution of the Krylov-subspace technique corresponding to the analysis of a second frequency.

11. The method of claim 6, wherein the system of linear equations corresponds to a non-linear system of difference equations, the non-linear system of difference equations being derived from a backward-euler discretization of a system of N differential equations that represents the behavior of a circuit.

12. The method of claim 6, wherein the system of linear equations corresponds to a quasi-periodic mixed frequency-time non-linear system matrix of sampled values.