Subject: Schneider's Benchmark example

From: [email-masked]
Date: Fri, 25 Jun 93 21:08:51 GMT

COMMENTS ON DAVE SCNEIDER'S BENCHMARK EXAMPLE
                       from Roger Hockney
                   --------------------------

Help, you have changed the notation on us! I am going to express your
example in the previously used notation:
         Computer A or B, Code X or Y, size N or M, procs p or q
Then your example is
            COMPUTER A                        COMPUTER B 
CODE X    T(A,X:N;p) = 1  s                T(B,X:N;p) = 2 s
CODE Y    T(A,Y:N;p) = 10 s                T(B,Y:N;p) = 2 s
Then the Temporal Performances are:
CODE X    R_T(A,X:N;p) = 1   soln/s        R_T(B,X:N;p) = 0.5 soln/s
CODE Y    R_T(A,Y:N;p) = 0.1 soln/s        R_T(B,Y:N;p) = 0.5 soln/s
and we can conclude that:
  "Computer A is better on code X, but Computer B is better on code Y". 
Further, the above is the only conclusion that can validly be drawn from 
this benchmarking data.  To be pedantic, it is also necessary to state that
"better" in benchmarking is shorthand for "shorter wall-clock elapsed time", 
T(A,X:N;p). I trust we have all agreed on that, otherwise we are in deep 
trouble.

If the work in flop-count is defined as in your first case
        F_B(*,X:N;*) = 1 Mflop    and   F_B(*,Y:N;*) = 10 Mflop
Then the Benchmark Performances are:
            COMPUTER A                           COMPUTER B 
CODE X    R_B(A,X:N;p) = 1 Mflop/s          R_B(B,X:N;p) = 0.5 Mflop/s
CODE Y    R_B(A,Y:N;p) = 1 Mflop/s          R_B(B,Y:N;p) = 5.0 Mflop/s
and again we can conclude that:
  "Computer A is better on code X, but Computer B is better on code Y". 
This is still correct, so where is the confusion?

If the work in flop-count is defined as in your second case case
        F_B(*,X:N;*) = 3 Mflop    and   F_B(*,Y:N;*) = 3 Mflop
Then the Benchmark Performances are:
            COMPUTER A                             COMPUTER B 
CODE X    R_B(A,X:N;p) = 3.0 Mflop/s          R_B(B,X:N;p) = 0.67 Mflop/s
CODE Y    R_B(A,Y:N;p) = 0.3 Mflop/s          R_B(B,Y:N;p) = 0.67 Mflop/s
and again we can conclude that:
  "Computer A is better on code X, but Computer B is better on code Y". 
This is still correct, so where is the confusion?

The confusion that you refer to seems to arise when you take an average
(you don't say what kind). But taking averages of benchmark rates is known 
to have little meaning, and quite simply should not be done. If A is better
on one code and B on another, it is not surprising that this result cannot
usefully be averaged. What is the average of "black" and "white", or any two
opposites? So I believe the problem is not with the definition of the
Benchmark performance, but with the taking of a meaningless average. In my
proposals to the methodolgy group, I deliberately did not recommend the
taking of any average. In fact, I recommend the graphical display of all
results. 

SCALING BEHAVIOUR
-----------------
You should mention that the scaling behaviour of a benchmark result depends
just as much, if not more, on the properties of the parallel benchmark code, 
as it does on the properties of the computer. An obvious example is Amdahl
performance saturation which limits the benchmark performance, and depends
on the amount of unparallelised code and the speed of a single processor.
It does not depend at all on the maximum number of processors that can be
assembled (which might be regarded as the scalability of the hardware).
For each benchmark, I would expect to be able to derive a best possible
scaling, from a theoretical timing analysis of the parallelised code, on
the basis that communication rates were infinite and startup times were
zero. This would show Amdahl saturation and be the ideal set of curves
that the real computers with finite rates and overheads would be aiming at.
For some embarrasingly parallel applications these curves (one for each
of a set of problem sizes) would be close to the ideal speedup lines, 
however for other problems various forms of performance saturation would
take place. 

The important thing is to have a realistic timing formula
showing the variation of T(A,X:N;p) with A,X,N and p. This is what we
have tried to do with the Genesis Benchmarks (see Addison et al,
Concurrency P&E, vol 5(1), 1-22). Only when such a formula is given, is
scaling completely understood. Also the effect of increasing problem size 
N with p in different ways can be studied by inserting the different 
variations into the timing formula. In the above reference the processing
node was characterised by 5 hardware parameters (message startup and stream 
rate, scalar arithmetic rate and vector rinf and nhalf), and the code by
the corresponding 5 program parameters (number of messages, total bytes sent, 
number of scalar flop, number of vectorised flop, and average vector length). 
Given such a formula, the best possible scaling can be calculated by setting
the message startup time to zero and the stream rate to infinity. I suggest
that the committee strongly recommend that such a comprehensive timing
formula be produced for each benchmark, by the writer of the benchmark.

                          Roger Hockney

PS Dave, it is enough to send your reply to pbwg-comm, please do not copy it to
rwh@pac becvause I then get it twice.