mark@mips.COM (Mark G. Johnson) (08/29/88)
Summary: An unusual and perhaps surprising result was found, running
SPICE on a parameterized MOS circiut. The measured runtimes
show an asymptotic complexity (in the sense of "big-O" asymptotes)
of n ^ 1.35 where n is the number of MOSFETs.
What may appear unusual is that the super-linear term is
dominated by the linear term for n < 43,000 transistors. {This
is an extrapolation; the experimental data only extends to
n=1000 transistors}
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
This note contains a small amount of data and a little algebra; it's
intented to stir up some reflection and discussion about a
commonly-accepted belief in lsi-cad:
"SPICE runtimes explode as circuit size increases."
Of course, this teeny piece of the picture may not be representative of
all possible circuit simulations; i.e. the generic disclaimer "your
mileage may vary" applies, since your vehicle may be used in quite
different circumstances.
DESCRIPTION OF EXPERIMENT
A spice-input-deck generator program was constructed. It creates
input decks consisting of n transistors where n is an input parameter.
The generated circuits are parallel (not series) topologies, thus forcing
every circuit node to change at the same time. The number of transient
timesteps simulated was constant, independent of n. Transistor sizes
were randomized (slightly) to create different waveshapes throughout
the circuit. The following relationship holds for n >= 5
# of nodes in the circuit == (3/5) * (# of MOSFETs)
Simulations were run with Berkeley SPICE 2G.6 on a VAX 11-780.
DATA
Runtimes are tabulated below. A nonlinear-least-squares optimization
program was employed, and the data were found to be a good fit to the
equation
*********************************************************************
* RUNTIME(sec) ~=~ (1.545) + (5.518 * n) + (0.130 * (n ^ 1.3514)) *
*********************************************************************
where n is the number of MOSFETs. The predicted runtimes from this
equation are also tabulated, along with the %error in the prediction.
Errors in the predictions are rather small, especially for the largest
circuit sizes. Note that the curve fitter was given 14 datapoints to
fit the four coefficients in the equation.
# of measured predicted runtime error in
MOSFETS runtime (sec) from equation (sec) prediction
--------------------------------------------------------------------------
2 12.77 12.91 1.10 %
5 31.55 30.28 -4.03 %
10 59.16 59.65 0.83 %
20 115.51 119.37 3.34 %
25 152.02 149.58 -1.61 %
50 287.70 303.18 5.38 %
75 472.55 459.91 -2.67 %
100 635.65 619.01 -2.62 %
150 955.86 942.82 -1.36 %
200 1307.4 1272.7 -2.65 %
300 1910.5 1946.7 1.89 %
450 2929.2 2985.9 1.94 %
725 4932.2 4956.9 0.50 %
1000 7063.6 6994.1 -0.98 %
-----------------------------------------------------------------------
DISCUSSION
At least for the class of circuits studied and in the range (2 < n < 1000),
the equation seems to fit the data pretty well:
RUNTIME(sec) = (1.545) /* constant term */
+ (5.518 * n) /* linear term */
+ (0.130 * (n ^ 1.3514)) /* super-linear term */
As n approaches infinity, the runtime is O(n ^ 1.3514). However let's
calculate the n where the superlinear term dominates the linear term:
0.130 * (n ^ 1.3514) >= 5.518 * n
(n ^ 1.3514) >= 42.446 * n ..... moved 0.130 to rhs
(n ^ 0.3514) >= 42.446 ..... divided by n
0.3514 * log(n) >= log(42.446) ..... took logarithm
n >= 42897.5
So for circuits where n < 42800 transistors, the superlinear "runtime
explosion" is not expected; runtime will be dominated by the simple
linear term (5.518 * n). Of course, this is based on a curve fit
from data where n <= 1000, so it's an an extrapolation and should be
viewed with some skepticism.
However, in this specific circuit domain, for these specific runtime
data (which cover the folklore region "only run SPICE with n < 250
transistors"), a superlinear explosion was not observed.
Naturally, other experiments with other assumptions (bipolar circuits?
AC analysis instead of transient analysis? serial topologies?) can
yield different results.
--
-- Mark Johnson
MIPS Computer Systems, 930 E. Arques, Sunnyvale, CA 94086
...!decwrl!mips!mark (408) 991-0208kim@wayne.UUCP (Kim Helliwell) (08/30/88)
In article <2913@obiwan.mips.COM>, mark@mips.COM (Mark G. Johnson) writes: > > Summary: An unusual and perhaps surprising result was found, running > SPICE on a parameterized MOS circiut. The measured runtimes > show an asymptotic complexity (in the sense of "big-O" asymptotes) > of n ^ 1.35 where n is the number of MOSFETs. > What may appear unusual is that the super-linear term is > dominated by the linear term for n < 43,000 transistors. {This > is an extrapolation; the experimental data only extends to > n=1000 transistors} Followed by some data and a derivation of a fitted curve. He seemed surprised by this behavior, but it matches very well what I know about SPICE, and what Berkeley people (e.g. Prof Newton) say about it. Basically, the linear term comes from the equation formulation--the model calculation and matrix loading. It should seem intuitive that this part of things is linear in the number of transistors. The superlinear term comes from the matrix solution. I agree that it may not be intuitive that this term is dominated by the linear term, but Newton and many others have known that for years. Normally, you expect that matrix solution would be O(n^3), so why is that not the case here? Simply because of the efficiencies introduced by maintaining a sparse matrix--because so many of the elements are identically zero, many of the steps of doing the matrix solution can be skipped entirely. This results in asymptotic behavior that goes like O(n^1.1-1.4), according to Newton. In fact, in the limiting case of NO off-diagonal elements in the matrix, it would be O(n)! By the way, this is why so much emphasis is put on maintaining sparsity throughout the solution process, and why pivots are chosen more based on preserving sparsity than on preserving accuracy. (If you don't know what that means, you can either ignore it or read Nagel's thesis--the chapter where he talks about matrix solution techniques.) -- "Never let work interfere with your reasons for working." Kim Helliwell