\section{A Fine-Grain Multithreaded Execution}
\vspace {-1.0pc}

A number of approaches to multithreading for latency tolerance have
been proposed and several have been implemented.  Many schemes provide
a substantial amount of hardware support for representing and
scheduling the multiple contexts. The Denelcor HEP~\cite{HEP} 
provided cycle-by-cycle interleaving of threads
which are each given their own hardware context of local registers. A
thread which is blocking on a network transaction is not scheduled by
a processor, and thus does not directly induce idle cycles, until the
dependent transaction completes. 
Other researchers have proposed hardware support for a relatively few
contexts for systems where global data caches can be relied upon to
mask most of the high latency requests~\cite{WeberGupta,Alewife}.

Multithreading for latency tolerance can also be implemented primarily
as a software technique with little or no special hardware support.
The Threaded Abstract Machine (TAM) is a fine-grain threading model
which evolved from the compiling of non-strict languages for hybrid
dataflow/von~Neumann machines~\cite{Culler}. Most TAM implementations
are targeted to ordinary processors with no special support for
multithreading, so this form of multithreading is rightly viewed as a
compiling discipline where a thread's context is explicitly managed by
the executing code.

Our study uses a TAM-like execution model on top of an otherwise
conventional RISC augmented with an efficient user level
interprocessor network interface.
\vspace {-0.4pc}

\subsection{Frames, Code Blocks and Threads}
\vspace {-1.0pc}

The execution state of a TAM computation comprises a {\em tree of
activation frames,} one {\em frame} for each invoked {\em code block},
typically a procedure or a loop iteration. The frame provides the
local storage for code block instances much like a stack frame in
conventional sequential execution. Please refer to
Figure~\ref{activation-tree-fig}.  Statically, a code block consists
of a set of interdependent {\em threads}. {\em Synchronization\/} (or
{\em inlet\/}) threads are scheduled by the arrival of messages.
Typically, a synchronization thread will copy a datum from the message
into the frame and then perform a synchronization operation in the
form of decrementing a counting semaphore in the current frame. If the
synchronization condition is met ({\em i.e.,} the counter decrements
to zero), then a {\em data thread\/} is queued for execution. A data
thread is described by the simple continuation {\tt (FP,IP)} where
{\tt FP} points to the current frame and {\tt IP} points to the first
instruction in the data thread.  Data threads are processed whenever
there are no incoming messages to process. That is, synchronization
threads are preferred over data threads. The model is not preemptive;
synchronization and data threads are nonblocking and, once scheduled,
execute to completion. Also note that the synchronization threads can
be directly mapped into so-called active message handlers
(see~\cite{activeM}).

\begin{twocolumnfig}{activation-tree-fig}{The execution state of a TAM
program is a tree of activation frames. Each frame may, in general,
have several concurrently executing threads. Work distribution is
accomplished by giving each processor a subset of the frames, and thus
the threads that correspond to them.}
\illustrationsizecenter{activation-tree-fig}{4.5in}
%\vspace {-1.0pc}
\end{twocolumnfig}

Within a frame, threads communicate with each other by sharing data in
the frame, including the manipulation of counting
semaphores (and potentially queueing another data thread for
execution). Note that, without special optimizations, interthread
communication does not occur through registers; each thread cold
starts with an invalid register set (except for a register containing
its {\tt FP}).  Communication between frames is strictly through
messages. Also, operations against global storage (the heap) are
accomplished by split-phase transactions. In a global read, for
example, a thread emits a read request into the network and then
continues computing (recall, threads cannot block). The remote memory
processing responds with a message containing the desired location's
value. This message is processed by a synchronization thread, just as
if it had been directly communicated by a thread in some other frame.

Importantly, the execution model is {\em fully parallel.} Generally
speaking, any of the frames in the tree can be responding
to messages and have a supply of running or ready-to-run data
threads. Work is distributed by giving each processor a subset of the
frames, and thus the threads that correspond to them.
\vspace {-0.4pc}

\subsection{Loop Bounds}
\vspace {-1.0pc}

In the TAM model, each iteration of a loop can be given its own
frame (various techniques of loop unrolling and frame reuse
are employed to reduce the overhead of this). By allowing a number of
iterations to exist simultaneously, loop iterations can proceed in
parallel, limited only by the inherent data dependencies across
iterations. By controlling the bound on the number of simultaneous
loop iterations, a programmer can control the amount of parallelism
exposed. {\em Loop bounds\/} can be specified dynamically on a
loop-by-loop basis. We vary the loop bounds in our simulations in
order to study the relationship between the amount of parallelism
exposed and the locality in the frame and instruction reference
streams.
\vspace {-0.4pc}

\subsection{Scheduling Policy}
\vspace {-1.0pc}

Another degree of freedom over the evolution of the program is the
scheduling policy for ready-to-run data threads. In the original TAM
work, each frame supported a local LIFO queue of enabled data threads.
Then, all frames on a given processor with non-empty queues were
linked together into a scheduling list. The scheduler always preferred
data threads from the current frame, so a frame switch would occur
whenever the local stack became empty or a message was processed which
corresponded to another frame (and thus a synchronization thread was
executed which corresponded to another frame). This policy provided
very good performance on single processor implementations, but does
not seem to have performed as well on multiprocessors because a single
frame can not provide sufficient parallelism to mask communications
latency.

In this study, we consider two very simple scheduling structures. On
each processor, we have either a LIFO or FIFO queue of ready-to-run
threads for that processor. In general, the queues will contain {\tt
(FP,IP)} pairs with many different {\tt FPs.} That is, threads for
different frames are mixed on the same scheduling stack. When a
synchronization thread detects that its dependent data thread is
enabled, the {\tt (FP,IP)} pair corresponding to the data thread is
enqueued. Whenever the scheduler requires more work, an {\tt FP,IP}
pair is dequeued and the scheduler jumps to the resulting {\tt IP} to
begin execution of the data thread.






