

\section{Relevance to the Future}
\label{s:future}

Both the CM-5 and Monsoon are custom, integrated parallel designs -- the
programming models, languages, compilers, processors and networks were all
designed specifically for parallel computing.  Because of this design
approach, the CM-5 and Monsoon and parallel machines like them have three
big disadvantages:
\begin{enumerate}
\item Higher prices due to low-volume, custom-designed processors and
networks.
\item Very tough competition from mainstream computers which improve in
performance at 70\% per year.
\item Most importantly, the inability to run an existing application base
because of incompatible programming models and languages.
\end{enumerate}
In the real world, there few customers who are willing to pay a premium for
two year old technology {\it and} completely re-write their applications,
and consequently, neither the CM-5 nor Monsoon have direct architectural
descendents in today's marketplace.

Regardless, parallel computing has truly entered the mainstream in the form
of small-scale 2 to 16 processor symmetric multiprocessors (SMP's), which
have been extremely popular in the marketplace.  These SMP's are based on
the same commodity microprocessors used in desktop workstations, and being
brought to market simultaneously with workstations by mainstream computer
manufacturers.  They are typically used to concurrently handle multiple
users running commercial sequential applications, but they can also serve
as large database servers and World Wide Web servers, and almost
incidently, they can 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.

For practical purposes, SMP's have won the architectural debate, although
perhaps more for economic rather than technical reasons.  SMP's are
abundant, relatively cheap, and capable of giving high performance either
individually or in clusters.  However, they are generally not used for
parallel computing in the traditional sense, and so 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 they represent two promising styles of
exploiting parallelism on SMP's.  In the rest 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}

SMP's pose an interesting platform for both multithreaded and data parallel
computation because there is no special hardware support for either model.
Despite this, most parallel computing performed on SMP's can be
characterized generally as data parallel style of multithreaded.

At the lowest level, within an SMP, the basic mechanism for parallelism is
OS threads or processes, and communication and synchronization occur
through shared memory.  Between SMP's, communication and synchronization
are implemented at the lowest level through explicit message passing.

These mechanisms can be exploited at a fairly low level through C or
Fortran programs which make calls to parallel ``libraries'', which can be
either multithreaded or data parallel.  Multithreaded-style lightweight
threads libraries are implemented on top of OS threads or processes, and
provide routines for creation and synchronization of lightweight threads.
Data parallel style message-passing libraries, such as PVM and MPI, provide
communications and synchronization routines for programs which are usually
structured in a data parallel: they usually have a single logical thread of
control, interleaving stages of communications and computation, and
parallelism arising from data parallelism.  Thread libraries can be
implemented for clusters of SMP's, although shared memory become
problematic.  Data parallel message-passing libraries are more
straightforward to implement both within SMP's and on clusters of SMP's
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 which has become the
standard data parallel Fortran.  Using HPF on high-end SMP's can provide a
level of performance approaching that of the CM-5 \cite{ECMWF}.  Several
vendors also provide HPF compilers for clusters of SMP's, and even within
an SMP, these compilers usually attempt to structure computation 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 by compiling Id for SMP's.
Whereas Id has implicit parallelism and synchronization, other languages
expose parallelization and synchronization more to the user.  Some of these
languages include Mul-T \cite{Kranz89}, Concert \cite{Plevyak96}, Cilk
\cite{Cilk95}, and Cid \cite{Cid94}.  Thread specification and
synchronization is also a part of the Java language definition \cite{Java},
and although Java was not designed with the goal of being a parallel
programming language, it may stand the best chance of being a widely
accepted parallel programming language for the same economic reasons which
made SMP's the predominant parallel architectures today.

\subsection{Future research}

Most of the technology for compiling HPF for SMP's and clusters of SMP's
exists today -- although it remains to be seen how large the market is for
HPF, and the amount of effort vendors will spend to support it.  Although
HPF is well-suited for GCM and other very regular scientific applications,
it is not well suited for the vast majority of commercial applications run
on high-end computers today.  Furthermore, HPF requires users to re-write
their applications, although this problem can be addressed by compiling
standard C or Fortran programs to execute in a single-threaded, statically
mapped, data parallel fashion.  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 handle hierarchical memories, and load balancing in the presence of
multiple users and processes.

Research in multithreaded computing on SMP's is more basic because the
state-of-the-art is not as advanced as for data parallel.  Compilation
problems include partitioning of work to a coarser granularity, and
detection of parallelism.  Run-time scheduling of work must be very fast in
creating and synchronizing work, and also pay attention to data placement,
temporal locality, and load balancing.  For clusters of SMP's, global
shared memory should be supported using distributed shared memory
implementations which may be integrated with the compiler and run-time
system.

In comparing the suitability of these two models for SMP's and clusters of
SMP's, the same issues we 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.  The main new issues are the ability to handle
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.  Research into
language support for multithreading is unlikely to be of practical
consequence unless an opportunity arises for incorporating such language
support into a new mainstream general-purpose language -- it seems that
parallelizing a sequential language for multithreaded execution would have
a larger impact.

The technical issues involved in implementing the data parallel model are
more tractable than those for multithreading.  Nonetheless, the generality
of the multithreading model argues that it will have the greater impact in
the future because of the greater effort and resources which will be placed
behind it.  Our study indicates that overheads for multithreading can be
comparable to a data parallel implementation.
