\section{Conclusion}
\label{section:conclusion}

Note that the data parallel model can also be implemented efficiently on
dataflow machines \cite{shaw92b}, but our Id implementation uses a
multithreaded computational model.

[ some words about message-passing implementations ...]


Undoubtedly, multithreading is a more general model of parallel computation
than the data parallel model, though currently the latter is by far the
dominant model of parallel computation.  The success of the multithreading
model will depend upon the range of problems which can be expressed, and
its efficiency with respect to the data parallel model when a problem can
be expressed in both models easily.  The GCM algorithm, like most
scientific applications today, is easily expressed in the data parallel
model.  Yet, what this study has shown is that the GCM algorithm
implemented in the implicitly parallel language Id on the Monsoon dataflow
machine almost matches the efficiency of a data parallel Fortran
implementation on the CM-5.

In this last section, we will briefly discuss the importance of the GCM
algorithm, and summarize the performance results of this study.  We
conclude by suggesting language, compiler, and architecture research needed
to realize the full potential of multithreading in the context of
scientific applications.

\subsection{Importance of the GCM algorithm}

The algorithm presented in this paper, especially the elliptic solver,
evolved substantially during this study.  Even though the focus of this
paper is not the GCM algorithm, it is worth pointing out the significance
of this new circulation model.

The dynamics of the GCM model is rooted in the incompressible Navier-Stokes
equations and the algorithm is designed to handle small scales well, so it
is well-suited to simulations of the ocean at very high spatial
resolutions.  A novel feature of our model is that unlike others which
employ approximated forms of the fluid equations, it asymptotes to the
continuum, as the resolution of the model is increased.  An important
implication of its formulation is that as computational power increases,
the model can be used to simultaneously resolve small-scale as well as
large-scale processes.  These issues are developed at length elsewhere
\cite{Marshall97a}.

The possible applications of this GCM model are myriad.  In the hydrostatic
limit, it can be used in a conventional way to study the general
circulation of the ocean in complex geometries.  But it can also address
(i) small-scale processes in the ocean such as convection in the mixed
layer (ii) the scale at which the hydrostatic approximation breaks down
(iii) questions concerning the posedness of the hydrostatic approximation
raised by, for example \cite{Browning}.  Finally, it is interesting to note
that the incompressible Navier-Stokes equations developed here are the
basis of the pressure-coordinate, quasi-hydrostatic atmospheric convection
models developed by Miller \cite{miller-pearce}.  Thus the ocean model is
isomorphic to atmospheric forms suggesting that it could be developed, and
coupled to, a sibling atmospheric model based on the same numerical
formulation.

\subsection{Performance results}

The normalized performance of Id running on Monsoon is comparable to the
performance of CM Fortran running on CM-5, based on cycles executed per
required floating point operation.  Both versions have the same number of
required floating point operations.  The Id version on Monsoon needed 14.6
cycles per required floating point operation, while for the CM Fortran
version on the CM-5 needed 15.2 cycles per required floating point
operation.  These numbers are quite sensitive to the choice of ocean
geometry -- they would look more favorable for multithreading if we had
chosen to study an ocean with a highly irregular geometry.  As always, the
performance is quite sensitive to source code tuning.  Nevertheless, the
efficiency of the multithreaded implementation is impressive in comparison
to the data parallel implementation, given the much greater expressiveness
of the multithreaded model.

For both approaches, the programmer must carefully tune the application to
the programming model and the architecture for good performance.  For the
data parallel version, the entire algorithm was structured around the
elliptic solver inner loop and around minimizing communication by a careful
choice of data representation and layout.  Additional performance can be
gained by setting the problem dimensions to avoid padding of arrays to fit
the machine configuration.  The four-level deep ocean does not provide
sufficient vector lengths for the CM-5, so the performance of the CM-5
version would be twice as good in the more realistic case of oceans with 20
to 50 layers.  There is also significant scope of improvement in compiler
technology for CM Fortran; however, because of the small market for MPP's,
such improvements may not happen.

