Subject: Methodology Chapter 2 contribution

From: Prof Roger Hockney <[email-masked]>
Date: Wed, 24 Mar 93 12:42:43 GMT

This is my first draft of a proposed Chapter2 for your comments
and amalgamation with contributions from other members of the
subcommittee. Please let me have your Comments, particularly
any parts that you cannot accept (I hope none, however), so that
I may edit it. I particularly wish to hear from our leader, David.
             Best regards   Roger Hockney.
You should be able to print it using LATEX, and the files benrep1.tex
benref1.bib sent to pbwg-comm alredy.
\chapter{Methodology}

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 megaflops (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 or Simulation 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}

The fundamental measurement made in any benchmark is the 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 (here 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.

\medskip
New symbols and units: 
\begin{enumerate}
\item flop : number of floating-point operations
\item mref : number of memory references (reads or writes)
\item barr : number of barrier operations
\item b    : number of binary digits (bits)
\item B    : number of bytes (groups of 8 bits)
\item ${\rm w}_{32}$ : number of words (number of bits per word as 
             subscript, here 32).
\end{enumerate}
Note that flop and mref are both inseparable four-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.

\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 ${\rm M}_2$    : binary mega $1024^2$
\item ${\rm G}_2$    : binary giga $1024^3$
\item ${\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 {\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 for this purpose.  

\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 \\
{\sc IF(X .REL. Y)}		& 1 flop \\
\end{tabular}
\end{table}

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)$, which may be 
greater than the nominal benchmark count, due to the distributed version 
performing redundant arithmetic operations.

\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)/{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}

We do not favour the use of any of the popular performance metrics: 
speedup, efficiency or performance per node; because all these are 
either easily misinterpreted or obscure important effects. 
The speedup of a benchmark code 
is defined as the ratio of the $p$-processor temporal performance to the 
single-processor temporal performance. It is a very useful and convenient 
measure if we are concerned with the optimisation of a particular code in 
isolation, because its value can easily be compared with the maximum possible 
speedup, namely the number of processors being used. We can thereby assess
how much of the potential hardware performance is being utilised. However
benchmarking is to do with comparing the performance of different computers,  
and all the above three metrics are unsuitable for this purpose.

Speedup compares the performance of a code with itself, and might therefore 
be called an introspective, or even incestuous measure. Problems can therefore 
arise (see below), and incorrect conclusions can be drawn, if we try to use 
speedup to compare different algorithms on the same computer, or the same 
algorithm on different computers. This is because speedup is a relative 
measure (it is defined as the ratio of two performances), and therefore all 
knowledge of the absolute performance has been lost. 
Benchmarking, however, is concerned with the comparison of the absolute 
performance of computers, and therefore the use of a relative measure like
speedup is not very useful, and can be positively misleading.  
For example, we do not wish to conclude that a computer with a large number of
slow processors and therefore high value of speedup, is faster than another 
with fewer processors and therefore with a lower speedup, if in fact the 
reverse is the case, because the processors on the second computer are so much 
faster. Only by adopting absolute measures of performance with physical units 
involving inverse time, can one avoid this type of false conclusion.

Speedup is not even useful for comparing the performance of one algorithm with 
another on the same computer, because it is not necessarily true that the 
algorithm with the highest speedup executes in the least time (see, e.g. 
~\cite{Cvet90}). One can only be sure that this is the case if the 
single-processor temporal performance of both algorithms is the same, which 
is most unlikely. If the single-processor performances of the two algorithms 
are different and we compare the speedups of the two algorithms, then we are 
comparing the performance of the two algorithms measured in different units.
This is like comparing the speeds of two cars, one measured in m.p.h. and the
other in cm/s. Such a comparison has no validity either for cars or 
algorithms. Computers and algorithms can only safely be compared in terms
of their absolute performance in solving a problem. The most unambiguous
measure is the temporal performance, which is the inverse of 
the time of execution, or the related simulation performance. 

The benchmark performance per node might seem to be an attractive 
metric because it is an absolute measure which
can be related directly to the hardware performance of node. However
it has the major defect that it hides the point at which the absolute 
performance begins to decrease as the number of processors increases. If we
plot benchmark performance against number of processors, this point is
clearly visible as a maximum, however if the same data is plotted as
performance per node, all we see is a very uninteresting monotonically 
falling line, and the important maximum has disappeared. The efficiency, 
which is defined as the speedup divided by the number of processors, is 
doubly condemned because it is a relative measure and hides the maximum.

\section{Performance Database}

The database of benchmark performance results should be based on an
extension of the excellent X-window display demonstrated by Jack Dongarra
at the March 1993 PBWG meeting. The basic data held would 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}.

% ----------------------------------------------------------------------------