From: aburto@marlin.NOSC.MIL (Alfred A. Aburto)
Newsgroups: comp.benchmarks
Subject: nsieve.c results
Date: 14 Apr 92 00:11:55 GMT
Article-I.D.: marlin.2011
Distribution: comp.benchmarks
Organization: Naval Ocean Systems Center, San Diego

-------

I have another program called nsieve.c which I tinker with now and then.
It is the sieve program for finding prime numbers. It allocates memory
for increasingly larger memory ('array') sizes and logs the run times. 
It also gives the MIPS rating for the program (not a 'typical' MIPS rating 
based upon some instruction mix, but just the expected MIPS rating for the 
instructions the program is expected to execute, so compilers and compiler
options used can make a difference in the results). The 'linear time' is 
just the first result (run time for the 8191 array size) scaled up 
according to the other array sizes divided by 8191.  
Some results follow:

(1) SPARCserver 490, cc -O4 -DUNIX nsieve.c

   Sieve of Eratosthenes (Scaled to 10 Iterations)
   Version 1.2, 03 April 1992

   Array Size   Number   Last Prime    Linear     RunTime    MIPS
    (Bytes)   of Primes               Time(sec)    (Sec)
       8191       1899        16381      0.065      0.065    25.5
      10000       2261        19997      0.079      0.080    25.5
      20000       4202        39989      0.159      0.162    25.4
      40000       7836        79999      0.317      0.333    25.0
      80000      14683       160001      0.635      0.662    25.5
     160000      27607       319993      1.269      1.686    20.2
     320000      52073       639997      2.539      4.942    13.9
     640000      98609      1279997      5.078     11.156    12.5
    1280000     187133      2559989     10.156     23.700    11.9
    2560000     356243      5119997     20.312     49.137    11.5

   Relative to 10 Iterations and the 8191 Array Size:
   Average RunTime =    0.100 (sec)
   High  MIPS      =     25.5
   Low   MIPS      =     11.5


(2) SPARCstation 2, cc -O4 -DUNIX nsieve.c

   Sieve of Eratosthenes (Scaled to 10 Iterations)
   Version 1.2, 03 April 1992

   Array Size   Number   Last Prime    Linear     RunTime    MIPS
    (Bytes)   of Primes               Time(sec)    (Sec)
       8191       1899        16381      0.072      0.072    23.2
      10000       2261        19997      0.087      0.088    23.1
      20000       4202        39989      0.175      0.180    22.9
      40000       7836        79999      0.350      0.367    22.7
      80000      14683       160001      0.699      0.796    21.2
     160000      27607       319993      1.398      1.748    19.5
     320000      52073       639997      2.797      3.547    19.4
     640000      98609      1279997      5.593      7.181    19.4
    1280000     187133      2559989     11.186     14.538    19.3
    2560000     356243      5119997     22.372     29.462    19.2

   Relative to 10 Iterations and the 8191 Array Size:
   Average RunTime =    0.083 (sec)
   High  MIPS      =     23.2
   Low   MIPS      =     19.2


(3) Amiga 2000, 68030/33.3 MHz, ICache ON, DCache OFF, Aztec C 5.0a

   Sieve of Eratosthenes (Scaled to 10 Iterations)

   Array Size   Number   Last Prime    Linear     RunTime    MIPS
    (Bytes)   of Primes               Time(sec)    (Sec)
       8191       1899        16381      0.214      0.214     7.4
      10000       2261        19997      0.261      0.263     7.4
      20000       4202        39989      0.522      0.532     7.4
      40000       7836        79999      1.045      1.075     7.5
      80000      14683       160001      2.089      2.180     7.5
     160000      27607       319993      4.179      4.429     7.4
     320000      52073       639997      8.358      8.867     7.5
     640000      98609      1279997     16.715     17.949     7.5
    1280000     187133      2559989     33.430     36.406     7.5


   Could Not Allocate Memory for Array Size: 2560000

   Relative to 10 Iterations and the 8191 Array Size:
   Average RunTime =    0.223 (sec)
   High  MIPS      =      7.5
   Low   MIPS      =      7.4


(4) Amiga 2000, 68030/33.3 MHz, ICache OFF, DCache OFF, Aztec C 5.0a

   Sieve of Eratosthenes (Scaled to 10 Iterations)

   Array Size   Number   Last Prime    Linear     RunTime    MIPS
    (Bytes)   of Primes               Time(sec)    (Sec)
       8191       1899        16381      0.396      0.396     4.0
      10000       2261        19997      0.483      0.485     4.0
      20000       4202        39989      0.966      0.984     4.0
      40000       7836        79999      1.931      1.997     4.0
      80000      14683       160001      3.863      4.036     4.0
     160000      27607       319993      7.726      8.608     3.8
     320000      52073       639997     15.451     17.432     3.8
     640000      98609      1279997     30.903     35.195     3.8
    1280000     187133      2559989     61.806     71.211     3.8


   Could Not Allocate Memory for Array Size: 2560000

   Relative to 10 Iterations and the 8191 Array Size:
   Average RunTime =    0.423 (sec)
   High  MIPS      =      4.0
   Low   MIPS      =      3.8


I'm not sure of the 'physics' of what is really going on here with
these different results, but I think the following is correct. If the
system cache is working effectively (or if there is no cache) then the
run times will be linear with increasing array size and the MIPS rating
will stay relatively constant with increasing array size. However if the
cache is working poorly then there will be a drop off in performance as
the array size increases. The drop off can be somewhat small (as with
the SPARCstation 2) or rather large (SPARCserver 490) or almost none 
(68030 caches ON or OFF).

Al Aburto
aburto@marlin.nosc.mil

-------