\section{\label{language-sec}The Parallel Continuation Machine}

The parallel continuation machine implements an SPMD programming
model, where all processors keep their own local copy of the
entire code. The execution itself is completely asynchronous, meaning
that each node may execute entirely different pieces of the program.

\subsection{Elements of the PCM}
A PCM program consists of a collection of {\em threads} that cooperatively
solve a single problem. Statically, a thread identifies nothing
more than a sequence of instructions, written in the machine language
of the processor. At runtime, an application can create
arbitrary numbers of dynamic instances of a static thread, each with
its own set of arguments.\footnote{We decided not to introduce a new
term for these dynamic thread instances. No confusion should occur if
the reader bears in mind that the word {\em thread} is used both in a
static and in a dynamic sense.}

The PCM thread specification language, which is explained in
section \ref{thread-lan}, allows the programmer to define threads and
to specify how threads communicate with each other. All machine
specific execution details, such as dynamic load balancing or the
mechanism require to enable transparent inter-thread communication,
are part of the PCM runtime system and do not have to be specified by
the user. This should simplify the task of writing explicit
multithreaded applications without sacrificing the programmer's power
for experimentation. The key elements of PCM's execution environment
are illustrated in Figure~\ref{pcm-model}.

\begin{figure}[htbp]
\centerline{\psfigure{pcm}{4.2in}} \caption{\label{pcm-model}Elements
of the PCM model}
\end{figure}

New dynamic instances of threads can be created by making closures.
{\em Closures} form the contract between the application code and the
runtime system. They contain a pointer to the thread code and all the
arguments needed to execute the code. The thread is ready to execute
when the closure becomes {\em full}; in other words, when it has
obtained all the arguments. Full closures are passed to the scheduler,
which keeps them in a {\em ready queue} and will later schedule them
for the encapsulated threads to run.

In order to enable points of synchronization, a closure can be created with
some of the arguments missing. These arguments are supplied by other threads
in the future. A thread supplying an argument to a non-ready closure must
obtain a reference to where the argument is to be sent. Such references will
be called {\em continuations}; a continuation is just a pointer to a closure
plus an integer offset into the closure. Note that we are slightly abusing
the term continuation here, which is used to refer (in sequential
computations) to {\em the rest of the computation} seen from a particular
program control point. In parallel programs, however, there is usually no
such thing as ``the rest of the computation'' from a single control point,
and the issue of how a thread can be regarded as ``continuing'' from another
thread, which sends one of the needed arguments, is further complicated by
the synchronization involved.

In order to detect when a closure becomes full, every closure has an
additional slot called the {\em join counter} that indicates the number
of its outstanding arguments. The join counter is initialized with an
integer equal to the number of missing arguments at closure creation
time, and decremented each time the closure receives an argument. No
closure is given to the scheduler until the join counter reaches zero.

\subsection{The Thread Specification Language}\label{thread-lan}

The thread specification language described in this section is
implemented as an extension to C. An example program computing the
Fibonacci function is shown in Figure~\ref{fib}.
% the example first
\begin{figure}[ht]
\begin{center}
{\small\begin{code}
{\bf thread} fib\_fork ({\bf Cont} parent, {\bf int} n)\{\\
\>  {\bf if} (n$<$2) {\sf send\_argument} (n, parent);\\
\>  {\bf else}\\
\>  \{\>{\bf closure} k1, s1, s2;\\
\ \\
\>\>    k1 = {\sf make\_closure} (fib\_sum, parent, \_, \_);\\
\>\>    s1 = {\sf make\_closure} (fib\_fork, {\bf cont}\{k1,fib\_sum:x\}, n$-$1);\\
\>\>    s2 = {\sf make\_closure} (fib\_fork, {\bf cont}\{k1,fib\_sum:y\}, n$-$2);\\
\>\>    {\sf post} (s1);\\
\>\>    {\sf post} (s2);\\
\>  \}\\
\}\\
\ \\
{\bf thread} fib\_sum ({\bf Cont} parent, {\bf int} x, {\bf int} y) \{\\
  \>{\sf send\_argument} (x$+$y, parent); \\
\}
\end{code}}
\end{center}
\caption{\label{fib}PCM program to compute Fibonacci}
\end{figure}

In this language a program consists of threads, marked by the
specifier {\bf thread}, and normal C functions. A preprocessor
expands just the threads into C functions, while copying the rest of
the C code literally. The resulting C program can then be compiled
and linked with the PCM runtime library.

Runtime primitives are used by the threads to create closures,
send arguments, and transfer closures to the scheduler:
\begin{itemize}
\item \verb+make_closure+ ({\em Thread}, {\em arg}${}_1$, $\dots$,
{\em arg}${}_n$) \quad Allocates a closure of size $n+2$, and returns
a pointer to the closure. The two additional slots are reserved for
the code pointer and the join counter. Closures can be created without
specifying all the arguments, in which case a missing argument is indicated
by ``\verb+_+''. The join counter is always initialized to the the number of
missing arguments. 