For the multithreaded version, inlining of functions and constants,
especially in the innermost loops is of crucial importance to reduce
instruction counts.  Furthermore, a bad choice of loop schema or loop
bounds can dramatically increase the number of instructions executed or the
number of idle cycles.  In general, larger loop bounds were chosen for the
outermost loops while innermost loops were kept either sequential or
unfolded.  The best performance was obtaining by a hybrid version of the
code, which performed some computation on land zones.  By treating all
enumerated water columns to a uniform depth, we could unroll the innermost
loops completely and thus avoid significant overheads associated with
dataflow loops.

The algorithm in this model was chosen to minimize communication across
water columns.  This provided substantial benefits for the data parallel
implementation.  It is possible to design a parallel algorithm for the
elliptic solver which communicates more, but reduces the total number of
operations significantly.  We expect such an algorithm would be faster on
Monsoon and slower on the CM-5 than the current version.  Overheads in the
data parallel model come primarily from high-level algorithmic limitations
of the programming model, whereas for the multithreaded model, overheads
are primarily the result of fine-grained synchronization and dynamic
treatment of array bounds.

\subsection{Further research in multithreaded computing}

Coding of the GCM in both Id and CM Fortran was straightforward, and we
believe that coding in either of these languages is significantly simpler
than writing message-passing ``node'' programs.  It is worth noting that
all the abstractions required to program the GCM algorithm in Id were
written by the programmer, while many of them are built-in primitives in CM
Fortran and HPF.  In spite of this, the number of lines of code for GCM is
fewer for Id than for CM Fortran\marginpar{X versus Y lines of code}.  As
scientists begin to use more sophisticated data structures, they will need
to define their own abstractions, and therefore will need the expressive
power of Id.  It is the inadequacy of Fortran that has driven some
scientists to look at languages like C++.  We think most scientists will
find Id or other implicitly parallel languages a more attractive option for
parallel programming than C++.

The experience of developing these programs has convinced us that the code
should not obfuscate the algorithm because the algorithm needs to evolve
for better performance or to incorporate new scientific theories.  We
believe this is the case for most scientific applications -- there is
usually significant algorithmic experimentation needed to develop a major
new code.

The GCM experience has convinced us that setting of loop bounds is a
substantial burden on the programmer.  Some other technique, perhaps based
on run-time scheduling, should be developed that will expose just enough
parallelism to keep the machine busy.  For efficiency of compilation, it
may be useful to identify some input parameters as static in an Id program.
An extreme case of this would be to specify the ocean geometry as static,
and let the compiler generate as efficient a code as possible for that
geometry.  The technique of {\it partial evaluation} can be applied for
this purpose, but it is not far enough along to be of practical use in this
complex a setting.

This performance study demonstrates the viability of dataflow
architectures, even for highly structured data parallel codes like GCM.
Most of the overheads in Monsoon that we encountered are at the
microarchitectural level, such as conditional switches, fanouts, and
bubbles.  Some of these overheads can be eliminated to improve the cycle
counts for the fine-grained dataflow approach by 30\% to 40\% for identical
programs executed.  The current Monsoon architecture has extremely high
network requirements because each reference to global shared memory
requires two network messages.  The only way to reduce this requirement is
by providing local cache memory.

In the current climate, it is difficult to build high-performance
Monsoon-like architectures which are radically different from commercial
microprocessors.  Therefore the attention of most researchers is on
augmenting existing processors to make them more suitable for parallel
processing.  *T-NG \cite{Start-NG}, the successor to Monsoon, is based on
the PowerPC architecture.  This will automatically solve the problem of
providing excellent performance on sequential threads, but it will have
substantially higher synchronization and scheduling costs and non-uniform
memory access time.  To successfully implement Id on an architecture like
*T-NG, compiler optimizations are critical, especially {\it partitioning}
of dataflow graphs to create longer thread lengths to amortize
synchronization costs \cite{Coorg94}.  Substantial work is needed on memory
hierarchy and data distribution, because that has a first order effect on
the performance of any modern RISC processor or parallel machine with
physically distributed memory.  Efficient run-time scheduling of loops and
lightweight threads is also extremely important.

We are investigating techniques for implementing the multithreading
model efficiently on conventional parallel architectures, such as
symmetric multiprocessors (SMP's).  SMP's currently span the range
from 2 to 64 processors and small SMP's are expected to be affordable
and widely available as early as 1996.  An implicitly parallel and
multithreaded programming system on such SMP's can have a far reaching
impact on both the commercial and scientific worlds.
