Subject: Reply to Dave Schneider on Metrics

From: [email-masked]
Date: Fri, 11 Jun 93 19:42:31 GMT

Reply to Dave Schneider on F_B and R_B
                --------------------------------------
                         from Roger Hockney

I agree with almost everything you said in your last note, from which I 
conclude:

        (a) There is, as yet, no axiomatic approach that we can use,
            therefore we are left to consider and improve the draft
            metrics that I presented to the last meeting (Chapter 1).

        (b) R_B(N;p) with sensibly defined F_B(N) is probably the least
            biased current metric (at least it is unambiguous and 
            acceptable). I claim below that it is also the most
            convenient and useful.

You rightly point out that R_B is no more than a scaled time measurement.
That is precisely why it is defined in the way that it is, with F_B(N) as
a nominal value (or function) that is the same for all computers and is
unchangeable by fiat. This is the way it has to be if R_B is to have the
properties we require. Thus F_B(N) should be thought of as inscribed in 
stone and handed down by the god of benchmarks. R_B is not intended to
be a measure of the flop-rate of the hardware, for which we have defined
another metric R_H, the hardware performance (incidentally a metric in
which we should not be interested). Rather R_B is an inverse-time measure
scaled for our convenience in a particular way (see below), to be more
useful than the straight inverse-time metric which we call Temporal 
Performance R_T=1/T, but find difficult to use and compare across
benchmarks. 

However, F_B(N) is also intended to approximate to the real hardware 
flop-count, F_H(N) of a good implementation of the one processor sequential 
code, so we expect the benchmark and hardware Mflop/s to be similar for p=1 
               R_B(N;1) \approx  R_H(N;1)=F_H(N)/T(N;1)
For p>1, F_H(N) may be >> F_B(N) because F_H counts redundant operations
which are common in parallel code, whereas F_B correctly does not. 
Redundant operations are any operations that are repeated in each processor
of a parallel implementation. Thus Benchmark and Hardware Mflop/s may 
differ widely in a parallel code. The important point is that we should 
not be interested in R_H, i.e. in generating hardware Mflop/s. The aim of 
the programmer should be to maximise Benchmark Mflop/s, which by its 
careful definition corresponds to minimising elapsed wall-clock execution 
time, T(N;p). To make this distinction clearer the two performance metrics 
have, strictly speaking, different units, and should be written differently:
              Benchmark Performance in units  Mflop/s(benchmark name)
              Hardware  Performance in units  Mflop/s(computer name)  

So that, whereas I agree that R_B is a scaled time measurement, I do not
agree that it is an arbitrary scaling (like SPEC use with the VAX11/780
reference timings). The scaling is closely related to the hardware 
flop-count of sequential code, and therefore a measure, albeit somewhat 
imprecise, of the amount of work required to solve the problem using 
current algorithms. The property that higher R_B means lower execution time, 
does not depend on this relation with the hardware flop-count being close 
(it only depends on F_B(N) being kept the same across all computers), but 
our Mflop/s numbers would begin to look rather silly (arbitrary) if it 
was not fairly close. At some stage I agree that we should adopt a better
measure of work than Mflop, that might come from the research you refer to,
but for this year's report, I can see no alternative to Mflop. Further, we 
are used to the measure, and performance values derived from it: Mflop/s.   

Concerning the ordering:

For a given N, if the R_B(N;p) of code A on computer X is greater than 
the R_B(N;p) of code B on computer Y, then code A runs in less time on X 
than B does on Y. That is the ordering given by time alone is the same as 
that given by R_B. 

Going to a different problem size, N2 say, is rather like going to a 
different benchmark, and it is possible that code B will execute on Y in 
less time than A does on X (i.e. the ordering may change), but this will be 
a real difference in behaviour of the codes which is reflected by R_B(N2;p)
of B on Y becoming greater than R_B(N2;p) of A on X. Such a change of 
ordering in R_B is real and not a matter of definition. Everything is as it 
should be.

I cannot think of an example, where changing the function F_B(N) can
change the ordering of the benchmarked computers. Can you give me an 
example, please. Remember that F_B(N) is the same function for all 
computers, its a property of the problem/benchmark, not the computer.

