\section{Parallel Programming}
\label{sec:parallel-programming} 

Writing parallel programs is currently much more difficult than
writing sequential programs.  The difficulty arises from three
problems: (1) managing the control flow along multiple threads of
execution, (2) managing the placement and access of global data, (3)
timing events in such a way that parallel speedup is achieved.  While
it is possible for a programmer to explicitly choreograph a parallel
program by indicating which tasks execute when, how tasks communicate
and synchronize, and where data should be placed and how it can be
accessed, such an undertaking is extremely complex.  Several parallel
programming models have thus emerged in an attempt to cope with these
difficulties.  We discuss some of these below.

\subsection{Data Parallel Model}

The data parallel programming model, exemplified by languages such as
CM Fortran, Fortran 90, Fortran D, and High Performance Fortran (HPF),
is a very popular model of parallel programming.  The data parallel
programming model maintains the single thread of execution of
sequential programming.  That single thread of execution, however, can
perform the same operation in parallel on a selected subset of array
elements (hence the name, {\em data parallel}).  Conceptually each
data element resides on a specific virtual processor.  Periodically,
data elements have to be moved to a virtual processor that needs them
for computation.  Since the cost of data movement is high, the initial
data placement, and the data movement operations must be planned very
carefully to achieve high performance.  Currently, the programmer has
to help with the placement of global data by providing directives
(automating the data placement process is currently an active area of
research).  Once the placement is specified, the compiler takes care
of the tedious task of generating the actual memory access code.

SIMD machines, like the CM-2, provide a direct hardware implementation
of this programming model.  Processors in the machine operate in
lock-step, with a single instruction stream controling the operation
of all the processors.  General communication, that is an arbitrary
permutation of array elements, is very expensive. For example, general
communication on the CM-2 takes about 80 times as long as a primitive
arithmetic operation; nearest neighbor communication is an order of
magnitude faster, but still takes about 4 times that of a primitive
arithmetic operation.  A program must keep general communication of
data to a minimum in order to achieve reasonable performance.
Unfortunately, some programs, are not amenable to this type of tuning.

The data parallel programming model has been implemented on various
types of MIMD machines such as distributed memory, message passing
machines ({\eg} CM-5, Paragon), cache-coherent shared memory machines,
and dataflow machines ({\eg} EM-4\cite{Shaw92b}).  Although each
processor has its own thread of control during execution, the program
still follows a single thread of control logically.  In order to
preserve the lock-step execution semantics of data parallel programs,
implementations on MIMD machines have to perform explicit barrier
synchronization periodically.  Barriers can be implemented in software
on top of the communication facilities of the machine\cite{Shaw92b}.
Many global communication primitives have the implicit effect of
barrier synchronization, making the removal of redundant explicit
barriers a compiler optimization.  For machines that do not have very
high performance networks, specialized global synchronization hardware
as found on the CM-5 is sometimes provided.  On the other hand, the
ability of each processor to have its own thread of control makes MIMD
machines much more efficient at executing conditionals than SIMD
machines.

Some distributed memory machines favor large messages over small ones
due to poor network interfaces. On such machines, the compiler or the
programmer has the added burden of grouping small messages together
({\ie} {\em message vectorization}).  Managing the global movement of
data remains the biggest issue in the implementation of data parallel
model.  Split-C is a language that provides a convenient way of
expressing global data movement in the data parallel
model\cite{Culler93c}.  

Placement of data is significantly easier on shared memory machines
than on distributed memory machines.  Shared memory machines are
somewhat more tolerant of dynamic communication requirements, but
still require good temporal and spatial locality to perform well.
Careful orchestration of data access pattern is still important on
these machines.

The data parallel programming model, because of its closeness to
sequential languages, and because of its good performance for a
certain class of programs (mostly dense matrix computations) on a
fairly wide range of hardware platforms, has gained wide acceptance.
The data parallel model is, however, restricted in the forms of
parallelism that it can exploit due to its single thread of control.
It is also restricted in the class of programs that it can efficiently
execute due to data placement requirements.  Any sort of irregularity
rapidly decreases the efficiency of data parallel programs, even
though there may be considerable parallelism in the underlying
algorithms.  As far as we know no one has even attempted to express a
symbolic code, such as a compiler, in the data parallel model.  These
types of programs need both a more general model of parallel computing
as well as a machine that can support general communication
efficiently.

\subsection{Control Parallel Model}

Programming models that try to exploit task level parallelism
represent a large departure from the data parallel programming model.
These models do not restrict parallelism to concurrent operation on
arrays.  Instead, they attempt to make full use of multiple threads of
control.  ``Data parallelism'' can still be exploited since it can be
expressed as multiple threads of execution on different array
elements.  These models, however, are more complicated than the data
parallel model, since they must manage multiple threads of control.
In the next few paragraphs, we discuss several programming models that
fall into this general category, but differ from one another in some
significant aspects.

