\section{Implications for the Future}
\label{s:future}

Both the CM-5 and Monsoon are custom, integrated parallel designs -- the
programming languages, compilers, processors and networks were all designed
specifically for a parallel computing model.  In both cases, scant
attention was paid to compatibility with existing sequential or parallel
programs.  One lesson of the Nineties is that, to take advantage of the
continuous improvements in technology, both the hardware and software for
parallel computers must be derived from the widespread personal computer
and associated server technology.  Although the CM-5 used Sparc
microprocessors for its nodes, most of its computational power came from
its custom-built vector units.  A modern symmetric multiprocessor (SMP)
with four microprocessors is a much more general-purpose building block
than the CM-5 node.  In the future, Monsoon style multithreading may be
incorporated in commercial microprocessors, but the external interface is
more likely to be a sequential machine language than a dataflow graph.

Regardless, parallel computing has truly entered the mainstream in the form
of small-scale 2 to 8-processor SMP's.  These SMP's are based on the same
commodity microprocessors used in desktop workstations and PC's, and being
brought to market simultaneously with workstations and PC's by mainstream
computer manufacturers.  They are typically used in the business world
either to handle multiple users running sequential applications, or as
large database and World Wide Web servers.  Almost incidently, they can
also be used for scientific computing applications such as GCM.  For higher
performance levels, clusters of SMP's can be networked using either custom
or commodity networks.  Under the US Department of Energy ASCI program
\cite{ASCI}, two 4-Teraflop machines are being constructed as clusters of
high-end SMP's.

However, so far SMP's have generally not been used for parallel computing
in the traditional sense, and therefore research into the two programming
models discussed in this study are still relevant.  Both the data parallel
and multithreading programming models can be implemented on SMP's and
clusters of SMP's, and represent the two most promising models for
exploiting parallelism on these architectures.  In the remainder of this
section, we discuss the implementation of data parallel and multithreading
programming models for SMP's and clusters of SMP's.

\subsection{Data parallel and multithreading on SMP's and SMP clusters}

Most parallel computing performed on SMP's today can be characterized
generally as data parallel or multithreaded, though SMP's have no special
hardware support for either model.  At the lowest level, the basic
mechanism for exploiting parallelism within an SMP is OS threads or
processes, and communication and synchronization occur through shared
memory.  Between SMP's, communication and synchronization are implemented
through explicit message passing.

These low-level mechanisms can be exploited through C or Fortran programs
via calls to parallel ``libraries'', that can be either multithreaded or
data parallel.  Multithreaded-style lightweight threads libraries are
implemented on top of OS threads or processes, and provide primitives for
creation and synchronization of lightweight threads.  Message-passing
libraries, such as PVM and MPI, provide communications and synchronization
routines for programs that are usually structured in a data parallel
manner (that is, they usually have a single logical thread of control,
interleaving stages of communications and computation). Thread libraries can
be implemented for clusters of SMP's, although the lack of a shared memory
across the cluster becomes problematic.  Data parallel message-passing
libraries are more straightforward to implement both within SMP's and on
clusters because they implicitly have a distributed memory model.

At a higher level, several compilers for High Performance Fortran (HPF)
exist for SMPs -- HPF is a successor to CM Fortran that has become the
standard data parallel Fortran.  Using HPF on high-end SMP's the GCM algorithm 
that has been under scrutiny here, can deliver a
level of performance approaching that of the CM-5 \cite{ECMWF}.  Several
vendors also provide HPF compilers for clusters of SMP's, and these
compilers usually attempt to structure computation even within an SMP as
phases of computation and message-passing style communication.

The state-of-the-art in high-level programming environments for
multithreaded computation is several years behind data parallel, and no
language or system has been as widely accepted as HPF has for data parallel
computation.  We are pursuing our research into multithreading by compiling
Id and a related language pH for SMP's \cite{shaw97,arvind-caro-maessen96}.
Whereas Id and pH have implicit parallelism and synchronization, other
languages require the user to expose the parallelization and
synchronization.  Some of these languages include Mul-T \cite{Kranz89},
Cilk \cite{Cilk95}, Concert \cite{Plevyak96}, Cid \cite{Cid94} and Java
\cite{Java}.

\subsection{Future research}

It is important to discuss the problems that need to be resolved in order to
provide the user with a single effective programming model which will work
on a cluster and scale down gracefully to a single SMP or a workstation.
We discuss both data parallel and multithreading models from this point of
view.

Most of the technology for compiling HPF for SMP's and clusters of SMP's
exists today, although it needs to be improved.  For example, for efficient
message passing, the compiler needs to coalesce messages to increase
message granularity, and for a more effective use of an SMP, the parallel
code fragments within an SMP need to maximize the use of threads and shared
memory. It remains to be seen if the market for HPF is large enough for
commercial vendors to make the required improvements.  A way to broaden the
use of data parallel compiler technology is to apply it to standard Fortran
and C programs.  This approach has been taken by the SUIF compiler
\cite{Amarasinghe}, and research issues in that direction include detection
of parallelism, mapping of data and work, restructuring of loops to 
exploit
hierarchical memories, and load balancing in the presence of multiple users
and processes.

Although data parallel is well-suited for GCM and other regular scientific
applications, it is ill-matched to the vast majority of commercial
applications that run on high-end computers today.  Yet, the research in
multithreaded computing on SMP's is not as advanced as for data parallel.
The main compiler issues are the ability to optimize in the presence of
hierarchical memories, the implementation of a shared memory abstraction in
a distributed memory environment, and load balancing coupled with temporal
and spatial locality concerns and multi-user environments. The compiler
also needs to be integrated with the run-time system for efficient
creation, synchronization and scheduling of threads. Compilation of
fine-grain parallel languages like Id also requires partitioning of work
into coarser grain threads for better efficiency. Further research for
incorporating multithreading into a mainstream general-purpose language is
also needed. It seems parallelizing a sequential language for multithreaded
execution would have the biggest impact.

In comparing the suitability of these two models for SMP's and clusters of
SMP's, the same issues that we have addressed in this paper arise.
Overheads from the data parallel model come from poor handling of irregular
problems, and overheads from multithreading come from dynamic parallelism
and synchronization.  Our study indicates that in some realistic
circumstances overheads for multithreading can be comparable to a data
parallel implementation even for regular scientific applications.  The
generality of the multithreading model may attract greater resources from
industry, and may have much greater impact in the future than the data
parallel model.
