Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1999-12-15
2002-04-16
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C703S014000
Reexamination Certificate
active
06374390
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to improving the performance of matrix evaluations. The invention is also related to an improvement in performance in evaluating sparse matrices having at least one model containing information for at least one node in the matrix being evaluated. The invention is still further related to an improvement in the performance of matrix evaluations where the sparse matrix represents Kirchoff's voltage and current laws for an electronic circuit being evaluated, and where the models represent specific structures and contain at least one conductance contribution value of an electronic circuit component of the electronic circuit.
2. Discussion of the Background
The use of matrix based solvers (matrix solutions) to simulate transient behavior of electronic circuits dates back to 1975, and is in wide use in the electronic design community. Nagel, L.,
SPICE
2
: A Computer Program to Simulate Semiconductor Circuits
, ERL Memo UCB/ERL M75/520, University of California, Berkeley, May 1975, hereinafter,
SPICE
; see also Cohen, E.,
Program Reference for SPICE
2, ERL, University of California, Berkeley, June 1976, hereinafter
Cohen
, and Quarles, T., Analysis of Performance and Convergence Issues for Circuit Simulation, EECS, University of California, Berkeley, April 1989, hereinafter,
Quarles
. This method of solution relies on the fact that differential circuit equations that describe transient behavior of circuits can be written as conductance coefficients (G) into a matrix, and the matrix can be solved to obtain new voltage values at each node of the circuit.
The use of matrix solutions has relied on a number of techniques to improve solution performance. Starting with
SPICE
, sparse matrix techniques have been utilized to reduce the amount of memory required to store the entire matrix. While sparse matrix systems reduce the amount of memory needed, they require a trade-off in performance due to the fact that the location of an individual matrix entry must be stored and because the matrix solution cannot be calculated through simple matrix index mathematics as in non-sparse systems.
FIG. 1A
is a circuit diagram of a two resistor circuit (R
1
and R
2
) having three circuit nodes (N
1
, N
2
, and N
3
).
FIG. 1B
is a matrix representing conductance values (G) of the two resistor circuit. The matrix element labeled G
1
+G
2
represents the circuit equation coefficients for the node N
2
between the resistors.
In a single processor computer, matrix evaluation cycles proceed according to the flow diagram in FIG.
2
. For each time point in the simulation, all of the device models are evaluated and the result is added to the matrix entry in a serial fashion. At Step
20
, a model is evaluated. Such model can be, for example, a model representing resistor R
1
in FIG.
1
A. The model evaluation determines the conductance values (G) of the circuit element, resistor R
1
. At Step
22
, the matrix is loaded with the conductance values determined in the model evaluation Step
20
. In this example, the conductance values of the circuit element resistor R, is collectively referred to as a matrix stamp R, is inserted into the matrix (see Matrix stamp of R
1
, FIG.
1
B). Steps
20
and
22
are repeated for each model to be evaluated.
At Step
24
, the matrix is solved to determine voltage values at each node of the circuit. At Step
26
, a convergence test is utilized to determine whether or not the circuit has reached a steady state solution. An example convergence test compares values at a vector of new nodal voltages (X
i
) to values from a last convergent time point (X
i−1
), and is defined as:
X
i
−X
i−1
≦Abstol+Reltol * Max (
X
i
, X
i−1
),
where Astol and Reltol are user defined convergence control variables of the simulator (having default values of 1e−6 and 1e−3 respectively), and the function Max ( ) returns the largest of two values.
If the convergence test does not reach steady state, the entire process is repeated for another simulated time point. In the above process, because the model evaluation can occupy as much as 50 percent of the processor's time, this leads to extremely long runs in large circuit simulation can be experienced.
The conventional implementation of matrix solvers has relied on device model structures similar to Resistor Model Structure
30
shown in FIG.
3
. Resistor Model Structure
30
stores identifying information
32
, including an instance and model identifier, and the conductance value G
36
, as evaluated during model evaluation (Step
20
in
FIG. 2
, for example). In addition, Resistor Model Structure
30
stores the memory locations of the matrix entries (Pointers
38
, for example). This mechanism requires that after each device model is evaluated, the new values of G (
36
, for example) must be ‘stamped’ into the matrix during the matrix load phase.
In a multiple processor system, each evaluation of a device model can be handed to a separate processor. As shown in
FIG. 4
, model evaluations
40
a
,
40
b
, and
40
c
are processed in parallel. While this can lead to some improvement in simulation time, the overall performance of the system will not be improved dramatically due to the nature of shared memory systems. Shared memory is utilized because some circuit equations cause overlapping entries at matrix positions where two or more circuit elements meet to form a circuit node, therefore the effect of adding additional processors is reduced because of a time consuming, serial process of matrix load (Step
42
).
If each device model is evaluated by a separate processor, then the simulation can enter a situation known as a blocking memory write in which two (or more) processors attempt to write to the same memory location. This can be seen by referring to the matrix entry labeled G
1
+G
2
in FIG.
1
B and corresponding to node N
2
in
FIG. 1A
, which shows that the value of this element has conductance contributions G
1
and G
2
from resistors R
1
and R
2
, respectively.
Some mechanism must be provided to prevent two processors from writing to a given memory location simultaneously. A blocking memory write prevents simultaneous writes by locking a memory location (matrix entry), reading it's value, adding the evaluation of the other models (conductances) that contribute to this nodal voltage, and then unlocking the memory location. However, blocking memory writes are expensive due to the fact that all other processes that are contributing to the value at the memory location being written are blocked until the lock/unlock cycle completes. Furthermore, in order to avoid an enormous number of memory location lock operations and associated bookkeeping and memory consumption involved in managing those locks, multi-processing systems have historically locked and unlocked the entire matrix before and after each stamping step.
Bischoff and Greenburg's original method Bischoff, G., and Greenburg, S.,
Cayenne—A Parallel Implementation of the Circuit Simulator SPICE
, Digital Equipment Corporation, Hudson Mass., CH2353-1/86/0000/0182 © 1986 IEEE, hereinafter
Bischoff and Greenburg
, overcomes this blocking problem by changing the matrix entry from a single scalar value to a sum value and a vector of individual conductances. As shown in
FIG. 5
, each matrix position (
50
, for example) includes a vector
52
where each vector entry (G
2
, for example) is a collection point for a single model evaluation. Thus, if two device models are connected to a circuit node, that node is represented in the matrix as a matrix position having three values, two of which provide locations for non-blocking writes by separate model evaluation processes (vector
52
), and one of which is a sum value
54
.
The effect of
Bischoff and Greenburg's
method on the matrix evaluation loop is shown in FIG.
6
. Model evaluations
40
a
,
40
b
, and
40
c
are performed as before, however, matrix loads shown as matrix load
Liebmann S. Peter
Quarles Thomas L.
Spruiell Leslie D.
Antrim Design Systems, Inc.
Fliesler Dubb Meyer & Lovejoy LLP
Garbowski Leigh Marie
Smith Matthew
LandOfFree
Method and apparatus for improvement of sparse matrix... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for improvement of sparse matrix..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for improvement of sparse matrix... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2854927