A misunderstanding may arise however if one compares the R_B(N;p) of one
problem size with the R_B(N2;p) of another problem size. It is not correct
to conclude that the higher R_B means the least execution time because the 
numerators F_B(N) and F_B(N2) are different. Generally speaking the larger
problem will generate more nominal benchmark Mflop/s(benchmark), and also
real hardware Mflop/s, but because it is a bigger problem will take much
longer to run. So higher R_B, in this comparison, may mean longer execution
time, not shorter. But we should not be surprised that a bigger problem
takes longer to run, even if it generates more Mflop/s (real and/or nominal).
To compare execution time across benchmarks or across different sizes of
the same benchmark, we must compare the Temporal Performance, R_T=R_B/F_B.

Because of the last paragraph, some have questioned whether one should
abandon R_B and use the Temporal Performance, R_T(N;p)=1/T(N;p), alone.
Probably one should quote both, but it is really a matter of convenience.
Values of R_B will tend to cluster around a relatively confined region of
the (R_B vs p) performance graphs, because they do approximate to the 
available hardware Mflop/s of the computer. Thus a set of results for a 
range of sizes of a range of benchmarks for a given computer tend to 
cluster together, and should give a fair idea of the range of possible 
performance, and this range should not be too large or scattered. The 
tendency will be for all benchmarks and all problem sizes to cluster near 
one value for p=1, although there will be some scatter due to vector 
length effects if vector processors are used. As p increases, the curves 
for different problem sizes and benchmarks will diverge, but since they 
are tied together at one end they can't get too far apart. Computers of 
different types may give recognisable patterns when performance results 
are displayed in this way in the (R_B vs p) plane. This may help us 
classify performance behaviour by describing the region of the plane
occupied by the benchmark results, but we need to see a lot of data first. 

It is also why I believe that an interactive graphical interface should 
be considered as an essential part (not just a sexy add-on) of the 
Parkbench performance database.   

In sharp contrast, values of time alone, and therefore R_T, will vary 
much more widely over orders of magnitude between small and large 
problems, and from one benchmark to another. It will be much more 
difficult to see any pattern of performance in the (R_T vs p) plane
or try to draw conclusions. In practice using R_T as the display metric
will be much more difficult and less useful.

                      Roger Hockney

---

From: [email-masked] (David John Schneider)
Date: Wed, 16 Jun 93 17:19:24 CDT

Roger,

I think that we are in agreement that the R_B measurement is the best
existing way of comparing the performance of different codes on
different machines.  I also agree with your conclusion that the
relative ordering of performance is unambiguous for a single code
across multiple machine if one uses the R_B metric.  This is one of
the strongest arguments in favor of the R_B metric.  The other issue
is also important -- can R_B be used to unambiguously order the
performance of different codes on different machines?  I will try to
set up an example of how R_B fails to satisfy requirements for a
unique order relation for this second question.

Let X and Y be two different machines, and let A and B denote two
different code/dataset combinations which run on both X and Y.  Assume
the following execution times:

	T(A,X) = 1
	T(B,X) = 10
	T(A,Y) = 2
	T(B,Y) = 2 

If F_B(A)=1 and F_B(B)=10, then the average R_B for X is greater than
for Y.  However, if F_B(A)=3 and F_B(B)=3, then the average R_B for X
is less than for Y.  However, it is obvious that the sum of the
execution time on X is greater than the sum of the execution times on
Y.  This example illustrates the way in which using "reasonable" but 
arbitrary normalization conventions, coupled with a "reasonable" 
single figure-of-merit, lead to confusion.

One might ask whether or not one can measure F_B accurately enough
using hardware performance monitoring equipment to eliminate this
confusion.  In fact, this is not always possible.  For example, one
can get very different operation counts for the same source
code/dataset in scalar and vector modes on vector computers.  As I
recall, Jim Hack presented examples at the US-Japan Performance
Evaluation Workshop where the hardware operation counts for individual
loops on the Y-MP can increase by a factor of 5 if the code when
executed in vector mode as opposed to scalar mode.  Despite these
large increases in operation count, the vector mode execution time can
be considerably smaller.  

				Dave

========================================================================

   Errors-To: [email-masked]
   X-Resent-To: [email-masked] ; Fri, 11 Jun 1993 15:43:29 EDT
   Errors-To: [email-masked]
   From: [email-masked]
   Date: Fri, 11 Jun 93 19:42:31 GMT

   Concerning the ordering:

			 Roger Hockney