\section{Performance comparison}
\label{section:performance}

Both GCM implementations use the same numerical algorithm, except for minor
differences such as the order of reductions.  Despite this, comparing the
two implementations requires care because of differences between
the languages, compilers, programming models, architectures, implementation
technologies, machine configurations, and manpower expended on software and
hardware.  In this section, we try to account for some of these
differences and determine the primary characteristics and overheads of the
two implementations.

\subsection{Performance metric}

Because both implementations have used the same mathematical algorithm, the
numerical results and the number of iterations for the conjugate gradient
to converge in each time step are identical.  Consequently, both codes
execute the same number of required floating point operations, though
the number and type of overhead instructions executed differ greatly.  We
consider floating point operations performed on land zones or land-land
surfaces to be non-essential.

We attempt to factor out most of the differences between the
implementations using the simple metric of cycles per {\it required}
floating point operation.  Up to this point, we have been measuring cycles
per floating point operation, which includes any extra floating point
operations which are used for computations on land.

The cycles per required floating point metric factors out many of the
differences between the implementations; it does not, however, quantify all
the dimensions that affect performance. For instance, one of the
architectures may be easier to implement at a high clock speed than the
other or more cheaply than the other; this metric also does not take into
account the much greater manpower spent in optimizing the CM-5 performance.
It would be misleading for us to try and rigorously quantify these factors,
and we leave it to the judgement of the reader to adjust our measurements
as they feel suitable. Nevertheless, as explained below, using this metric
(while understanding its limitations) does yield significant insight into
the efficiency with which GCM can be mapped to the two contrasting
computational environments.

The cycles per required floating point operation metric is clearly better
than the cycles per every floating operation measure we have been using to
this point for both the CM-5 and Monsoon implementations.  For example, in
Figure \ref{figure:gcm-comparison}, the ``Land$+$Water'' version is more
efficient per floating point operation, but many of the floating point
operations that are considered are actually overhead operations because
they are executed on land zones.  When taken into consideration, the
ratio of cycles per required floating point for the ``Water Only'' versus
the ``Land$+$Water'' versus the ``Hybrid'' implementations of multithreaded
PCG is actually about $1.0:.44:.35$, showing that the hybrid version is the
fastest.

\subsection{Quantifying overheads}

Monsoon and CM-5 can be viewed as radically different attempts at feeding
relatively standard FPU's, though this was certainly not a design goal of
Monsoon.  Taken in this context, the ``best case'' numbers 
clearly indicate that the CM-5 is much better when the
situation is ideal -- i.e.,~when there is no garbage padding,
ghost zones are not taken into account and
the problem size is large enough to
overcome vector startup costs.
The rest of this section quantifies further what the effects of the various 
overheads of each model are.

\subsubsection{Overheads due to padding and ghost zones}

The overhead from garbage padding on the CM Fortran verion is usually not
more than 10\%; the compiler can usually find a layout which is fairly
close to the one requested by the programmer.  Because of the hardware
support for ignoring garbage padding, the CM-5 does not pay any additional
cost in terms of execution for garbage padding, above and beyond the direct
overhead due to unused zones.

Ghost zones are a more serious concern for geometries that are shallow or
narrow. The Id version does not have to work on the
faces of the geometry, except to explicitly insert ghost zones on the step
before the stencil computation, and even the stencil computation itself
does not need to compute on ghost zones.  Although the Id version also must
pay for the memory, it does not have to pay for the execution time for
filling ghost zones.

It is clear that ghost zones are not a serious overhead for wide, deep
geometries.  However, we often work with geometries that are of depth 5 to
10, in which case overhead for ghost zones can range from 20\% to 40\% or
more.

\subsubsection{Overheads due to water}

Figure \ref{figure:varying-water} shows the effect of varying the
percentage of water zones on the surface for the Id and CM Fortran codes.
Water zones on the surface are counted, because the hybrid version of
the Id code can only take advantage of eliminating an entire column of
zones at a time.

\begin{fig}{figure:varying-water}{The CM-5 version of PCG is more sensitive
to variations in the percent of water than the hybrid Monsoon version.}
\illustrationx{3.1in}{figures/water-scaling.ps}
\end{fig}

The number of ``required'' floating point operations was calculated as all
floating point operations which are performed in columns of the geometry
which have a water surface zone.  This is not the actual number of required
floating point operations because floating point operations on land zones
are still being executed in the hybrid version of the Id code.  However,
given the number of surface water zones, the number of actual required
floating point operations may vary widely, and the purpose of this graph is
to compare the Id and CM Fortran versions against each other, not against
an ideal.  For these purposes, this measurement is fair, because any
difference between the required floating point operations in this graph and
the actual number of required floating point operations would affect the
performance of both versions proportionately.

The performance for the CM-5 version was calculated by assuming an ideal
performance of 3.5 cycles per floating point operation when the geometry is
100\% water, and then extrapolating backwards by assuming that the
execution time will be identical regardless of the percentage of water
zones.  We give a zone of performance for the CM-5, because the ideal
performance may vary widely depending upon the padding overhead and the
overhead due to executing a smaller problem size.  The upper end of the
zone assumes performance at 100\% water of seven cycles per floating point
operation; this number is not necessarily the upper bound of the
performance of the CM-5 version, and may in fact be worse for some
problems as seen in the next section.

The performance of the Id version was measured on a large geometry, varying
the percentage of water zones on the surface.  The geometry was of size $50
\times 50 \times 10$, running on a two processor system, and is a large
enough problem size to keep the machine busy.  We varied the percentage of
surface water zones and measured the total number of cycles as a ratio of
required floating point operations.

