Subject: Generalised Speedup

From: [email-masked]
Date: Thu, 10 Jun 93 15:50:42 GMT

COMMENTS ON GENERALISED SPEEDUP
              -------------------------------
                      Roger Hockney

I would like to thank Xian-He Sun for contributing to the Speedup 
debate, in suggesting that PARKBENCH should consider Generalised Speedup 
as a Performance metric. The suggestion is interesting, but I do not 
favour it myself for the following reasons:
  (1) If generalised speedup is defined as
                          W(N;p)*T(N;1)
                GS(N;p) = -------------
                          W(N;1)*T(N;p)
then to make the number given for GS unambiguous, we must ask that the 
benchmarker give the values used for W(N;p), W(N;1) and T(N;1), so that
we can work out the time it took to run the benchmark = T(N;p). This is
impractical and unnecessarily complicated.
  (2) In comparing a parallel implementation with a serial one, it is 
essential that we use the same flop-count or work. That is to say, not
give the parallel version credit for performing unnecessary redundant
operations, i.e. we require W(N;p)=W(N,1). In this case, of course,
generalised speedup reduces to ordinary speedup, and my comments about
the undesirabilty of ordinary speedup have already been expressed. 
  (3) In any case I do not understand what generalised speedup is 
supposed to be a measure of? Unless this can be satisfactorily
answered, we should not use it.
  (4) In general, we must first decide what the objective of parallel
computing is, and then pick a metric that measures this property.
Some possible objectives are to design code and build computers 
which solve specified problems called the benchmarks: 
   (a) in the LEAST ELAPSED WALL-CLOCK TIME.
   (b) that generate the highest hardware Mflop/s, R_H(N;p), defined 
       as the sum of all flop actually performed in all processors
       (measured possibly by hardware monitors), divided by the 
       elapsed wall-clock time. 
   (c) that generate the highest self-speedup on a multiprocessor, 
       defined as SS(p)=T(1)/T(p) with T(1)=time on one-processor 
       of the same computer.
It is obvious to me, that we seek objective (a); and that objectives (b)
and (c) are both irrelevant distractions (unless one wishes to apply for 
the Gordon Bell award!). Understanding of parallel benchmarking starts
when one realises that (b) and (c) do not necessarilly imply (a). 
  (5) Having decided that the objective is to minimise elapsed wall-clock
time, we must choose only metrics that increase in value as this time
decreases, and can therefore be used to rank computers in the order
we want. Such metrics are:
    (d) Temporal Performance,  R_T(N;p)=1/T(N;p)
    (e) Benchmark Performance, R_B(N;p)=F_B(N)/T(N;p)
        with the nominal flop-count F_B(N) defined as part of the 
        benchmark and never changed. That is we use the same F_B(N)
        for all computers that we compare.
    (f) Absolute-Speedup,      AS(N;p)=T(N;1)/T(N;p)
        where T(N;1) is defined in seconds as part of the benchmark
        definition. It may or may not correspond to the one-processor
        time on an actual computer. There is a different T(N;1) for
        each problem size, N, but for any problem size, it is fixed 
        for all time (probably a formula has to be given). That is
        we use the same T(N;1) for all computers we compare.
Note that neither the hardware performance R_H(N;p)=F_H(N)/T(N;p), nor
the self-speedup SS(N;p)=T(N;1)/T(N;p) have the desired property, because
the numerators may both change as we go from computer to computer. In
self-speedup, T(N;1) is the time to run the benchmark on one processor
of the system being tested. The number therefore changes when one goes 
to another computer, but we do maintain the usually assumed properties
of speedup (see last note). 
In contrast, of course, with absolute-speedup T(N;1) is
published as part of the benchmark description, and the same number
is used in calculating the absolute-speedup on all computers. Absolute-
Speedup can therefore be used to order computers in the way we want, BUT
we have lost the usually expected properties of speedup (see last note).
  (6) I agree with Dave Schneider, and have never believed that one can
expect to quantify the speed of a computer with one number. In fact I
am against any form of averaging, and think that the raw performance
data should be examined as a function of at least two variables,
namely problem size and number of processors. Hence my desire (need)
to see sufficient performance points measured to be able to plot graphs 
(hopefully in a fairly standard format) to show this multidimensional
performance surface. 
  (7) TO CONCLUDE: I dont like generalised speedup also because it
complicates an already difficult picture. Although I have defined
Absolute-Speedup as a possible metric with a sharpened-up definition, 
I do not think we should use it because it is bound to be confused 
with self-speedup, which I know we must not allow as a metric, because 
it is just plain WRONG. My position is that we should stick very much 
to my original draft (disallowing Speedup or Efficiency). Although we 
might leave-in the definition of Hardware Performance, as a definition,
the text should make clear that it is not an appropriate metric
to use to compare the performance of benchmarks.
  (8) How do you like my definitions of self-speedup and absolute-
speedup to distinguish two very different metrics which seem to
get confused? I am sure that many people think of self-speedup when
asked what speedup means; but then think they can use it as an
absolute-speedup when they come to talk about performance comparisons.
Not so.
                          Roger Hockney

---

From: [email-masked] (David John Schneider)
Date: Thu, 10 Jun 93 13:56:21 CDT

