\section{Multithreaded Architecture Projects}
\label{related}

In this section, we breiefly discuss two related
multithreaded architecture projects.
These are the Monsoon project, which implements
a pogram execution model closely related to the one we have
presented; and the Tera computer and its forerunners, which also
address multiprocessor latency and synchronization issues.

\subsection{The Monsoon Project}

Several projects have designed and constructed multiprocessors to
execute nested function programs using dataflow principles.
Of these, the design that comes closest to fulfilling the
characteristics we have outlined is the Monsoon dataflow multiprocessor
~\cite{PapadopoulosCul90}.
The program execution model adopted in these machines derives from
the original {\em unravelling interpreter\/}~\cite{ArvindGosPlo78},
which has much in common with the graph/heap model of \cite{Dennis74}.
In Monsoon there are two forms of data memory, the frame store
and I-structure storage. These correspond, respectively, to
the data frames and heap storage of our implementation.
Monsoon uses dataflow graphs as an intermediate program form
for compiling. Each function application in Monsoon is executed entirely
by one processor, and all local variables are held in a stack
frame allocated in the local frame store.

Monsoon supports {\em I-structures}.
Incremental arrays are held in separate memory units that act
on messages sent by processors to request read and write operations.
Attempts to
read an undefined location in I-structure memory cause the
continuation of the processor activity to be entered in a defer queue
held in the I-structure memory. If the queue
has only one entry, it is stored in place of the expected
value; if more entries are needed, they are listed in an overflow area.
For more on I-structures, see~\cite{ArvindNikPin89}.
A write operation makes an entry in I-structiure memory defined, and
causes all waiting activities to be resumed with the element value.
Experiments with Monsoon have shown that defer queues
contain only a few entries during program execution, most often no more
than one~\cite{HicksEtAl93}.

There is no cache memory in Monsoon. Because the frame store is
local and is built of fast static RAM, there would be little benefit
in caching local variables. The implementation scheme
we have presented could be applied to the Monsoon I-structure memory.
It shows how caching of I-structure words may be done so as to
increase efficiency by reducing the number of network
transactions and decreasing the average latency of I-structure
accesses.

A successor project to Monsoon, the Start-NG
project~\cite{AngArvChi94}, plans to implement
a closely related program execution model using a
conventional superscalar microprocessor, the PowerPC chip.


\subsection{The HEP, Horizon and Tera}

The HEP, Horizon and Tera multiprocessor architectures
have considerable conceptual commonality with the designs
considered here. The processors are multithreaded and can
tolerate latency of memory accesses through the memory
network. Each processor has a large register set built of
fast static memory. The Tera commercial
supercomputer~\cite{AlversonEtAl90} is designed upon
the ideas and experiences from the Denelcor HEP
multiprocessor~\cite{Smith81} and the Horizon project at the
Supercomputing Research Center~\cite{KuehnSmi88}.
The Tera architecture includes four tag bits in each memory word
to support thread synchronization. These tags could be used
to support I-structure operations for incremental arrays, but
software support would be required to manage the queue of deferred
read operations and to schedule activities. To avoid excess
network traffic from repeated
attempts to complete a memory access blocked until a tag is set
by another process, an automatic retry mechanism is provided.

The Tera architecture does not include cache memory. Instead,
it depends on its large register set to reduce required main
memory bandwidth, and multithreading to ameliorate the
latency of main memory access.
Implementing caching as we have described above could improve
the efficiency of I-structure operations significantly.

The program execution model for these machines is a set of
independent processes running in a shared address space, and
the architecture does not provide any specific support for
function application as in Monsoon. Hence it appears that
support of modular nests of functions will be left to the
run-time software and compilers for high-level languages.



