Subject: Parkbench Report

From: [email-masked]
Date: Wed, 18 Aug 93 15:27:54 GMT

UNITS.TEX and revised BENCOM1.TEX and LOWLEV2.TEX
        -------------------------------------------------

Appended are an update to the units section (units.tex) to use as a
replacement within the methodology chapter (method4.tex). This requires 
further additions to the latex command file (bencom1.tex), which should
be replaced with the new one here. 

Also supplied is the third draft of the lowlevel chapter (lowlev2.tex).

                      Roger Hockney, 18 Aug 1993

%------------------------------------------------------------------------
%      PARKBENCH REPORT (third draft), File:        units.tex
%      Replace the whole \section{Units and Symbols} in method4.tex by
%      the following:
%------------------------------------------------------------------------

\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 \msend: message send operation [latex \verb1\1msend]
\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 ${\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 to mean 'per'.  

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

%------------------------------------------------------------------------
%      PARKBENCH REPORT (third draft), File:        bencom1.tex
%------------------------------------------------------------------------
%
%        **************************************************************
%                      LATEX COMMANDS FOR PARKBENCH REPORTS
%        **************************************************************
%
\def\pipe{\mathop{\rm pipe}\nolimits}
\newcommand{\Parkbench}{\mbox{\sc PARKBENCH}}
\newcommand{\Suprenum}{\mbox{\sc SUPRENUM}}
\newcommand{\flop}{\mbox{\rm flop}}
\newcommand{\inst}{\mbox{\rm inst}}
\newcommand{\inop}{\mbox{\rm intop}}
\newcommand{\vecop}{\mbox{\rm vecop}}
\newcommand{\msend}{\mbox{\rm msend}}
\newcommand{\iter}{\mbox{\rm iter}}
\newcommand{\mref}{\mbox{\rm mref}}
\newcommand{\barr}{\mbox{\rm barr}}
\newcommand{\bit}{\mbox{\rm b}}
\newcommand{\B}{\mbox{\rm B}}
\newcommand{\sol}{\mbox{\rm sol}}
\newcommand{\w}{\mbox{\rm w}}
\newcommand{\usec}{\mbox{\rm $\mu$s}}
\newcommand{\where}{\mbox{\rm where}}
\newcommand{\rmand}{\mbox{\rm and}}
\newcommand{\Mflops}{\mbox{\rm Mflop/s}}
\newcommand{\flops}{\mbox{\rm flop/s}}
\newcommand{\flopB}{\mbox{\rm flop/B}}
\newcommand{\tstepps}{\mbox{\rm tstep/s}}
\newcommand{\Mwps}{\mbox{\rm Mw/s}}
\newcommand{\spone}{\mbox{\ }}
\newcommand{\sptwo}{\mbox{\ \ }}
\newcommand{\spfour}{\mbox{\ \ \ \ }}
\newcommand{\spsix}{\mbox{\ \ \ \ \ \ }}
\newcommand{\speight}{\mbox{\ \ \ \ \ \ \ \ }}
\newcommand{\spten}{\mbox{\ \ \ \ \ \ \ \ \ \ }}
\newcommand{\rinf}{\mbox{$r_\infty$}}
\newcommand{\Rinf}{\mbox{$R_\infty$}}
\newcommand{\nhalf}{\mbox{$n_{\frac{1}{2}}$}}
\newcommand{\fhalf}{\mbox{$f_{\frac{1}{2}}$}}
\newcommand{\Nhalf}{\mbox{$N_{\frac{1}{2}}$}}
\newcommand{\phalf}{\mbox{$p_{\frac{1}{2}}$}}
\newcommand{\Phalf}{\mbox{$P_{\frac{1}{2}}$}}
\newcommand{\rhat}{\mbox{$\hat{r}$}}
\newcommand{\half}{\mbox{$\frac{1}{2}$}}
\newcommand{\rnhalf}{\mbox{(\rinf,\nhalf)}}
\newcommand{\rfhalf}{\mbox{(\rhat,\fhalf)}}
\newcommand{\RNhalf}{\mbox{(\Rinf,\Nhalf)}}
\newcommand{\Rphalf}{\mbox{(\Rinf,\phalf)}}
\newcommand{\third}{\mbox{$\frac{1}{3}$}}
\newcommand{\quart}{\mbox{$\frac{1}{4}$}}
\newcommand{\eighth}{\mbox{$\frac{1}{8}$}}
\newcommand{\nineth}{\mbox{$\frac{1}{9}$}}

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

%------------------------------------------------------------------------
%      PARKBENCH REPORT (third draft), File:        lowlev2.tex
%------------------------------------------------------------------------
%file: lowlev2.tex
\chapter{Low-Level Benchmarks}
\footnote{assembled by Roger Hockney for low-level subcommittee}

\section{Introduction}

The first step in the assessment of the performance of a massively
parallel computer system is to measure the performance of a single
processing node of the multi-node system. There exist already many
good and well-established benchmarks for this purpose, notably the
LINPACK benchmarks and the Livermore Loops. These are not part of
the \Parkbench suite of programs, but \Parkbench recommends that 
these be used to measure single-node performance, in addition to
some specific low-level measurements of its own (see section 
\ref{oneproc}). There follows a brief description of existing 
benchmarks that are recommended for measuring single-node 
performance, with a discussion of their value. 

\subsection{Most Reported Benchmark: LINPACKD (n=100)}

This well-known standard benchmark is a Fortran program
for the solution of (100x100) dense set of linear equations by
Gaussian elimination. It is distributed by Dr J. J. Dongarra of
the University of Tennessee. The results are quoted in Mflop/s
and are regularly published and available by electronic mail.
The main value of this benchmark is that results are known for 
more computers than any other benchmark. Most of the compute time 
is contained in vectorisable DO-loops such as the DAXPY (scalar 
times vector plus vector) and inner product. Therefore one expects 
vector computers to perform well on this benchmark. The weakness 
of the benchmark is that it tests only a small number of vector 
operations, but it does include the effect of memory access and
it is solving a complete (although small) real problem. 

\subsection{Performance Range: The Livermore Loops}

These are a set of 24 Fortran DO-loops (The Livermore Fortran Kernels, LFK)
extracted from operational codes used at the Lawrence Livermore 
National Laboratory \cite{Ma88}. They have been used since the early 
seventies to assess the arithmetic performance of computers and their 
compilers. They are a mixture of vectorisable and non-vectorisable
loops and test rather fully the computational capabilities of the
hardware, and the skill of the software in compiling efficient code,
and in vectorisation. The main value of the benchmark is the range
of performance that it demonstrates, and in this respect it 
complements the limited range of loops tested in the LINPACK benchmark. 
The benchmark provides the individual performance of each loop,
together with various averages (arithmetic, geometric, harmonic)
and the quartiles of the distribution. However, it is difficult to
give a clear meaning to these averages, and the value of the benchmark
is more in the distribution itself.  In particular, the maximum and
minimum give the range of likely performance in full applications.
The ratio of maximum to minimum performance has been called the
{\em instability} or the {\em speciality} ~\cite{Hoc91}, and is a measure 
of how difficult it is to obtain good performance from the computer,
and therefore how specialised it is. The minimum or worst performance
obtained on these loops is of special value, because there is much
truth in the saying that "the best computer to choose is that with 
the best worst-performance". 

\section{\label{oneproc}Single-Processor Benchmarks}

The single-processor low-level benchmarks provided by \Parkbench, aim to 
measure performance parameters that characterise the basic architecture of 
the computer, and the compiler software through which it is used. For this
reason, such benchmarks have also been called appropriately 'basic 
architectural benchmarks'. Following the methodology of Euroben~\cite{FGHS89},
the aim is that these hardware/compiler parameters will be used in performance 
formulae that predict the timing and performance of the more complex kernels 
(see Chapter~\ref{kernel}) and compact applications (see Chapter 
~\ref{compact}). They are therefore a set of 'synthetic' benchmarks contrived 
to measure theoretical parameters that describe the severity of some overhead
or potential bottleneck, or the properties of some item of hardware. Thus 
RINF1 characterises the basic properties of the arithmetic pipelines by 
measuring the parameter \rnhalf, and POLY1 and POLY2 characterise the severity
of the memory bottleneck by measuring the parameters \rfhalf.   

The fundamental measurement in any benchmarking is the measurement of elapsed
wall-clock time. Because the computer clocks on each node of a multi-node MPP 
are not synchronised, all benchmark time measurements must be made with a 
single clock on one node of the system. The benchmarks TICK1 and TICK2 have, 
respectively, been designed to measure the resolution and check the absolute 
value of this clock. These benchmarks should be run with satisfactory results 
before any further benchmark mreasurements are made.

\subsection{Timer resolution: TICK1}

TICK1 measures the interval between ticks of the clock being used
in the benchmark measurements. That is to say the resolution of
the clock. A succession of calls to the timer routine are inserted
in a loop and executed many times. The differences between successive
values given by the timer are then examined.  If the changes in the
clock value (or ticks) occur less frequently than the time taken to 
enter and leave the timer routine, then most of these differences
will be zero. When a tick takes place, however, a difference equal 
to the tick value will be recorded, surrounded by many zero differences. 
This is the case with clocks of poor resolution, for example most UNIX 
clocks that tick typically every 10 ms. Such poor UNIX clocks can still
be used for low-level benchmark measurements if the benchmark is
repeated, say, 10,000 times, and the timer calls are made outside this 
repeat loop.  

With some computers, such as the
CRAY series, the clock ticks every cycle of the computer, that is to say
every 6ns on the Y-MP. The resolution of the CRAY clock is therefore
approximately one million times better than a UNIX clock, and that is
quite a difference! If TICK1 is used on such a computer the difference
between successive values of the timer is a very accurate measure of
how long it takes to execute the instructions of the timer routine, and
therefore is never zero. TICK1 takes the minimum of all such differences,
and all it is possible to say is that the clock tick is less than or
equal to this value. Typically this minimum will be several hundreds
of clock ticks. With a clock ticking every computer cycle, we can make
low-level benchmark measurements without a repeat loop. Such measurements
can even be made on a busy timeshared system (where many users are
contending for memory access) by taking the minumum time recorded from
a sample of, say, 10,000 single execution measurements. In this case,
the minimum can usually be said to apply to a case when there was no
memory access delay caused by other users.

TICK1 exists and forms part of the Genesis benchmarks ~\cite{Hey91}.

\subsection{Timer value: TICK2}

TICK2 confirms that correctness of the time values returned by the
computer clock, by comparing its measurement of a given time interval
with that of an external wall-clock (actually the benchmarker's 
wristwatch). Parallel benchmark performance can only be measured
using the elapsed wall-clock time, because the objective of
parallel execution is to reduce this time. Measurements made with a
CPU-timer (which only records time when its job is executing in the CPU) 
are clearly incorrect, because the clock does not record waiting time 
when the job is out of the CPU. TICK2 will immediately detect the 
incorrect use of a CPU-time-for-this-job-only clock. An example
of a timer that claims to measure elapsed time but is actually a
CPU-timer, is the returned value of the popular Sun UNIX timer ETIME. 
TICK2 also checks that the correct multiplier is being used in the 
computer system software to convert clock ticks to true seconds.  

TICK2 exists and will form part of the next release of the Genesis 
benchmarks ~\cite{Hey91}.

\subsection{Basic Arithmetic Operations: RINF1}

This benchmark takes a set of common Fortran DO-loops and analyses
their time of execution in terms of the two parameters \rnhalf
~\cite{Hoc77,HoJe81,Hoc82,Hoc83,Hoc87,HoJe88}. \rinf is the 
asymptotic performance rate in Mflop/s which 
is approached as the loop (or vector) length ,$n$, becomes longer. \nhalf 
(the half-performance length) expresses how rapidly, in terms
increasing vector length, the actual performance, $r$, approaches \rinf. 
It is defined as the vector length required to achieve a performance 
of one half of \rinf. This means that the time, $t$, for a DO-loop
corresponding to $q$ vector operations (i.e. with $q$ floating-point 
operations per element per iteration) is approximated by:
\begin{equation}
                  t = q * ( n + \nhalf ) / \rinf          \label{Eqn1}
\end{equation}      
         Then the performance rate is given by
\begin{equation}
        r =  \frac{q*n}{t} = \frac{\rinf}{(1+\nhalf /n)}   \label{Eqn2}
\end{equation}                                        
We can see from Eqn.(\ref{Eqn1}) that \nhalf is a way of measuring the
importance of vector startup overhead (=\nhalf/\rinf) in terms
of quantities known to the programmer (loop or vector length).
In the benchmark program, the two parameters are determined by a
least-squares fit of the data to the straight line defined by 
Eqn.(\ref{Eqn1}). A useful guide to the significance of \nhalf is to note
from Eqn.(\ref{Eqn2}) that 80 percent of the asymptotic performance is
achieved for vectors of length $4 \times \nhalf$. Generally speaking, 
\nhalf values of upto about 50 are tolerable, whereas the performance
of computers with larger values of \nhalf is severely constrained
by the need to keep vector lengths significantly longer than \nhalf.
This requirement makes the computers difficult to program efficiently,
and often leads to disappointing performance, compared to the
asymptotic rate advertised by the manufacturer.  

RINF1 exists as part of the Hockney and Genesis benchmarks ~\cite{Hey91}. 
An independently written version forms module MOD1AC of the EuroBen
benchmarks ~\cite{StRi93}.

\subsection{Memory-Bottleneck Benchmarks: POLY1 and POLY2}

Even if the vector lengths are long enough to overcome the vector 
startup overhead, the peak rate of the arithmetic pipelines may not
be realised because of the delays associated with obtaining data from 
the cache or main memory of the computer. The POLY1 and POLY2 benchmarks 
quantify this dependence of computer performance on memory access
bottlenecks. The computational intensity, $f$, of a DO-loop is defined 
as the number of floating-point operations (flop) performed per memory 
reference (mref) to an element of a vector variable ~\cite{HoJe88}. 
The asymptotic performance, \rinf, of a computer is observed to increase 
as the computational intensity increases, because as this becomes 
larger, the effects of memory access delays become negligible
compared to the time spent on arithmetic. This effect is characterised
by the two parameters (\rhat,\fhalf), where \rhat~ is the peak hardware
performance of the arithmetic pipeline, and \fhalf is the computational
intensity required to achieve half this rate. That is to say the
asymptotic performance is given by:
\begin{equation}
              \rinf = \frac{\rhat}{(1+\fhalf/f)}          \label{Eqn3}
\end{equation}                                        
If memory access and arithmetic are not overlapped, then \fhalf can
be shown to be the ratio of arithmetic speed (in Mflop/s) to memory
access speed (in Mword/s). The parameter \fhalf, like \nhalf, measures 
an unwanted overhead and should be as small as possible. In order to vary 
$f$ and allow the peak performance to be approached, we choose a kernel 
loop that can be computed with maximum efficiency on any hardware. This 
is the evaluation of a polynomial by Horner's rule, in which case the
computational intensity is the order of the polynomial, and both the
multiply and add pipelines can be used in parallel. To measure \fhalf, 
the order of the polynomial is increased from one to ten, and the measured 
performance for long vectors is fitted to Eqn.(\ref{Eqn3}).

The POLY1 benchmark repeats the polynomial evaluation for each order
typically 1000 times for vector lengths upto 10,000, which would 
normally fit into the cache of a cache-based processor. Except for 
the first evaluation the data will therefore be found in the cache. 
POLY1 is therefore an {\em in-cache} test of the memory bottleneck 
between the arithmetic registers of the processor and its cache. 

POLY2, on the other hand, flushes the cache prior to each different
order and then performs only one polynomial evaluation,
for vector lengths from 10,000 upto 100,000, which would normally
exceed the cache size. Data will have to be brought from off-chip
memory, and POLY2 is an {\em out-of-cache} test of the memory
bottleneck between off-chip memory and the arithmetic registers.

The POLY1 benchmark exists as MOD1G of the EuroBen benchmarks 
~cite{StRi93}. POLY2 exists as part of the Hockney benchmarks.

\section{Multi-Processor Benchmarks}

The \Parkbench suite of benchmark programs provide low-level benchmarks
to characterise the basic communication properties of an MPP by measuring 
the parameters \rnhalf for communication (COMMS1, COMMS2, COMMS3). The
ratio of arithmetic speed to communication speed (the hardware/compiler
parameter \fhalf for communication) is measured by the POLY3 benchmark.
The ability to synchronise the processors in a large MPP, in an acceptable
time, is a key characteristic of such computers, and the SYNCH1 benchmark
measures the number of barrier statements that can be executed per second
as a function of the number of processors taking part in the barrier.

\subsection{Communication Benchmarks: COMMS1 and COMMS2}

The purpose of the COMMS1, or {\em Pingpong}, benchmark \cite{Hoc88,Hoc91} 
is to measure the basic communication properties of a message-passing MIMD 
computer. A message of variable length, $n$, is sent from a master node to 
a slave node. The slave node receives the message into a Fortran data array, 
and immediately returns it to the master. Half the time for this `message 
pingpong' is recorded as the time, $t$, to send a message of length, $n$.  
In the COMMS2 benchmark there is a message exchange in which two nodes 
simultaneously send messages to each other and return them. In this case
advantage can be taken of bidirectional links, and a greater bandwidth
can be obtained than is possible with COMMS1. In both benchmarks, the time 
as a function of message length is fitted by least squares using the 
parameters \rnhalf \cite{Hoc82,HoJe88} to the following linear timing model:
\begin{equation}
                     t = (n + \nhalf)/\rinf            \label{Eqn(4.1)}
\end{equation}
when the communication rate is given by
\begin{equation}
    r = \frac {\rinf}{1+\nhalf/n} = \rinf \pipe (n/\nhalf) \label{Eqn(4.2)}
\end{equation}
\begin{equation}
\where \spten   \pipe (x) = \frac {1}{1 + 1/x}
\end{equation}
and the startup time is
\begin{equation}
                     t_0 = \nhalf/\rinf                \label{Eqn(4.3)}
\end{equation}
In the above equations, \rinf is the {\em asymptotic bandwidth} of 
communication which is approached as the message length tends to infinity 
(hence the subscript), and \nhalf is the message length required to achieve 
half this asymptotic rate. Hence \nhalf is called the {\em half-performance
message length}. 

The importance of the parameter \nhalf is that it provides a yardstick with
which to measure message-length, and thereby enables one to distinquish 
the two regimes of short and long messages. For long messages $(n > \nhalf)$, 
the denominator in equation \ref{Eqn(4.2)} is approximately unity and the 
communication rate is approximately constant at its asymptotic rate, \rinf 
\begin{equation}
                   r \approx \rinf                    \label{Eqn(4.3.5)}
\end{equation} 
For short messages $(n < \nhalf)$, the communication rate is best 
expressed in the algebraically equivalent form
\begin{equation}
                 r = \frac {\pi_0 n} {(1+ n/ \nhalf)}   \label{Eqn(4.4)}
\end{equation}
\begin{equation}
\where \spten     \pi_0 = t_0 ^{-1} = \rinf/\nhalf      \label{Eqn(4.5)}
\end{equation} 
For short messages, the denominator in equation \ref{Eqn(4.4)} is 
approximately unity, so that
\begin{equation}
                 r \approx \pi_0 n = n / t_0            \label{Eqn(4.6)}
\end{equation}
In sharp contrast to the approximately constant rate in the long-message 
limit, the communication rate in the short message limit is seen to be 
approximately proportional to the message length. The constant of 
proportionality, $\pi_0$, is known as the {\em specific performance}, and 
can be expressed conveniently in units of kilobyte per second per byte 
(kB/s)/B or k/s. 

Thus, in general, we may say that \rinf characterises the long-message 
performance and $\pi_0$ the short-message performance. The COMMS1 benchmark 
computes all four of the above parameters, 
$(\rinf, \nhalf, t_0, \rmand \pi_0)$,
because each emphasises a different aspect of performance. However only 
two of them are independent. In the case that there are different modes
of transmission for messages shorter or longer than a certain length, the
benchmark can read in this breakpoint and perform a separate least-squares 
fit for the two regions. An example is the Intel iPSC/860 which has a different
message protocol for messages shorter than and longer than 100 byte. 

Because of the finite (and often large) value 
of $t_0$, the above is a {\em two-parameter} description of communication 
performance. It is therefore incorrect, and sometimes positively misleading,
to quote only one of the parameters (e.g. just \rinf, as is often done) to
describe the performance. The most useful pairs of parameters are \rnhalf
$(\pi_0,\nhalf)$ and $(t_0,\rinf)$, depending on whether one is concerned
with long vectors, short vectors or a direct comparison with hardware times. 
Note also that, although \nhalf is defined
as the  message length required to obtain half the asymptotic rate \rinf,
the two parameters \rnhalf are sufficient to calculate the communication rate 
for any message length via equation \ref{Eqn(4.2)}, or equivalently using 
$\pi_0$ instead of \rinf via \ref{Eqn(4.4)}.

The COMMS1 and COMMS2 benchmarks exist as part if the Genesis benchmarks
~\cite{Hey91}.

\subsection{Total Saturation Bandwidth: COMMS3}

To complement the above communication benchmarks, there is a need for
a benchmark to measure the total saturation bandwidth of the complete
communication system, and to see how this scales with the number
of processors. A natural generalisation of the COMMS2 benchmark
could be made as follows, and be called the COMMS3 benchmark:
Each processor of a $p$-processor system sends a message of length $n$
to the other $(p-1)$ processors. Each processor then waits to receive
the $(p-1)$ messages directed at it. The timing of this generalised
'pingping' ends when all messages have been sucessfully received by all
processors; although the process will be repeated many times to obtain
an accurate measurement, and the overall time will be divided by the
number of repeats. The time for the generalised pingping is the time to
send $p(p-1)$ messages of length $n$ and can be analysed in the same way
as COMMS1 and COMMS2 into values of \rnhalf. The value obtained for \rinf
is the required total saturation bandwidth, and we are interested in how
this scales up as the number of processors $p$ increases and with it the
number of available links in the system.

This benchmark does not exist, but Roger Hockney will develop a trial
version for the Intel iPSC, followed by PARMACS and PVM. Perhaps suitable 
and better benchmarks exist elsewhere. Please send in your suggestions.

\subsection{Communication Bottleneck: POLY3}

POLY3 assesses the severity of the communication bottleneck.
It is the same as the POLY1 benchmark except that the data for the
polynomial evaluation is stored on a neighbouring processor. The value of
\fhalf obtained therefore measures the ratio of arithmetic to communication
performance. Equation ~\ref{Eqn3} shows that the computational intensity 
of the calculation must be significantly greater than \fhalf (say 4 times
greater) if communication is not to be a bottleneck. In this case
the computational intensity is the ratio of arithmetic performed on a
processor to words tranferred to/from it over communication links.
In the common case that the amount of arithmetic is proportional to
the volume of a region, and the data communicated is proportional to
the surface of the region, the computational intensity is increased as
the size of the region (or granularity of the decomposition) is increased. 
Then the \fhalf obtained from this benchmark is directly related 
to the granularity that is required to make communication time unimportant.

The POLY3 benchmark does not exist, although native versions have been
used on transputer systems ~\cite{Hoc91}. A trial benchmark will be 
prepared for Intel iPSC computers by Roger Hockney, followed by PARMACS 
and PVM versions.

\subsection{Synchronisation Benchmarks: SYNCH1}

SYNCH1 measures the time to execute a barrier synchronisation statement
as a function of the number of processes taking part in the barrier.
The practicability of massively parallel computation with thousands
or tens of thousands of processors depends on this barrier time not
increasing too fast with the number of processors. The results are quoted
both as a barrier time, and as the number of barrier statements
executed per second (barr/s).

The SYNCH1 benchmark exists as part of Genesis v2.1.1 ~\cite{Hey91}.

\begin{verbatim}
--------------------------------------------------------------------------
------------------------  END CHAPTER-3  ---------------------------------
--------------------------------------------------------------------------
--------------------------------------------------------------------------
------------------------  START APPENDIX  --------------------------------
--------------------------------------------------------------------------
According to the wishes of the Parkbench committee, the following sections
may be either omitted completely in the final report, or relegated to an
Appendix. Their purpose is to state the current status of the low-level
benchmarks, and to give some examples of measurements as an aid to judging
the value of the benchmarks. 
--------------------------------------------------------------------------
-------------------------   END APPENDIX  --------------------------------
--------------------------------------------------------------------------
\end{verbatim}

\section{Appendix}

\subsection{Summary of Benchmark Status}

The following Table-\ref{Table3} summarises the current state of the 
proposed low-level benchmarks, and the properties they are intended
to measure.

\begin{table}
\centering
{\small
\parbox{5in}{
\caption{\label{Table3}
          Status of proposed Low-Level benchmarks. Note we abbreviate
          performance (perf.), arithmetic (arith.), communication (comms.),
          operations (ops.).}}
\begin{tabular}{llcccc}
\hline
Benchmark       & Measures             & Parameters & Exists &  Author     \\
                &                      &            &        &             \\
\hline
SINGLE-PROCESSOR                                                           \\
   TICK1        & Timer resolution     & tick interval & Genesis & Hockney \\
   TICK2        & Timer value          & wall-clock check& Genesis & Hockney \\
   RINF1        & Basic Arith. ops.    & \rnhalf    & Genesis & Hockney \\
   POLY1        & Cache-bottleneck     & \rfhalf    & EuroBen & Hockney \\
   POLY2        & Memory-bottleneck    & \rfhalf    & Hockney & Hockney \\
   SYNCH1       & Barrier time & rate  & \barr/s    & Hockney & Hockney \\
\hline
MULTI-PROCESSOR                                                         \\
   COMMS1       & Basic Message perf.  & \rnhalf    & Genesis & Hockney \\
   COMMS2       & Message exch. perf.  & \rnhalf    & Genesis & Hockney \\
   COMMS3       & Saturation Bandwidth & \rnhalf    & No      & Hockney \\
   POLY3        & Comms. Bottleneck    & \rfhalf    & No      & Hockney \\
\hline

\end{tabular}
}
\end{table}

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

\subsection{Arithmetic Benchmark Results}

As an indication of the type of results given by the proposed low-level
arithmetic benchmarks, Table-\ref{Table1} gives measurements made on a 
number of workstations, and microprocessor chips that are used as 
processing nodes in multiprocessor MIMD computers. 

\begin{table}
\centering
{\small
\parbox{5in}{\caption{\label{Table1}
Performance of some common numerical benchmarks on some common workstations 
and microprocessor chips used in MIMD computers. Measurements were made with 
the highest level of optimisation that ran, and are in Mflop/s for 64-bit 
precision, except where stated in parentheses. The units of \nhalf are vector 
length, and \fhalf are flop/mref (floating-point operations per memory 
reference). Results are for the best generally available compiler on the 
date shown. Those for the i860 are for the first Greenhills compiler which 
is known not to use many important i860 hardware features. 
Later more advanced compilers should give significantly better results.  
}}
\begin{tabular}{lccccccc}
\hline
               &Sun   &Solbourne&Stardent&Inmos&Intel&IBM RS/  &DEC   \\
 Benchmark     &Sparc1&System 5 &TS2025 &T800  &i860 &6000-530 &$\alpha$\\
               &      &         &       &20MHz &40MHz& 25MHz   &133MHz \\
\hline
      d/m/y &18/1/90&25/1/90 &8/8/89 &15/4/89&6/8/90&14/6/90&13/1/93  \\  
%           m/y & 1/90 &  1/90   &  8/89 &  4/89 & 8/90 & 6/90 & 1/93  \\  
\hline
   Linpackd    & 1.27 &  2.79   & 4.32  & 0.33  & 3.89 & 9.54 & 20.7  \\
     n=100 \\
\hline
   Livermore   & 2.36 &  4.64   &       & 0.72  & 8.76 & 31.8 & 46.6  \\
     Maximum \\
\hline
   Livermore   & 0.45 &  0.89   & 0.45  & 0.10  & 0.47 & 1.34 & 4.47  \\
     Minimum \\
\hline
   RINF1(32') \\
   \rinf      & 1.29 &  2.50   &19.29  &  0.34 & 4.62  & 5.13 & 33.8  \\
  (\nhalf)    &(0.30)& (1.00)  &(1.03) &   (0) &(3.61) &      &(12.2) \\
\hline
   POLY1 \\
   \rhat      & 2.50 &  5.18   &42.31  &        &10.59   &25.85 & 88.9\\
  (\fhalf)    &(0.77)& (0.60)  &(0.51) &        &(1.12)  &(0.34)& (0.71)\\
\hline
\hline
\end{tabular}
}
\end{table}

Table-\ref{Table1} shows that the DEC $\alpha$ chip outperforms
all other workstations and chips on all benchmarks by a significant 
margin, as befits the start of a new generation of chips. However, one 
cannot help being impressed by the figures. The remaining workstations 
and chips are compared with each other below.

Table-\ref{Table1} shows that the IBM RS/6000 chip set performs 
best on the LINPACKD100 benchmark, followed by the Stardent ST2025 
which has a vector architecture. 
The i860 performs significantly worse than the IBM 6000. However
the benchmark performance of both machines is expected to improve 
as their compilers develop.

Table-\ref{Table1} gives the maximum and minimum 
performance observed in the 24 Livermore loops. 
The minimum performance can be taken as giving the 
worst scalar arithmetic performance that is likely to be found, 
and the maximum gives the best performance that is likely to be 
seen on highly vectorisable loops. The computer with the best 
worst-performance, which is a very good metric to examine, is 
the IBM RS/6000 followed by the Solbourne. The best maximum 
performance is seen in the RS/6000 followed by the i860.

The RINF1 benchmark gives values of the \rnhalf parameters for the kernel 
A=B*C (vector = vector $\times$ vector), and shows the Stardent ST2025 
performing best with the
highest \rinf and lowest \nhalf, followed by the IBM RS/6000. 

The POLY1 benchmark shows 
the Stardent ST2025 with the highest peak performance, followed 
by the IBM RS/6000 and then the i860. Of these three, the value for 
the IBM is best, and the Stardent quite low, but the value greater 
than one for the i860 shows that there is a severe memory bottleneck 
problem with this chip that will prevent it from getting close to its
peak advertised performance on many problems.

\subsection{Example Results for the COMMS1 benchmark}

We report below results for the COMMS1 benchmark on the \Suprenum,
and Intel iPSC/860 ~\cite{Hoc91} and Touchstone Delta ~\cite{HoCa92} 
computers. 

Table-\ref{Table4.1} gives the values obtained for the communication 
parameters, in the version of the benchmark using the native \Suprenum
extensions to the Fortran90 language. These include a SEND and RECEIVE
language statement with a syntax similar to that of the Fortran READ
and WRITE statement.
The asymptotic stream rate, or bandwidth, (\rinf) shows considerable
variation on the Suprenum, depending on how the data to be transferred
is specified in the I/O list of the SEND statement.  A variable length
array in Fortran90 syntax in single precision achieves 0.67 MB/s,
whereas the same statement specified in double precision achieves 4.8
MB/s.   This double-precision rate is about twice that observed
on the iPSC/860 with their CSEND Fortran subroutine, which sends an array 
whose length is specified in bytes. The principal difference between the 
two computers is the magnitude of the startup time, $t_0$, which is 
$73\mu s$ on the iPSC/860 compared with about 3ms on the Suprenum.  Since 
the startup time, via $\pi_0$, determines the transfer rate for short 
messages (say $<100$B), we see that the Suprenum is 45 times slower than 
the iPSC/860 for short messages. On the other hand the Suprenum has almost 
twice the stream rate for long messages (as seen by the value of \rinf), 
provided the most favourable format (i.e. double precision or 64-bit)
is used in the I/O list.  One may compute from these numbers that the
iPSC/860 is faster at transferring messages for all message lengths
less than 16,481 Byte. The longer startup time on Suprenum results in 
larger values of \nhalf, showing that longer messages are needed to 
achieve any given fraction of the asymptotic rate.

The results for the Touchstone Delta show that this computer has the
fastest short and long message performance, judged respectively by the
values of $\pi_0$ and \rinf. However the improvement of short message
performance over the iPSC/860 is only marginal, and the long message 
performance is only about one quarter of the advertised bandwidth of 
25MB/s. However harware and software improvements made since the 
measurements were made should have improved the results.

If we compare the new generation of production computers, the Intel
Paragon XP/S and the Meiko CS-2, we find, on the dates stated, the CS-2 
to have a higher communication performance than the Paragon for both 
short ($\pi_0$) and long messages (\rinf), and therefore for all message 
lengths. However both computers are at an early state of the hardware
and software development, and both have considerable development 
potential. The COMMS1 benchmark will continue to be used to track
this competition in communication performance, and the success of both
manufacturers to achieve a high performance for both short and long messages.

\begin{table}
\centering
{\small
\parbox{3.5in}{
\caption{\label{Table4.1}
      Values of (\rinf,\nhalf, $t_0$, $\pi_0$) for the communication 
      of messages between two nodes of the same cluster on the Suprenum 
      and neighbouring nodes on the Intel iPSC/860, Touchstone Delta, 
      Intel Paragon and Meiko CS-2 computers. The Delta measurements 
      were made on 17 Jan. 1992, and should have been improved by 
      subsequent hardware and software changes. Paragon measurements
      were made at ORNL 25-28 May, 1993, and the CS-2 measurements were
      made at Southampton University 9 July, 1993}}
\begin{tabular}{llcccc}
\hline
Specification   & Range      & \rinf   & \nhalf   & $t_0$  & $\pi_0$   \\
                & B*         & MB/s    & B        & ms     & k/s       \\
\hline
   SUPRENUM                                                            \\
sp SEND A(1:N)  &            & 0.67    &  2041    & 3.05   & 0.328     \\
dp SEND A(1:N)  &            & 4.82    & 12740    & 2.64   & 0.378     \\
\hline
   INTEL iPSC/860                                                      \\
CSEND (,A,N,,)  & $N<100$    & 2.36    & 179      & 0.074  & 13.5      \\
                & $N>100$    & 2.80    & 560      & 0.200  &  5.0      \\
\hline
   INTEL Delta                                                         \\
CSEND (,A,N,,)  & $N<512$    & 3.48    & 213      & 0.061  & 16.3      \\
                & $N>512$    & 6.76    & 892      & 0.132  & 7.57      \\
\hline
   INTEL Paragon XP/S                                                  \\
CSEND (,A,N,,)  & $N<40000$  & 23.5    & 4044     & 0.172  & 5.80      \\
\hline
   Meiko CS-2                                                          \\
PARMACS         & $N<40000$  & 43.0    & 3747     & 0.087  & 11.5      \\
\hline
* B - byte

\end{tabular}
}
\end{table}

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

%------------------------------------------------------------------------
%      PARKBENCH REPORT (third draft),     END OF FILES
%------------------------------------------------------------------------