Subject: Revised SPEEDUP section

From: [email-masked]
Date: Wed, 2 Jun 93 16:59:55 GMT

Because the definition of Speedup is of such general concern to all
members, not just those in the Methodology subcommittee, I am sending
this proposed ammendment to all committee members:
                      ***********************
\subsection{Speedup and Efficiency}

Speedup is a popular metric that has been used for many years to compare
the performance of parallel computers. However its definition is open
to ambiguity and misuse because it always begs the question "Speedup
over what?"; a question that is often not clearly answered in publications 
using this metric. Whilst preferring the use of absolute measures of
performance, such as Benchmark Performance defined earlier, the PARKBENCH
committee accepted that speedup would probably continue to be used, and
that the best policy was to sharpen-up its definition. 

Speedup is universally defined as
\begin{equation} 
                     frac{T_1}{T_p}
\end{equation}
where $T_p$ is the p-processor time to perform some benchmark, and $T_1$
is called the one-processor time. There is no doubt about the meaning
of $T_p$, because this is measured time $T(N;p)$ to perform the benchmark.
There is, however, usually considerable discussion over the meaning of $T_1$,
whether it is the time for the parallel code running on one-processor which
probably contains unnecessary parallel overheads, or whether it is the best
serial code (probably quite a different algorithm) running on one processor.
The latter choice sounds much more realistic, but would require a program
of research to determine what was the best serial algorithm, and the 
rescaling of all previously computed Speedup values every time a better
serial algorithm was discovered. An additional problem is that even if we
decide what $T_1$ should be, there may not be enough memory on a single 
node to store the whole data for a large problem suitable for using a large
MPP. It may not therefore be possible to measure $T_1$ on an MPP, however 
we define it.

The purpose of benchmarking is to compare the performance of different
computers, on the basis that the best performance corresponds to the
least wall-clock execution time. In order to use Speedup for this purpose,
it does not matter how $T_1$ is defined, or what its value is. It only
matters that the same value of $T_1$ is used to calculate all Speedup 
values used in the comparison. Looked at in this way, $T_1$ is just a
single reference time which is defined for each benchmark, and to which 
all parallel execution times are compared. The answer to the question
"over what?" is then "over $T_1$", and it is clear then why the same 
$T_1$  must be used for all comparisons of different computers on
the same benchmark. If we do not use the same $T_1$ for all comparisons,
then we are using different units to measure the performance on
the different computers. This makes as much sense as comparing the 
numerical value of the maximum speeds of three cars, when one is
measured in m.p.h, the second in feet per second and the third in m/s.

The SPEC committee uses the above proceedure in the definition of their
SPEC ratio which is defined as the Speedup over a reference time obtained
by running the defining serial code on a VAX11/780. The problem is that
periodically it seems necessary to update these reference times to a
currently available computer, or to keep a VAX11/780 going in a special
museum (I suppose it would be the Smithsonian or NPL) in a similar way
as the standard yard or metre are carefully maintained. Nevertheless
there is no doubt that keeping a constant value of $T_1$, however it
is defined, for each benchmark is the only way of making Speedup an 
acceptable metric for measuring and comparing computer performance.  

Defining $T_1$ as a reference time unrelated to the parallel computer
being benchmarked unfortunately has the conseqence that certain 
properties that many people regard as essential to the idea of 
Speedup are lost:

\begin{enumerate}
\item It is no longer necessarilly true that the Speedup of the
      parallel code on one processor is unity. It may be, but only
      by chance.
\item It is no longer true that the maximum Speedup using $p$-processors
      is $p$.
\item Because of the last item, Efficiency=Speedup/$p$ is no longer
      a meaningful measure of processor utilisation.
\end{enumerate}

Thus it appears that if we sharpen-up the definition of Speedup to make
it an acceptable metric for comparing the performance of different
computers, we have to throw way the main properties which have made
the concept of Speedup useful in the past. There is a choice: keep
Speedup with its traditional properties, and accept that it has no place
as a metric for comparing computer performance (i.e. in benchmarking), or 
define Speedup in a way that can be used in benchmarking, and lose the
traditional properties. There is no middle way, or possible compromise.

If we use $T_1$ as the time for the defining serial code on a very fast
single processor (currently, say, a CRAY C90), then I am sure that
manufacturers would be reluctant to having to quote the Speedup of their MPP
with hundreds of processors in the above way. If the Speedup of the 100
processor MPP over a single node of the MPP is a respectable 80, say, it
is likely that the Speedup over $T_1$  would be reduced to about 10 or less,
because the fast single processor is likely to be at least ten times faster 
than the workstation chips used in MPPs. 

[For all the above reasons I, personally RWH, do not believe that Speedup
can be saved as a useful metric for comparing computer performance, and
that it should only be kept as a convenient metric to use when 
optimising code on a particular multiprocessor computer in isolation. 
However if the committee wishes to allow its use as a metric the following 
rules should apply:]

The use of absolute measures of computer performance such as Temporal 
(tstep/s) or Benchmark performance (Mflop/s based on a given nominal 
flop-count) avoid the above problems of definition. However,
if Speedup is used as a metric for comparing computer performance on
benchmarks, then the PARKBENCH committee requires that:

\begin{enumerate}
\item The value of $T_1$ in seconds that was used in the speedup calculation
      must be quoted along with the value of Speedup 
\item The same value of $T_1$ must be used when calculating all Speedup
      values for a particular benchmark.
