Subject: method5.tex

From: "Michael W. Berry" <[email-masked]>
Date: Wed, 01 Sep 1993 22:03:01 -0400

This is a revision of the methodology chapter of the PARKBENCH
report submitted by David Bailey.

Regards,

Mike
------- Forwarded Message

Date: Wed, 1 Sep 93 17:24:22 -0700
From: [email-masked] (David H. Bailey)
To: [email-masked]
Subject: Revised Methodology section.  Please distribute to method group

%file method5.tex

% Compiled by David Bailey for methodology subcommittee.
% Text below submitted by Roger Hockney to methodology subcommittee.
% This text includes revision by Bailey on 01 Sep 1993.

\chapter{Methodology}

\section{Philosophy}

One might ask why anyone should care about developing a standardized,
rigorous and scientifically tenable methodology for studying the
performance of high-performance computer systems.  There are several
reasons why this is an important undertaking:

\begin{enumerate}

\item To establish and maintain high standards of honesty and
integrity in our profession.

\item To improve the status of supercomputer performance analysis as
a rigorous scientific discipline.

\item To reduce confusion in the high-performance computing literature.

\item To increase understanding of these systems, both at a low-level
hardware or software level and at a high-level, total system
performance level.

\item To assist the purchasers of high-performance computing equipment
in selecting systems best suited to their needs.

\item To reduce the amount of time and resources vendors must expend in
implementing multiple, redundant benchmarks.

\item To provide valuable feedback to vendors on bottlenecks that can
be alleviated in future products.

\end{enumerate}

It is important to note that researchers in many scientific
disciplines have found it necessary to establish and refine standards
for performing experiments and reporting the results.  Many scientists
have learned the importance of standard terminology and notation.
Chemists, physicists and biologists long ago discovered the importance
of ``controls'' in their experiments.  The issue of repeatability
proved crucial in the recent ``cold fusion'' episode.  Medical
researchers have found it necessary to perform ``double-blind''
experiments in their field.  Psychologists and sociologists have
developed highly refined experimental methodologies and advanced data
analysis techniques.  Political scientists have found that subtle
differences in the phrasing of a question can affect the results of a
poll.  Researchers in many fields have found that environmental
factors in their experiments can significantly influence the measured
results; thus they must carefully report all such factors in their
papers.

If supercomputer performance analysis and benchmarking is ever to be
taken seriously as a scientific discipline, certainly its
practitioners should be expected to adhere to standards that prevail
in other disciplines.  This document is dedicated to promoting these
standards in our field.

\section{Fundamental Metrics}

The conclusions drawn from a benchmark study of computer performance
depend not only on the basic timing results obtained, but also on
the way these are interpreted and converted into performance figures.
The choice of the performance metric, may itself influence the 
conclusions. For example, do we want the computer that generates the 
most megaflop per second (or has the highest Speedup), or the computer 
that solves the problem in the least time? It is now well known
that high values of the first metrics do not necessarily imply the 
second property. This confusion can be avoided by choosing a more 
suitable metric that reflects solution time directly, for example 
either the Temporal, Simulation or Benchmark performance, defined below. 
This issue of the sensible choice of performance metric is becoming
increasing important with the advent of massively parallel computers
which have the potential of very high megaflop rates, but have 
much more limited potential for reducing solution time. 

\section{Time Measurement}

Before other issues can be considered, we must discuss the measurement
of run time.  In recent years a consensus has been reached among many
scientists in the field that the most relevant measure of run time is
actual wall-clock elapsed time.  This measure of time will be required
for all ParkBench results that are posted to the database.

Elapsed wall-clock time means the time that would be measured on an
external clock that records the time-of-day or even Greenwich mean
time (GMT), between the start and finish of the benchmark.  We are not
concerned with the origin of the time measurement, since we are taking
a difference, but it is important that the time measured would be the
same as that given by a difference between two measurements of GMT, if
it were possible to make them.  It is important to be clear about
this, because many computer clocks (e.g. Sun Unix function ETIME)
measure elapsed CPU time, which is the total time that the process or
job which calls it has been executing in the CPU.  Such a clock does
not record time (i.e. it stops ticking) when the job is swapped out of
the CPU.  It does not record, therefore, any wait time which must be
included if we are to assess correctly the performance of a parallel
program.  On some systems, scientists have found that even for
programs that perform no explicit I/O, considerable ``system'' time is
nonetheless involved, for example in fetching certain library routines
or other data.