The performance of both versions deteriorates as the percentage of water decreases,
but as exepected the CM-5 version shows more severe degradation, because it
carries out the same amount of computation regardless of the geometry, whereas
the Id version does less work for the geometries with less water. Because
many real geometries of interest consist of 30\% to 70\% water, this
overhead in conjunction with others may make the performance of the CM
Fortran version more comparable with that of the Id version.

\subsubsection{Overheads due to small problem size}

\begin{fig}{figure:varying-vector-length}{Efficiency versus problem size
for the PCG computation; the CM-5 is more sensitive to problem size than
Monsoon.  This difference is primarily due to the added parallelism
exploited by the multithreaded model compared to the data parallel model.}
\illustrationx{3.1in}{figures/size-scaling.ps}
\end{fig}

\noindent Both machines will have worse performance for smaller problem
sizes than for larger problem sizes because of less parallelism to keep the
machines busy.  Figure \ref{figure:varying-vector-length} shows the effect
of varying the problem size, measured in elements of the geometry per
processor.  To obtain this graph, the time needed to perform
PCG for various problem sizes is measured on both Monsoon and the CM-5; the
hybrid Monsoon version is employed, only geometries having 100\% water
were considered.

The variable $N_{1/2}$ is typically used for vector processor to measure
the vector length necessary to reach one half of the performance of the
machine when it has a problem with an infinite vector length.  In a
parallel setting, $N_{1/2}$ will vary according to the size of the machine,
and the problem.  For GCM, we see that on the CM-5, $N_{1/2} \sim 1000$
per VU.  To obtain the number for the entire machine, we must
multiply by the number of VU's in the machine.  For Monsoon, the same value
is $N_{1/2} \sim 35$ per PE.

Because the CM-5 starts out at about 3.5 cycles per floating point
operation versus Monsoon at about 11 cycles per floating point operation,
the CM-5 is still better in absolute terms than Monsoon over much of the
range shown in the graph, despite the fact that its performance deteriorates
faster as the problem size decreases.
The Monsoon version reaches peak performance at a smaller problem size
because Monsoon exploits much more parallelism than the CM-5 does.  Whereas
the CM-5 generally takes advantage of data parallelism for each operation,
Monsoon can take advantage of data parallelism for multiple array
operations at a time, as well as procedural and instruction-level
parallelism.

\subsubsection{Multiplying overheads}

The three primary overheads (padding, water, and size) described to this
point are multiplicative in nature.  Figure \ref{figure:scaling-effects}
shows the effects of these overheads on some example geometries.  The
ocean geometry chosen has a relatively high percentage of water (60\% overall
and 66\% on the surface) compared to some real geometries.  The
high percentage of water in this particular geometry favors the data
parallel approach; however, extrapolating the performance of geometries with 
less water is straightforward.

The first geometry on the left in Figure \ref{figure:scaling-effects} is
the 5-layer domain.  Here, there is a significant amount of overhead from
ghost zones and water.  Also, the base cycles per (every) floating point
operation is high because of poor vector unit utilization due to the
relatively small problem size ($\sim$ 600 zones/VU).  Garbage padding is a
minimal overhead.  For Monsoon, we see a ratio that is fairly close to the
``best case'' because Monsoon is less sensitive to problem size and
percentage of water.

\begin{fig}{figure:scaling-effects}{The multiplicative effects of overhead
for the PCG, varying the number of layers.}
\illustrationx{3.1in}{figures/scaling-effects.ps}
\end{fig}

When we go to a 12-layer geometry, the CM-5 version improves significantly,
primarily because of the better VU utilization due to a larger problem size
-- this directly effects the absolute water overhead.  The ghost zone
padding overhead is also reduced because of the deeper geometry.  The
Monsoon version remains about the same because it is not as sensitive to
problem size.

For the final geometry, a 32-layer ocean, the CM-5 has a base
cycles per floating point operation that is still noticeably worse than its
best case.  The padding and ghost zone overheads are almost negligible, but
the water overhead boosts the ratio to about 9 cycles per required floating
point operation.  We were not able to run a problem of this size on
Monsoon, but we predict it would be not much different than the 12-layer
case, because Monsoon is not as sensitive to problem size as the CM-5.

The three problem sizes shown in Figure \ref{figure:scaling-effects} are
typical of simulations that we perform on a daily basis on the CM-5.
If we had considered a geometry with less water, both
versions would have had higher overheads, but the CM-5 performance would
degrade more than the Monsoon version, because the CM-5 is more sensitive
to variations in the percentage of water.

\subsection{Conclusion}

The best case for CM Fortran on the CM-5 is for very large, all-water
geometries, and the efficiency of the CM-5 for these problems is about 3
times better than for Id on Monsoon (3.5 versus 10.1 cycles per floating
point operation).  However, in more realistic cases, the efficiency of the
data parallel implementation varied from 0.5 to 2 times that of the
multithreaded version. The multithreaded version was more flexible in
handling problem irregularity, and it reached peak performance at a smaller
problem size than the data parallel version.

For both versions, significant programmer tuning was required to obtain
good efficiency, and the type of tuning for each version was very
different.

Although multithreading is a far more general model of parallel computing
than data-parallel, our results indicate that even for an application that
is ideally suited for the data-parallel model, a multithreading
implementation can be comparable in efficiency to a data-parallel
implementation.  Additional minor changes to the Monsoon microarchitecture
(optimizing fanout, bubbles and switches) could reduce multithreading
overhead by about 30-40\%.