{\em Communicating Sequential Processes} (CSP) based programming
languages, such as Ada and Occam, offer one approach to control
parallel programming.  The multiple threads of control are exposed at
the source language level. These threads are called tasks in Ada and
processes in Occam.  Communication between processes is through fixed
channels, and synchronization is achieved through the use of blocking
sends and receives.  Globally shared memory is usually not supported
in this model.  Any shared data has to be communicated through
messages managed by the programmer. The network of processes and
channels corresponding to a program are statically mapped onto
physical processors and channels.  A very simple scheduler on each
processor schedules processes and manages communication.  While this
programming model puts the power of writing parallel programs in the
programmer's hands, it does not provide very much support in managing
the complexity of parallel programming.

PVM\cite{PVM3} represents another approach to parallel programming
which is closely related to the CSP model.  This model is implemented
via libraries on top of conventional sequential languages like C or
Fortran.  PVM consists mostly of send and receive functions.  Messages
have to be explicitly received.  Receives can be blocking or
non-blocking and can specify a message sender processor and/or a
message type to receive, but are not required to do so.  Shared memory
is not directly supported by PVM.  There are other parallel
programming ``languages''/packages that are similarly implemented via
libraries on top of C that do support the abstraction of shared
memory.  An example is the Argonne National Laboratory's (ANL)
parallel processing macro package, parmacs, used in the SPLASH
benchmarks\cite{splash}.  The management of multiple threads of
control is still the programmer's responsibility in all these
packages.

In an effort to exploit finer grain parallelism, several programming
models take a much more dynamic view of thread creation and
synchronization.  Each processor keeps a pool of threads and does
``multithreaded execution''.  This allows the idle cycles in one
thread, due to such things as waiting for synchronization or remote
memory operations, to be used by other threads to perform useful work.
A very dynamic form of scheduling is required by this model. In
general, management of threads can be done in user code, in the
operating system, or by a system supplied run-time system (RTS).
Having the user manage threads is impractical, tedious, and error
prone.  Having the operating system manage the threads imposes
extremely high overheads.  Both methods are prone to deadlocks and
race conditions.  A better solution is to hide this complexity from
the user and have the system software, either compiler, run time
system, or both handle this task.  When the compiler generates
threads, it is able to adhere to certain restrictions that allow the
RTS to ensure that deadlocks and races do not occur.  The TAM model,
which we will discuss later, embodies many of these
features\cite{jpdc-tam93}.

\subsection{Implicitly Parallel Model}
 
Id, a parallel language based on functional languages, represents an
effort at exploiting fine-grain parallelism while keeping the task of
parallel programming manageable \cite{Id}.  The implicitly parallel
programming model offered by Id insulates the programmer from the
concerns of managing parallel threads of control and global data.
Instead of a data parallel, or task-level model, the programmer is
provided with a data-driven model.  In writing code with the
functional subset of Id, the programmer only has to think about
expressing data dependencies, a task that is inherent in any form of
programming.  The functional nature of the language allows the
compiler to extract fine-grain parallelism and generate code that
takes advantage of multiple threads of execution via multithreading.
In Id, synchronization is managed automatically by the compiler,
allowing fine-grain producer-consumer synchronization.  The
programming model provides global shared memory by default, and thus,
the programmer does not have to manage data movement explicitly.

The functional nature of Id is the key that provides automatic
extraction of parallelism.  Other functional languages, notably
SISAL\cite{sisal-on-cray}, are similarly able to exploit implicit
parallelism.  Id goes one step further by providing non-strict
procedure calls, which allow a call to begin execution before all the
arguments have arrived, thus pushing the idea of an eager, data-driven
execution to its limits.

The implicitly parallel approach provides a model that takes full
advantage of all forms of available parallelism, while hiding the
complexity of multiple threads of control.  It is more general than
the data parallel model in the forms of parallelism it can exploit,
while avoiding the coding complexity of the control parallel models.
Having such positive traits, the implicitly parallel approach will be
a clear winner if the model could be implemented efficiently.  Here,
however, lies the difficulty encountered in this approach.  The fine
granularity of the parallelism makes efficient implementation on
commercial parallel machines difficult.  Since synchronization is
pervasive, threads are switched frequently.  Compile time information
for managing locality is simply not available under such dynamic
conditions, and this makes it difficult to generate efficient code.

The implicitly parallel model also requires a global shared address
space and word-level memory accesses. Commercially available parallel
machines either do not support these abstractions or do so poorly,
thus increasing the difficulty in efficient implementation.  Despite
these problems, considerable progress has been made.  The Monsoon
dataflow machine, which we will discuss in greater detail in
Section~\ref{sec:monsoon}, is a demonstration that hardware can be
built to support such a programming model.  Much work still has to be
done to deliver the promises of implicit parallel programming.  The
potential payback of taking advantage of all forms of useful
parallelism implicitly, without the complexity for the programmer, is
a great incentive to continue research in this area.  This paper will
deal with some of these difficulties and propose means of overcoming
them.