Roger,

The basic reason that I finally decided to advocate reporting only
elapsed times is that, despite the fact that the R_B metric formally
carries the units of Mflops/sec, it does not correspond to what one
would actual compute if one counted floating point operations and
measured elapsed time on all machines.  The problem is that the
definition of F_B(N) is arbitrary.  As such, R_B is not a measure of
computational rate, it is simply an arbitrarily scaled time-based
measure.  Because the relative ordering can be switched by altering
the assigned F_B values, whether the R_B of code A on machine X is
greater or less than the R_B of code B on machine Y becomes a matter
of definition, not measurement.  Therefore, I do not think that R_B is
an acceptable long-term solution to the problem of needing an unbiased
metric to compare the performance of different codes on different
machines.

In your response to my previous note, you asked for more information
regarding how to implement an axiomatically based information theory
approach.  I will try to sketch my current ideas in this area here.
However, I would like to make it clear that I am not advocating that
Perfect, PARKBENCH, or anyone else to stop what they are doing to
pursue this line of inquiry.  Instead, I am simply trying understand
the cause of the confusion regarding metrics, and to see if I can find
satisfactory long-term solutions.  In the mean time, it is important
to continue to muddle along with possible incomplete or even
inconsistent definitions.  As far as I can tell, the R_B measure that
you have advocated is the least biased of the current candidates for
metrics for use in comparing the performance of different codes on
different machines.  So, on with the polemic...

Most proposals to date for F_B(N) such as those used by Linpack and
previously by Perfect, as well as the current PARKBENCH effort, remove
this ambiguity by fiat.  As such, they all suffer from the ills
described above.  To me, the challenge is to develop methods to
measures of "computational work" such as F_B(N) from first
principles.  This is where I believe an axiomatic approach such as
used in information theory can be useful.  All computer instructions
ultimately reduce to a common currency, Boolean logic.  The value and
generality of information theory is that it is formulated in terms of
the "alphabet" in which the message is presented, not the meaning
assigned to it by the recipient.  All bits and bit-level operations
should be treated equally.

One way to to remove the ambiguity would be to define F_B(N) as the
minimum floating point operation count needed for each value of N.  In
many practice, it is known that it is possible to make tradeoffs which
increase the number of integer/logical operations to reduce the number
of floating point operations.  The use of indirect addressing for
sparse matrix problems is a classic example of this sort of tradeoff.
The fact that the value of these tradeoffs, as measured by reduction
in elapsed time, are related to architectural issues implies that a
satisfactory definition of computational work must treat integer,
logical and floating point operations on the same footing.  However,
some of the basic operations are clearly more difficult to implement 
than others, thus it is unfair to assign equal "difficulty" measures
to each operation.

I think one must eventually proceed by computing the complexities of a
given set of atomic operations using well defined input and output
datatypes according to a well defined set of rules.  If complexities
of the atomic operations are known, perhaps it will be possible to
obtain find the minimum "work" rather than the minimum floating point
operation count.  Proposals for determining the complexity of atomic
operations were made by Hellerman and Rozwadowski in the early
1970's.  Hellerman's ideas met with sharp criticism, especially by
Welch.  Some of Welch's criticisms are valid in that they are related
to ambiguities in Hellerman's definitions.  I feel that Hellerman
addressed most of the valid criticisms in his response to Welch's
letter.  With a little(?) more work, I think that the
Hellerman-Rozwadowski scheme can be made into a practical method.
This scheme simply recognizes the fact that all computer operations
are implemented at the lowest level by Boolean logic.  At this level
the distinction between the interpretation of the bits is irrelevant.
A bit is a bit regardless of whether it is part of a character
variable or a double precision floating point variable.  The
complicated atomic operations on larger datatypes can be summarized in
tabular form.  The Hellerman-Rozwadowski definition of work is the
information theoretic "entropy" of these tables.  Both Hellerman and
Rozwadowski based their table construction methods on traditional
Boolean logic operations.  Alternative proposals based on "reversible"
elements have been put forward by Charles Bennett, Richard Feynman,
and others.  Choosing between these alternatives amounts to selecting
the "alphabet" used to describe the Boolean operations which are used
to construct higher-level operations.  As such, they affect the final
value computed values for the "difficulty" of each operation.  However, 
the need for a choice of "alphabets" is clear.  Moreover, the choice
which is actually can be clearly and concisely stated.

Because of the widespread adoption of the IEEE floating point standard
which defines both the atomic operations and the datatypes, I suggest
that this would be a reasonable place to start.  In comparison, the
integer and logical datatypes and associated operations are easy.
Hellerman has already carried out a detailed analysis of the integer
and logical operations defined by the IBM S/360 architecture.  I 
think that one can construct architecturally neutral definitions.

I apologize for not being able to included bibliographic references 
in this note since I do not have the papers with me at the moment.
I will try to remember to post them separately.

				Dave

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

   Errors-To: [email-masked]
   X-Resent-To: [email-masked] ; Thu, 10 Jun 1993 12:05:40 EDT
   Errors-To: [email-masked]
   From: [email-masked]
   Date: Thu, 10 Jun 93 15:50:42 GMT