\section{Introduction}

In this paper we present a case study of a state-of-the-art ocean
circulation model \cite{Marshall97a,Marshall97b} implemented in Id (a truly
implicitly parallel language) \cite{id} on Monsoon (a multithreaded
dataflow machine) \cite{monsoon} and then critically compare it with the
same algorithm developed in a data parallel Fortran dialect on the CM-5 (a
massively parallel, distributed memory, Von-Neumann architecture)
\cite{CM-5}.  The ocean model contains abundant data parallelism and
attains good performance on the CM-5. The process of implementing the
multithreaded Id version gives us insight into the techniques necessary to
attain good performance, on real scientific applications, using implicitly
parallel languages, multithreaded architectures and data-driven
computation.

Multithreading is the simultaneous parallel execution of multiple threads
of computation: threads can spawn new threads and may synchronize with
other threads.  In the arbitrarily-general form of multithreading presented
by Id on Monsoon the sequence of computation is entirely data-driven and
controlled solely by data dependencies in the underlying algorithm. This
allows all forms of parallelism in an algorithm to be exploited.

Despite the elegance of this approach, the arbitrarily-general
multithreading programming model has not gained widespread usage in
parallel scientific codes.  Instead the single program multiple data (SPMD)
approach has been widely adopted for production parallel codes. Here the
inherent data parallelism common to many scientific codes is exploited and
a rigid regime of synchronous computation followed by communication is
followed. Although an expressively restrictive framework which only
exploits certain forms of parallelism, this programming model is generally
acknowledged as being highly efficient for many scientific codes in which
the data structures are highly regular.

The data parallel model implementation examined here uses CM Fortran, which
exploits data parallelism at the statement level. Another common approach
in scientific computing uses shared-memory or message-passing
multi-processing to exploit data parallelism at the sub-program level. In
either case the computational model is limited to, and can only really work
efficiently for, problems that are predominantly data parallel and regular.
In contrast, the fully general multithreaded environment presented by Id on
Monsoon can exploit all the forms of parallelism, including data
parallelism, that an algorithm possesses, and so imposes less restrictions
on expression.  However, a lack of mainstream software and hardware support
and a conseqent lack of absolute performance have precluded much serious
attention being given to such general multithreading by the architects of
present day parallel scientific applications.

Even within the discipline of computer science, there are relatively few
studies of multithreaded implementations of large scientific applications
carried out on multithreaded architectures.  Closely related to this study,
Hicks, et.al.~\cite{id-performance} considered performance of Id on Monsoon
for several applications and compared it to sequential performance in C or
Fortran 77 on a conventional RISC architecture.  Yeung \cite{Yeung93} uses
the preconditioned conjugate gradient algorithm to study the effects of
architectural support for synchronization on the MIT Alewife architecture.
Hiromoto, et.al.~\cite{Hiromoto84} have performed detailed performance
studies of various scientific applications for the Denelcor HEP.  Hammes,
et.al.~\cite{Hammes95} have performed a comparison of Id and Haskell for a
Monte Carlo photon transport code.  Sur and Bohm~\cite{Sur94} study
different Id implementations of FFT in the context of solving partial
differential equations and implementations of the Dongarra-Sorensen
eigensolver \cite{SurBohm94}.  Arvind and Ekanadham \cite{Arvind88a} have
compared the implementation of the hydrodynamics modeling application
SIMPLE in Id and in Fortran; Arvind, et.al~\cite{Arvind88} have also
explored the benefits of fine-grained parallelism in scientific
applications.  In one of the original papers about programming for dataflow
machines, Dennis, et.al.~\cite{Dennis84} describe the process of
implementing a weather modeling code for a theoretical static dataflow
architecture as well as the sources of parallelism within the code.

Other related work includes high-performance implementations of functional
languages.  Most notably, SISAL has shown very good performance on a number
of ``conventional'' parallel architectures \cite{Cann92} as well as
multithreaded architectures \cite{Gurd:1985:MPD} \cite{Sohn94}
\cite{Oldehoeft86} and has been used to write a number of scientific
applications \cite{Cann92}.  Miranda has been used to code an oil reservoir
simulation \cite{Amoco93}.  Haskell has been used to code a parallel
finite-element problem \cite{Grant95}.

The authors believe this study is the first detailed system-level
comparison of a large, real scientific application implemented in a data
parallel environment {\it and} a multithreaded environment.  Comparison is
possible, but definitive conclusions are difficult to draw because of the
differences in languages, compilers, architectures, technology, and
investment levels in manpower.  Nonetheless, in accounting for some of
these differences, we conclude that overheads for the two implementations
come from very different sources and that, surprisingly, they balance out
for realistic problems.

The paper is organized as follows: Section~\ref{section:ocean-model} begins
with a brief algorithmic description of the model and an analysis of its
computational requirements (readers primarily interested in the computer
science aspects of this study may choose to skip
Section~\ref{section:ocean-model} without much loss of continuity).
Section~\ref{section:programming-fortran} and
Section~\ref{section:programming-id} describe the programming,
optimization, and best case performance of the data parallel and
multithreaded versions of the ocean model, respectively.
Section~\ref{section:performance} compares the performance of the two
versions when they are adjusted for overheads seen in real problem
definitions.  Finally in Section~\ref{s:future} presents the relevance of
this research in the context of current trends in the design of
high-performance parallel systems.
