🚀 go-pugleaf

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-0208