\item The benchmark writer must provide, as part of the definition of the
      benchmark, the value of $T_1$ in seconds that is to be used. 
\item Only if the above rules are obeyed will the benchmark results be
      accepted as unambiguous and entered into the PDS database.
\end{enumerate}

---

From: [email-masked] (David John Schneider)
Date: Wed, 2 Jun 93 17:25:43 CDT

Several weeks ago at the first meeting of the newly reconstituted
SPEC-Perfect steering committee, we also got tangled up in policy
questions related to speedup and other derived quantities.  After the
usual heated discussions, we decided to simply report only elapsed
times (i.e. time-to-solution or it's inverse).  As usual, this
conclusion was a result of a lot of discussion, much of which I expect
was the same as occurred at the PBWG meeting.  Since the SPEC-Perfect
meeting, I have spent some time trying to understand why speedup and
other issues always provoke such contentious discussions.  The current
debate in the PBWG has prompted me to try to write down some of these
ideas to clarify my own thinking.  The basic conclusion that I have
reached is that there are two important classes of problems in basic
performance evaluation methodology today, both of which can be readily
addressed.  Since I have been unable to attend PBWG meetings and
directly participate in methodology subcommittee meetings, I'll
attempt to summarize my thoughts here.

The first class of problems is very basic -- we are searching for
something which does not exist.  For example, there is tendency to
expend considerable effort to define a single, universal figure of
merit for comparing machines when, in fact, there are good reason to
think that this cannot ever be done in a unique and unbiased manner.
It would be nice to be able to say that machine X is better
(eg. faster) than machine Y, with no qualifications.  However, this
simply isn't possible (see below).

Second, there are other performance measures such as speedup which
are, at best, loosely correlated with an end user's perception of
delivered performance and therefore are of little real utility.  I
agree with all of Roger's comments in this regard.  Nevertheless,
these loosely defined performance measures tend to get a lot of press
in both academic and popular publications because they are "easy to
understand".  In fact, the contentious debates on these issues
indicate that this "understanding" is largely illusory and
unsatisfactory when taken out of the context or when this context
is not provided at all.

I feel that both of these classes of problems can be overcome by
adopting and adhering to an axiomatic approach.  The utility an
axiomatic approach in defining a set of logically consistent
performance measures has been recently advocated by directly by David
Snelling.  Others such as Roger Hockney, John Larson, David Bailey
have argued forcefully for the need of a well defined mathematical
framework, and the axiomatic approach provides one alternative for
constructing such a framework.  One of the the most important aspects
of axiomatic approach is that it forces one to precisely and
explicitly state assumptions regarding the measurement process that
have previously remained implicit or imprecise.  In the axiomatic
approach, computer performance evaluation becomes the study of the
complicated mapping from the set of computer codes into the
multidimensional space of measureable quantities which obey the
prescribed axioms (additivity, positivity, etc.).  A second important
aspect of the axiomatic approach is that makes it clear that one
cannot construct a unique, universal, unbiased ranking scheme for
computer performance simply because there is no natural ordering to
the underlying space of measurements.  Therefore, the search for a
universal figure of merit is certain to fail.

Would a well informed computer scientist attempt to develop an
algorithm for determining whether or not a Turing machine will halt
when presented with an arbitrary input?  Would a practically minded
physicist or engineer write a grant to develop a perpetual motion
machine or a faster-than-light communication system?  In all cases, if
one accepts the usual mathematical description of the underlying
problem, then all of these endeavors can be proven futile.  Why
then in benchmarking do we continue to pursue the goal of a single
figure of merit?

As emphasized by David Snelling, the axiomatic approach has been
extrordinarily successful in the physical sciences.  For example, one
can meaningfully ascribe quantities such as energy and momentum to
particles, waves fields, and combinations thereof.  More recently, in
the hands of Shannon and others the field of communication theory
underwent a spectacular revolution from a raw empiricism to a
quantitative science in a space of only several years by employing a
very simple system of axioms and a clear set of definitions.  In this
case the basic axioms were largely borrowed from the foundations of
statistical physics (information content or entropy should be an
extensive, non-negative function, etc.).  Shannon's major contibution
was to recognize that it is possible distinguish between the precisely
definable notion of "information content", and the loosely defined
"meaning" of this information to the recipient of the message.  

I believe that the same type of precise thinking which was so
successfully applied by Shannon to transform communication theory into
a quantitative science also needs to be applied to performance
evaluation.  The list of existing performance measures which can be
incorporated into an axiomatic framework is very remarkably short, and
Roger Hockney has enumerated essentially of the time-based measures in
hsi previous versions of PBWG documents.  I personally think it is a
large step backwards to include speedup in light of the sound
arguments against it.  The SPEC-Perfect group steering committee
concluded that the major argument in favor of speedup and single
figures of merit was their current popularity, and this reason was
insufficient for us to adopt them as part of our basic measurement and
reporting methodology.

--

		Dave Schneider 

		University of Illinois at Urbana-Champaign 
		Center for Supercomputing Research and Development
		367 Computer and Systems Research Laboratory
		1308 W. Main Street
		Urbana, IL  61801-2307
		MC-264

		phone : (217) 244-0055  
		fax   : (217) 244-1351
		E-mail: [email-masked]

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

From: [email-masked]
Date: Wed, 2 Jun 93 16:59:55 GMT
To: [email-masked]
Subject: Revised SPEEDUP section

	[stuff deleted]