Only timings actually measured may be cited for ParkBench benchmarks
(and we strongly recommend this practice for other benchmarks as
well).  Extrapolations and projections, for instance to a larger
number of nodes, may not be employed for any reason.  Also, in the
interests of repeatability it is highly recommended that timing runs
be repeated, several times if possible.

Two low-level benchmarks are provided in the ParkBench~ suite to test
the precision and accuracy of the clock that is to be used in the
benchmarking.  These should be run first, before any benchmark
measurements are made.  They are:
\begin{enumerate}

\item TICK1 - measures the precision of the clock by measuring the time 
              interval between ticks of the clock. A clock is said to
              tick when it changes its value.

\item TICK2 - measures the accuracy of the clock by comparing a given
              time interval measured by an external wall-clock (the
              benchmarker's wrist watch is adequate) with the same
              interval measured by the computer clock. This tests the
              scale factor used to convert computer clock ticks to seconds, 
              and immediately detects if a CPU-clock is incorrectly being 
              used.
\end{enumerate} 

The fundamental measurement made in any benchmark is the elapsed
wall-clock time to complete some specified task. All other performance
figures are derived from this basic timing measurement. The benchmark
time, $T(N;p)$, will be a function of the problem size, $N$, and the
number of processors, $p$. Here, the problem size is represented by
the vector variable, $N$, which stands for a set of parameters
characterising the size of the problem: e.g. the number of mesh points
in each dimension, and the number of particles in a particle-mesh
simulation.  Benchmark problems of different sizes can be created by
multiplying all the size parameters by suitable powers of a single
scale factor, thereby increasing the spatial and particle resolution
in a sensible way, and reducing the size parameters to a single size
factor (usually called $\alpha$).

We believe that it is most important to regard execution time and
performance as a function of at least the two variables $(N,p)$, which
define a parameter plane. Much confusion has arisen in the past by
attempts to treat performance as a function of a single variable, by
taking a particular path through this plane, and not stating what path
is taken.  Many different paths may be taken, and hence many different
conclusions can be drawn.  It is important, therefore, always to
define the path through the performance plane, or better as we do
here, to study the shape of the two-dimensional performance hill.  In
some cases there may even be an optimum path up this hill.

\section{Units and Symbols}

A rational set of units and symbols is essential for any numerate
science including benchmarking. The following extension of the
internationally agreed SI system of physical units \cite{SI75} is 
made to accommodate the needs of computer benchmarking.

The value of a variable comprises a pure number stating the number of
units which equal the value of the variable, followed by a unit
symbol specifying the unit in which the variable is being measured.
A new unit is required whenever a quantity of a new nature arises,
such as e.g. the first appearance of vector operations, or message 
sends. Generally speaking a unit symbol should be as short as
possible, consistent with being easily recognised and not already
used. The following have been found necessary in the characterisation
of computer and benchmark performance in science and engineering. 
No doubt more will have to be defined as benchmarking enters new areas.

\medskip
New unit symbols and their meaning: 
\begin{enumerate}
\item \flop : floating-point operation [latex \verb1\1flop]
\item \inst : instruction of any kind [latex \verb1\1inst]
\item \inop : integer operation [latex \verb1\1inop]
\item \vecop: vector operation [latex \verb1\1vecop]
\item \send: message send operation [latex \verb1\1send]
\item \iter : iteration of loop [latex \verb1\1iter]
\item \mref : memory reference (read or write) [latex \verb1\1mref]
\item \barr : barrier operation [latex \verb1\1barr]
\item \bit  : binary digit (bit) [latex \verb1\1bit]
\item \B    : byte (groups of 8 bits) [latex \verb1\1B]
\item \sol  : solution or single execution of benchmark 
              [latex \verb1\1sol]
\item \w    : computer word. Symbol is lower case (W means watt) 
              [latex \verb1\1w]
\end{enumerate}
When required a subscript may be used to show the number of bits
involved in the unit. For example: a 32-bit floating-point operation
${\flop}_{32}$, a 64-bit word ${\w}_{64}$, also we have
${\bit}={\w}_1$, ${\B}={\w}_8$, ${\w}_{64}= 8 {\B}$.

Note that flop, mref and other multi-letter symbols are inseparable
four or five-letter symbols. The character case is significant in all
unit symbols so that e.g. Flop, Mref, $W_{64}$ are incorrect. Unit
symbols should always be printed in roman type, to contrast with
variables names which are printed in italic. To aid in the use of
roman type, especially within Latex maths mode, Latex commands have
been defined for each unit, these commands being a backslash followed
by the unit symbol (except for '\inop' and '\bit' whose names are
changed in the command to avoid a clash with already defined system
commands). Such commands will print in roman type wherever they
occur. Because 's' is the SI unit for seconds, unit symbols like
'sheep' do not take 's' in the plural. Thus one counts: one flop, two
flop, ..., one hundred flop etc. This is especially important when the
unit symbol is used in ordinary text as a useful abbreviation, as
often, quite sensibly, it is.

\medskip
SI provides the standard prefixes:
\begin{enumerate}
\item k    : kilo meaning $10^3$
\item M    : mega meaning $10^6$
\item G    : giga meaning $10^9$
\item T    : tera meaning $10^{12}$
\end{enumerate}
This means that we cannot use M to mean $1024^2$ (the binary mega) as is 
often done in describing computer memory capacity, e.g. 256 MB. We can 
however introduce the new prefix:
\begin{enumerate}
\item K    : meaning 1024, then use a subscript 2 to indicate the binary
             versions
\item $\mbox{\rm M}_2$    : binary mega $1024^2$
\item $\mbox{\rm G}_2$    : binary giga $1024^3$
\item $\mbox{\rm T}_2$    : binary tera $1024^4$
\end{enumerate}
In most cases the difference between the mega and the binary mega (4\%) 
is probably unimportant, but it is important to be unambiguous. In this
way one can continue with existing practice if the difference doesn't 
matter, and have an agreed method of being more exact when necessary.
For example, the above memory capacity was probably intended to mean
$256 \mbox{\rm M}_2 \B$.

As a consequence of the above, an amount of computational work involving
$4.5 \times 10^{12}$ floating-point operations is correctly written as 
4.5 Tflop. Note that the unit symbol Tflop is never pluralised with an
added 's', and it is therefore incorrect to write the above as 4.5 Tflops 
which could be confused with a rate per second. The most frequently used 
unit of performance, millions of floating-point operations per second 
is correctly written Mflop/s, in analogy to km/s. The slash is necessary 
and means 'per',  because the 'p' is an integral part of the unit symbol 
'flop' and cannot also be used to mean 'per'.  

\section{Floating-Point Operation Count}

Although we discourage the use of millions of floating-point
operations per second as a performance metric, it can be a useful
measure if the number of floating-point operations, $F(N)$, needed to
solve the benchmark problem is carefully defined.

For simple problems (e.g. matrix multiply) it is sufficient to use a
theoretical value for the floating-point operation count (in this case
$2n^3$ flop, for nxn matrices) obtained by inspection of the code or
consideration of the arithmetic in the algorithm. For more complex
problems containing data-dependent conditional statements, an
empirical method may have to be used.  The sequential version of the
benchmark code defines the problem and the algorithm to be used to
solve it. Counters can be inserted into this code or a hardware
monitor used to count the number of floating-point operations. The
latter is the procedure followed by the {\sc PERFECT} Club
\cite{Berr89}. In either case a decision has to be made regarding the
number of flop that are to be credited for different types of
floating-point operations, and we see no good reason to deviate from
those chosen by McMahon \cite{Ma88} when the Mflop/s measure was
originally defined.  These are:

\begin{table}[h]
\centering
\begin{tabular}{ll}
add, subtract, multiply		& 1 flop \\
divide, square-root		& 4 flop \\
exponential, sine etc.		& 8 flop (this figure will be adjusted) \\   
{\sc IF(X .REL. Y)}		& 1 flop \\
\end{tabular}
\end{table}

Some members of the committee felt that these numbers, derived in the
1970s, no longer correctly reflected the situation on current
computers.  However, since these numbers are only used to calculate a
nominal benchmark flop-count, it is not so important that they be
accurate. The important thing is that they do not change, otherwise
all previous flop-counts would have to be renormalised.  In any case,
it is not possible for a single set of ratios to be valid for all
computers and library software. I (rwh) suggest the committee stays
with the above ratios until such time as they become wildly wrong and
extensive research provides us with a more realistic set.

We distinguish two types of operation count. The first is the nominal
benchmark floating-point operation count, $F_B(N)$, which is found in
the above way from the defining Fortran77 sequential code. The other
is the actual number of floating-point operations performed by the
hardware when executing the distributed multi-node version,
$F_H(N,p)$, which may be greater than the nominal benchmark count, due
to the distributed version performing redundant arithmetic
operations. Because of this, the hardware flop count may also depend
on the number of processors on which the benchmark is run, as shown in
its argument list.

\section{Performance Metrics}

Given the time of execution $T(N;p)$ and the flop-count $F(N)$ several
different performance measures can be defined.  Each metric has its
own uses, and gives different information about the computer and
algorithm used in the benchmark.  It is important therefore to
distinguish the metrics with different names, symbols and units, and
to understand clearly the difference between them.  Much confusion and
wasted work can arise from optimising a benchmark with respect to an
inappropriate metric. The principal performance metrics are:

\subsection{Temporal Performance}

If we are interested in comparing the performance of different
algorithms for the solution of the same problem, then the correct
performance metric to use is the {\it Temporal Performance}, $R_T$,
which is defined as the inverse of the execution time
\begin{equation}
                            R_T(N;p)=T^{-1}(N;p)              \label{Eqn(1)}
\end{equation}
The units of temporal performance are, in general, solutions per
second (sol/s), or some more appropriate absolute unit such as
timesteps per second (tstep/s). With this metric we can be sure that
the algorithm with the highest performance executes in the least time,
and is therefore the best algorithm. We note that the number of flop
does not appear in this definition, because the objective of algorithm
design is not to perform the most arithmetic per second, but rather it
is to solve a given problem in the least time, regardless of the
amount of arithmetic involved.  For this reason the temporal
performance is also the metric that a computer user should employ to
select the best algorithm to solve his problem, because his objective
is also to solve the problem in the least time, and he does not care
how much arithmetic is done to achieve this.

\subsection{Simulation Performance}

A special case of temporal performance occurs for simulation programs
in which the benchmark problem is defined as the simulation of a
certain period of physical time, rather than a certain number of
timesteps. In this case we speak of the {\em Simulation Performance}
and use units such as {\em simulated days per day} (written sim-d/d or
'd'/d) in weather forecasting, where the apostrophe is used to
indicate 'simulated'; or {\em simulated pico-seconds per second}
(written sim-ps/s or 'ps'/s) in electronic device simulation. It is
important to use simulation performance rather than timestep/s if one
is comparing different simulation algorithms which may require
different sizes of timestep for the same accuracy (for example an
implicit scheme that can use a large timestep, compared with an
explicit scheme that requires a much smaller step). In order to
maintain numerical stability, explicit schemes also require the use of
a smaller timestep as the spatial grid is made finer. For such schemes
the simulation performance falls off dramatically as the problem size
is increased by introducing more mesh points in order to refine the
spatial resolution: the doubling of the number of mesh-points in each
of three dimensions can reduce the simulation performance by a factor
near 16 because the timestep must also be approximately halved. Even
though the larger problem will generate more Megaflop per second, in
forecasting, it is the simulated days per day (i.e. the simulation
performance) and not the Mflop/s, that matter to the user.

As we see below, benchmark performance is also measured in terms of the amount
of arithmetic performed per second or Mflop/s. However it is important to
realise that it is incorrect to compare the Mflop/s achieved by two algorithms 
and to conclude that the algorithm with the highest Mflop/s rating is the best
algorithm. This is because the two algorithms may be performing quite 
different amounts of arithmetic during the solution of the same problem.
The temporal performance metric, $R_T$, defined above, has been introduced
to overcome this problem, and provide a measure that can be used to compare
different algorithms for solving the same problem. However, it should be 
remembered that the temporal performance only has the same meaning within the 
confines of a fixed problem, and no meaning can be attached to a
comparison of the temporal performance on one problem with the temporal
performance on another.

\subsection{Benchmark Performance}

In order to compare the performance of a computer on one benchmark with 
its performance on another, account must be taken of the different amounts of 
work (measured in flop) that the different problems require for their solution.
Using the flop-count for the benchmark, $F_B(N)$, we can
define the {\em Benchmark Performance} as
\begin{equation}
                            R_B(N;p)=F_B(N)/{T(N;p)}           \label{Eqn(2)}
\end{equation}
The units of benchmark performance are Mflop/s (benchmark name), where we 
include the name of the benchmark in parentheses to emphasise that the 
performance may depend strongly on the problem being solved, and to emphasise 
that the values are based on the nominal benchmark flop-count. In other 
contexts such performance figures would probably be quoted as examples of the 
so-called {\em sustained} performance of a computer. We feel that the use of 
this term is meaningless unless the problem being solved and the degree of 
code optimisation is quoted, because the performance is so varied across 
different benchmarks and different levels of optimisation. Hence we favour 
the quotation of a selection of benchmark performance figures, rather than a 
single sustained performance, because the latter implies that the quoted 
performance is maintained over all problems.

Note also that the flop-count $F_B(N)$ is that for the defining sequential 
version of the benchmark, and that the same count is used to calculate $R_B$ 
for the distributed-memory (DM) version of the program, even though the DM 
version may actually perform
a different number of operations.  It is usual for DM programs to perform more
arithmetic than the defining sequential version, because often numbers are
recomputed on the nodes in order to save communicating their values from a
master processor. However such calculations are redundant (they have already
been performed on the master) and it would be incorrect to credit them to the
flop-count of the distributed program. 

Using the sequential flop-count in the
calculation of the DM programs benchmark performance has the additional 
advantage that it is possible to conclude that, for a given benchmark,
the implementation that has the highest benchmark performance is the best 
because it executes in the least time.  This would not necessarily be the 
case if a different $F_B(N)$ were used for different implementations of the 
benchmark. For example, the use of a better algorithm which obtains the
solution with less than $F_B(N)$ operations will show up as higher benchmark
performance. For this reason it should cause no surprise if the benchmark 
performance occasionally exceeds the maximum possible hardware performance. 
To this extent benchmark performance Mflop/s must be understood
to be nominal values, and not necessarily exactly the number of operations
executed per second by the hardware, which is the subject of the next
metric. The purpose of benchmark performance is to compare different
implementations and algorithms on different computers for the solution of
the same problem, on the basis that the best performance means the least
execution time. For this to be true $F_B(N)$ must be kept the same for
all implementations and algorithms.  

\subsection{Hardware Performance}

If we wish to compare the observed performance with the theoretical 
capabilities of the computer hardware, we must compute the actual number of
floating-point operations performed, $F_H(N;p)$, and from it the actual
{\em Hardware Performance} 
\begin{equation}
                            R_H(N;p)=F_H(N,p)/{T(N;p)}             \label{Eqn(3)}
\end{equation}
The hardware performance also has the units Mflop/s, and will have the same 
value as the benchmark performance for the sequential version of the benchmark. 
However, the hardware performance may be higher than the benchmark performance 
for the distributed version, because the hardware performance gives credit for 
redundant arithmetic operations, whereas the benchmark performance does not.
Because the hardware performance measures the actual floating-point operations
performed per second, unlike the benchmark performance, it can never exceed
the theoretical peak performance of the computer.

Assuming a computer with multiple-CPUs each with multiple arithmetic pipelines,
delivering a maximum of one flop per clock period, the theoretical peak value
of hardware performance is
\begin{equation}
   r^*= \frac{fl.pt.pipes/CPU}{clock.period}\times number.CPUs   \label{Eqn(4)}
\end{equation}
with units of Mflop/s if the clock period is expressed in microseconds. By 
comparing the measured hardware performance, $R_H(N;p)$, with the theoretical 
peak performance, we can assess the fraction of the available performance that 
is being realised by a particular implementation of the benchmark.

\subsection{Speedup, Efficiency and Performance per Node}

``Parallel speedup'' is a popular metric that has been used for many
years in the study of parallel computer performance.  However, its
definition is open to ambiguity and misuse because it always begs the
question ``speedup over what?''  

Speedup is usually defined as
\begin{equation} 
       \frac{T_1}{T_p}
\end{equation}

\noindent 
where $T_p$ is the $p$-processor time to perform some benchmark, and
$T_1$ is the one-processor time.  There is no doubt about the meaning
of $T_p$ --- this is the measured time $T(N;p)$ to perform the
benchmark.  There is often considerable dispute over the meaning of
$T_1$: should it be the time for the parallel code running on one
processor, which probably contains unnecessary parallel overhead, or
should it be the best serial code (possibly using a different
algorithm) running on one processor?  Many scientists feel the latter
is a more responsible choice, but this requires research to determine
the best practical serial algorithm for the given application.  If at
a later time a better algorithm is found, current speedup figures
might be considered obsolete.  An additional difficulty with this
definition is that even if a meaning for $T_1$ is agreed to, there may
be insufficient memory on a single node to store an entire large
problem.  Thus in many cases it may be impossible to measure $T_1$
using this definition.

One principal objective in the field of performance analysis is
benchmarking: to compare the performance of different computers.  It
is generally agreed that the best performance corresponds to the least
wall-clock execution time.  In order to adapt the speedup statistic
for benchmarking, it is thus necessary to define a single reference
value of $T_1$ to be used for all calculations.  It does not matter
how $T_1$ is defined, or what its value is, only that the same value
of $T_1$ is used to calculate all speedup values used in the
comparison.

However, defining $T_1$ as a reference time unrelated to the parallel
computer being benchmarked unfortunately has the consequence that many
properties that many people regard as essential to the concept of
parallel speedup are lost:

\begin{enumerate}

\item It is no longer necessarily 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 figures computed as speedup
divided by $p$ are no longer a meaningful measure of processor
utilization.

\end{enumerate}

There are other difficulties with this formulation of speedup.  If we
use $T_1$ as the run time on a very fast single processor (currently,
say, a Cray C90 or a NEC SX-3), then manufacturers of highly parallel
systems will be reluctant to quote the speedup of their system in the
above way.  For example, if the speedup of a 100 processor parallel
system over a single node of the same system is a respectable factor
of 80, it is likely that the speedup computed from the ``standard''
$T_1$ would be reduced to 10 or less.  This is because a fast vector
processor is typically at least ten times faster than the RISC
processors used in many highly parallel systems of a comparable
generation.

Thus it appears that if one sharpens the definition of speedup to make
it an acceptable metric for comparing the performance of different
computers, one has to throw away the main properties that have made
the concept of speedup useful in the past.  

Accordingly, the ParkBench committee has decided the following [DHB's
suggestion]:

\begin{enumerate}

\item No speedup statistic will be kept in the ParkBench database.

\item Speedup statistics based on ParkBench benchmarks must never be
used as figures of merit when comparing the performance of different
systems.  We further recommend that speedup figures based on other
benchmarks not be used as figures of merit in such comparisons.

\item Speedup statistics may be used in a study of the performance
characteristics of an individual parallel system.  But the basis for
the determination of $T_1$ must be clearly and explicitly stated.

\item The value of $T_1$ should be based on an efficient uniprocessor
implementation.  Code for message passing, synchronization, etc.
should not be present.  The author should also make a reasonable
effort to insure that the algorithm used in the uniprocessor
implementation is the best practical serial algorithm for this
purpose.

\item Given that a large problem frequently does not fit on a single
node, it is permissible to cite speedup statistics based on the timing
of a smaller number of nodes.  In other words, it is permissible to
compute speedup as $T_p / T_m$, for some $m, \; 1 < m < p$.  If this
is done, however, this usage must be clearly stated, and full details
of the basis of this calculation must be presented.  As above, care
must be taken to insure that the unit timing $T_m$ is based on an
efficient implementation of appropriate algorithms.

\end{enumerate}

\section{Performance Database}

\begin{verbatim}
It was agreed that this subsection be redrafted by Jack Dongarra.

- --------------------------  START OLD TEXT  ---------------------------------
\end{verbatim}

\input{pds.tex}

\begin{verbatim}
- ---------------------------  END OLD TEXT  ---------------------------------

- ----------------------  SOME PROPOSED NEW TEXT  ----------------------------
\end{verbatim}

At present each benchmark measurement for a particular problem size $N$ and
processor number $p$, is represented by one line in the database with
variable length fields chosen by the benchmark writer as suitable and 
comprehensive to describe the conditions of the benchmark run. The fields
separated by a marker include, benchmarkers name and e-mail, computer 
location and date, hardware specification, compiler date and optimisation 
level, $N$, $p$, $T(N,p)$, $R_B(N,P)$ and other metrics as deemed appropriate
by the benchmark writer. Ideally, the line for the database would be 
produced automatically as output by the benchmark program itself.

\begin{verbatim}
- ----------------------  END PROPOSED NEW TEXT  ----------------------------
\end{verbatim}

\section{Interactive Graphical Interface}

The Southampton Group has agreed to provide an interactive graphical front 
end to the ParkBench~ database of performance results. To achieve this,
the basic data held in the Performance Data Base should be values of
$T(N;p)$ for at least 4 values of problem size $N$, each for sufficient
$p$-values (say 5 to 10) to determine the trend of variation of performance
with number of processors for constant problem size. It is important that
there be enough $p$-values to see Amdahl saturation, if present, or any 
peak in performance followed by degradation. A graphical interface is
really essential to allow this multidimensional data to be viewed in any
of the metrics defined above, as chosen interactively by the user.
The user could also be offered (by suitable interpolation) a display of 
the results in various scaled metrics, in which the problem size is 
expanded with the number of processors.

In order to encompass as wide a range of performance and number of 
processors as possible, a log-scale on both axes is unavoidable, and
the format and scale range should be kept fixed as long as possible
to enable easy comparison between graphs. A three-cycle by three-cycle
log-log graph with range 1 to 1000 in both $p$ and Mflop/s would cover
most needs in the immediate future. Examples of such graphs are to be
found in \cite{Hoc92,Add93}. 

A log/log graph is also desirable because the size and shape of the Amdahl 
saturation curve is the same wherever it is plotted on such a graph. 
That is to say there is a universal Amdahl curve that is invariant to 
its position on any log/log graph. Amdahl saturation is a two-parameter 
description of any of the performance metrics, $R$, as a function of $p$ 
for fixed $N$, which can be expressed by
\begin{equation}
                   R = \frac{R_\infty}{(1 + \phalf/p)}
\end{equation}
where $R_\infty$ is the saturation performance approached as $p \rightarrow 
\infty$ and \phalf is the number of processors required to reach half
the saturation performance. The graphical interface should allow this
universal Amdahl curve to be moved around the graphical display, and
be matched against the performance curves. The changing values of the two 
parameters \Rphalf should be displayed as the Amdahl curve is moved.

As more experience is gained with performance analysis, that is to say
the fitting of performance data to parametrised formulae, it is to be
expected that the graphical interface will allow more complicated formulae
to be compared with the experimental data, perhaps allowing 3 to 5
parameters in the theoretical formula. But, as yet, we do not know what
these for parametrised formula should be.

\section{Benchmarking Procedure and Code Optimisation}

Manufacturers will always feel that any benchmark not tuned specifically
by themselves, is an unfair test of their hardware and software. This is
inevitable and from their viewpoint it is true. NASA have overcome this 
problem by only specifying the problems (the NAS paper-and-pencil 
benchmarks \cite{naspar2}) and leaving the manufacturers to write the 
code, but in many circumstances this would require unjustifiable effort
and take too long. It is also a perfectly valid question to ask how a
particular parallel computer will perform on existing parallel code, and
that is the viewpoint of ParkBench. 

The benchmarking procedure is to run the distributed ParkBench~ suite on
an 'as-is' basis, making only such non-substantive changes that are required 
to make the code run (e.g. changing the names of header files to a local
variant). The as-is run may use the highest level of automatic compiler
optimisation that works, but the level used and compiler date should be
noted in the appropriate section of the performance database entry.      

After completing the as-is run, which gives a base-line result, any form of 
optimisation may be applied to show the particular computer to its best 
advantage, up to completely rethinking the algorithm, and rewriting
the code. The only requirement on the benchmarker is to state what has been
done. However, remember that, even if the algorithm is changed, the official
flop-count, $F_B(N)$ that is used in the calculation of nominal benchmark
Mflop/s, $R_B(N,p)$, does not. In this way a better algorithm will show up
with a higher $R_B$, as we would want it to, even though the hardware 
Mflop/s is likely to be little changed.

Typical steps in optimisation might be:
\begin{enumerate} 
\item explore the effect of different compiler optimisations on a single 
      processor, and choose the best for the as-is run.
\item perform the as-is run on multiple processors, using enough values 
      of $p$ to determine any peak in performance or saturation.
\item return to single processor and optimise code for vectorisation,
      if a vector processor is being used. This means restructuring loops 
      to permit vectorisation.
\item continue by replacement of selected loops with optimal assembly coded 
      library routines (e.g. BLAS where appropriate).
\item replacement of whole benchmark by a tuned library routine with the
      same functionality.
\item replace whole benchmark with locally written version with the same 
      functionality but using possibly an entirely different algorithm 
      that is more suited to the architecture.
\end{enumerate} 
% ----------------------------------------------------------------------------

------- End of Forwarded Message