\item \verb+post+ $(k)$ \quad Hands the closure $k$ over to the
scheduler. Only a full closure can be posted inside the thread that
created it. Closures with empty slots will be posted by
\verb+send_argument+ when the join counter reaches zero~\footnote{Note
that for all examples shown in this paper except the protein
folding problem of section~\ref{case-studies}, it is possible to let
{\sf make\_closure} automatically post full closures, thus omit the
explicit post operation.}.

\item \verb+send_argument+ ($v$, $c$)\quad Sends value $v$ to
continuation $c$ and decrements the join counter of the target
closure. The closure is posted if the join counter becomes zero. A
continuation has the type {\bf Cont} and contains two fields: a
pointer to a closure, and an integer offset within the closure. A new
continuation can be constructed, for example, using the expression
{\bf cont}\verb+{k1, fib_sum:x}+, where \verb+k1+ is a closure pointer
and \verb+fib_sum:x+ a symbolic reference to the first argument slot.
\end{itemize}

The preprocessor expands a thread, for example \verb+fib_fork+, into
a C function that takes a single argument, namely a closure, and
fetches all specified arguments from the closure before starting its
actual execution.

\subsection{Executing a PCM Program}

% figure first
\begin{figure}[p]
\begin{center}
\begin{tabular}{ccc}
\psfigure{shot0}{2.2in}&\psfigure{shot1}{2.2in}&\psfigure{shot2}{2.2in}\\
%%0&1&2\\
&&\\
&&\\
\psfigure{shot3}{2.2in}&\psfigure{shot4}{2.2in}&\psfigure{shot5}{2.2in}\\
%%3&4&5\\
&&\\
&&\\
\psfigure{shot6}{2.2in}&\psfigure{shot7}{2.2in}&\psfigure{shot8}{2.2in}\\
%%6&7&8
&&\\
\end{tabular}
\end{center}
\caption{Snapshots of the state of PCM after each thread completion.}\label{snapshots}
\end{figure}

Figure~\ref{snapshots} illustrates the sequence of events, when the Fibonacci
program runs on a single processor.  When there are multiple processors the only
difference is that full closures may be migrated to ensure a balanced load across
all available processors. These scheduling issues will be discussed in more detail
in section~\ref{scheduler-sec}.

The execution of a PCM program can be divided into three phases: initialization,
computation, and termination. We did not show the initialization and termination code
in Figure \ref{fib}, since they are not really important. The first and third phases
are usually very short, with the computation phase constituting the bulk of the
overall execution.

During the {\em initialization} phase, shown in Figure~\ref{snapshots}.0, the
program creates two closures. One specifies the start of the computation, in this
example a ready instance of \verb+fib_fork+, and one specifies the actions to be
taken when the computation ends, in this example a non-ready instance of a special
thread called \verb+top+. This \verb+top+ thread is supplied by the runtime system
and its responsibilities are to terminate the computation and to print the
result(s). The \verb+top+ closure can be instructed to expect any number of results
and must be the one to execute last.

During the {\em computation} phase, the scheduler enters a perpetual loop: popping a
full closure from the ready queue; calling the thread function, such as
\verb+fib_fork+ or \verb+fib_sum+, as specified in the closure, with the closure
pointer as its only argument. Figure \ref{snapshots}.1--\ref{snapshots}.7 show
snapshots of the machine state, once after each full closure has executed. For
example, in figure \ref{snapshots}.1, the thread \verb+fib_fork+ with argument 3 has
just terminated. It created three closures: two full ones for \verb+fib_fork+ with
arguments 2 and 1 respectively, and a closure for \verb+fib_sum+ waiting for two
arguments. The full closures were immediately posted.  These full closures contain
continuations which point to the place in the sum closure where they will send their
results.  Similarly the sum closure contains a continuation pointing to the top
closure, which is where its result should be sent. 

During the {\em termination} phase, shown in Figure~\ref{snapshots}.8,
the top thread is run. It will print the result of the
computation and then cause the scheduler to exit the loop, thereby
terminating the computation. For multiprocessor computations, the
processor on which the \verb+top+ thread is executed also
signals schedulers on other processors to exit their work loops.

\subsection{Tail-Calls}

A thread may directly call other threads via the following runtime
primitive:

\begin{itemize}
\item \verb+tail_call+ ({\em Thread},
{\em arg}${}_1$, $\dots$, {\em arg}${}_n$) \quad
\end{itemize}

A tail-call represents a more efficient invocation of a thread,
avoiding any of the the dynamic execution overheads incurred otherwise. In
the example shown in Figure \ref{fib}, the thread \verb+fib_fork+
creates two full closures \verb+s1+ and \verb+s2+ and posts both of
them before releasing control and returning to the scheduler. After
receiving control, the immediate action of the scheduler will be to
pop the \verb+s2+ closure and to call its thread function
\verb+fib_fork+, which in turn needs to unpack the \verb+s2+ closure
prior to doing actual work. We can thus avoid this costly detour
through the scheduler by rewriting the code with a tail-call as
follows:

{\small\begin{code}
\>\>    s1 = {\sf make\_closure} (fib\_fork, {\bf cont}\{k1, fib\_sum:x\}, n$-$1);\\
\>\>    {\sf post} (s1);\\
\>\>    {\sf tail\_call} (fib\_fork, {\bf cont}\{k1, fib\_sum:y\}, n$-$2);
\end{code}}

To implement this mechanism, the thread preprocessor actually expands a thread into
two C functions: a {\em general entry version}, which is what we mentioned before;
and a {\em fast entry version} which receives all arguments directly. A
\verb+tail_call+ is thus converted into a standard C function call to the fast entry
version. The actual performance improvements obtained with the tail-call mechanism
can be quite impressive, especially for fine-grained applications, such as the
Fibonacci example, where the performance improved by almost twenty-five percent. The
effects of using the tail-call mechanism can be seen in Figure~\ref{commcost}.

\subsection{Passing Vectors in Closures}

An additional mechanism provided by the thread language allows structures to be
passed in closures. One of these structures may even be of arbitrary length. These
vectors can then be referenced within a thread like any other local variable. The
one vector argument which is allowed to be of arbitrary length needs to be specified
as the last argument, to make sure it is packed into the tail of the closure. 
\begin{itemize}
\item[] \verb+thread+ {\em foo} (\dots, {\em type vect1}[10], \dots, {\em type vect2}[])
\end{itemize}
declares a vector argument {\em vect} of type {\em type}. 
It is the responsibility of the creator of
the closure to initialize the vector. For example, the expression 
\begin{itemize}
\item[] \verb+make_closure+ ({\em foo}, \dots, {\em vect1}[10], \dots, {\em vect2} = [{\em size}])
\end{itemize}
creates a closure for {\em foo}, dynamically defining {\em vect2} to consist of
{\em size} entries. In addition, {\em vect1} and {\em vect2} will be declared to be
pointers initialized to the zeroth word of the corresponging vector arguments.
These pointers must be used subsequently to initialize the vectors, which would
otherwise be left empty. If we use ``\verb+_+'' instead of a {\em vector name} when
allocating a closure, then the vector is intentionally left empty, and its {\em
size} will be added to the initial join count.  

\subsection{Partitioning Functions into Threads}

Consider the following C program, which can be viewed as the ``source'' of the
two threads shown in Figure~\ref{fib}.
{\small\begin{code}
\>  {\bf int} fib ({\bf int} n)  \{\\
\>\>    {\bf if} (n$<$2) {\bf return} (n);\\
\>\>    {\bf else} {\bf return} (fib(n$-$1) $+$ fib(n$-$2));\\
\>  \}
\end{code}}
The function \verb+fib+ as shown has no parallelism. It order to expose
parallelism, we must post one or both of the sub-calls to \verb+fib+. But
here we encounter a major difficulty: the addition depends on the return value
of both calls. How can we set up the linkage between threads or instruct the
scheduler to execute the addition after both sub-calls are complete? 

One well-known solution is to use a {\em blocking thread model}. In
such a model, the runtime system would suspend an executing \verb+fib+
thread after it forked off its two sub-calls and later, when the two
sub-calls terminate, resumes the thread so that it can continue its
execution. The costs for suspending and restoring a thread can be
fairly expensive, depending on the number of registers that need to
be saved\footnote{On the CM-5, for example, when suspending the
current thread, it is necessary to save the entire context kept in the
register windows. Generally, if the function call follows the
callee-save convention, then all the callee-save registers must be
saved.}.

The solution shown in Figure~\ref{fib} uses a {\em non-blocking thread
model}. In this model, new threads are created at points where context
switches would otherwise occur. For example, thread \verb+fib_fork+
makes a closure for \verb+fib_sum+, which is exactly saving the
context needed for \verb+fib_sum+ to execute later.  Consequently,
threads always execute to completion once started.  In other words, we
are essentially following a caller-save convention, which tends to
save fewer registers. For instance, in the \verb+fib_sum+ closure,
only the continuation \verb+parent+ needs to be saved.

From a language point of view, threads provide an abstraction which is
lower than the one of functions. As we have seen, a function such as
\verb+fib+ translates into two static threads, which will then expand
into three dynamic threads at runtime. As pointed out in the
introduction, there are compilers with automatic partitioners that
systematically convert and package a function into threads. Automatic
partitioning is still a very active area of research (see for example,
\cite{tcs92}), but we will not touch it further, since we are mainly
interested in using the thread language in its own right in this
paper.
