%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Multithreading Approach}
% ----------------------------------------------------------------------------
\label{sec:Start0-1}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------
\subsection{A multithreaded computation model}
%----------------------------------------------------------------------------

From the compiler writer's perspective, multithreading presents a
model that has simpler primitives.  The simplicity makes it possible
to pursue optimizations that are difficult if not impossible in the
pure dataflow model.  The separationg of control and data transfer
mechanisms is another big difference.  Researchers have observed
that a large number of the synchronizations and fanouts executed by a
program in the pure dataflow model are redundant.  They can be removed
if some implicit ordering of instruction is assumed, just like in
conventional sequential programs.  Even on Monsoon where the
synchronization is well supported in hardware, synchronization still
costs in terms of bubbles.  The complementary fanouts definitely costs
cycles too.  

The multithreaded view is still close to the traditional pure dataflow
view, except that each node of the dataflow graph, which used to be a
single instruction, now constains a linear sequence of instructions.
The linear sequence of instructions within each node is often called a
thread, and are instructions with predictable short latency.

Instructions that can potentially incur long latency, such as accesses
to global memory, are placed in separate threads from the uses of
their results.  Synchronization between producer and consumer threads
is needed to coordinate execution dynamically.  The matching of dyadic
instructions is generalized to allow a flexible number of incoming
values to a thread.  Coordination of the availability of these values
is done with a {\em synchronization counter} which keeps a count of
the number of remaining values that have yet to be produced.  Only
when the count reaches zero is the consumer thread posted for
execution.  The synchronization counter is decremented by the threads
producing the needed values, with initialization before any producer
thread starts execution.  In summary, each dataflow node now contains
a sequential collection of instructions called a thread,
synchronization is made explicit, and scheduling of thread is also
made explicit.  An important additional requirement is that each
thread runs to completion once it is started.  As in dataflow, each
processor can have many threads available for execution at any time.

This view of multithreaded execution is by no means the only one in
the multithreaded incarnation of dataflow execution.  Other views,
notably Traub's PhD work\cite{Traub-phd} views a thread as a linear
sequence of instructions with possible suspension points within it.
However, Traub's original work in~\cite{Traub-phd} is aimed primarily
at dealing with Id's {\em non-strict} semantics.  It is beyond the
scope of this paper to talk about non-strictness.  It suffices to say
that the non-strict semantics of Id makes it unsafe, in general, to
impose a linear ordering between instructions.  Thus to put any two
instructions into the same thread, the compiler has to prove that it
is safe to do so.  Reducing overhead due to dynamic scheduling is
still a primary motivation behind Traub's work.

The multithreaded model presented here is closest to the TAM (Threaded
Abstract Machine)\cite{jpdc-tam93} model proposed by Culler et. el.
at Berkeley.  TAM however has further notions of how scheduling of
threads should be done.  TAM also distinguishes between inlet threads
and compute threads.  The former are threads executed in response to
incoming messages.  The choice of ``adopting'' the TAM view of threads
here is partly because it is the most widely studied dataflow style
multithreading model so far, with performance results from CM-5.  It
was also partly ported to the J-Machine\cite{Spertus}.  

%----------------------------------------------------------------------------
\subsection{Challenges of Multithreading}
%----------------------------------------------------------------------------
\label{sec:multithread-ops}
%----------------------------------------------------------------------------

Moving to the multithreaded model presents challenges both in the
hardware and software aspects.  On the hardware front, the basic
mechanisms that are needed to support the model have to be identified,
and means of retrofitting them to a stock microprocessor have to be
found.  On the software front, the compiler has to generate threaded
code from a dataflow graph of uni-instruction nodes.  This process is
called partitioning.  As mentioned earlier, this is complicated in the
case of non-strict languages which rely heavily on dynamic scheduling
for their semantics.  

We will first consider some basic operations not often found on
uniprocessor code that are performed frequently in the multithreaded
model.  We then see how these can be provided, or the need for them
can be reduced.  

%----------------------------------------------------------------------------
\subsubsection{Network Access}
%----------------------------------------------------------------------------

Network access is very important to the multithreaded model, just as
it had been for the pure dataflow model.  In trying to be a fully
general model of parallel computing, supporting a lot of sharing of
data and close interaction between computation going on on different
processors, the multithreaded model makes heavy demands on the
network.  Arguments and results of remote calls are passed between
processors across the network.  With split-phase accesses to memory as
the primary form of support for shared memory, network traffic arising
from memory access can be huge too.  Statistics from Monsoon showed
that global memory accesses take up between 8 to 20\% of all cycles.
Cheap access to network, meaning costing the processor few cycles, is
thus necessary.  So is high network bandwidth.  Finally, low latency
is a big plus, but somewhat less crucial because of the ability of
dataflow style multithreading to tolerate latency.

A slow network interface will undermind the advantages of running on
multiple machines, makes such operations as split-phase accesses to
global memory unacceptably slow.  The cycles used to access the
network are all part of the overhead of running multithreaded code on
a parallel processor.  If 50\% of the cycles being executed are used
to access the network, there is a parallel slowdown of 2.  In other
words, if you have only two processors, there would be no point in
running parallel on them, since you could run just as fast on a single
processor.  Of course, one could try to reduce the number of network
accesses, but that is not always possible or it may be too difficult
to do.

%----------------------------------------------------------------------------
\subsubsection{Split-phase operations}
%----------------------------------------------------------------------------

Operations that may take a long time are compiled into a {\em
split-phase} operation in the multithreaded model.  This basically
means that the instructions consuming the results of these operations
are put in separate threads from the operations, and dynamically
scheduled.

Split-phase operations are used predominantly for remote (global)
memory requests.  A memory operation is divided into three stages:
initiating the request from a compute processor, performing the
requested operation at the home location of the desired word of
memory, and finally notifying the requesting processor of the
completion or result of the operation.  The first and third stages of
the operation are performed on the compute processor, while the second
is done at the home location.  The third phase is needed for read
operations for the obvious reason that that is when the read result is
returned.  For writes the third phase indicates that the operation has
completed globally, an information that is needed for implementing any
consistency model.  As the first and third stages can be separated by
a significant amount of time, the compute processor switches to
processing other threads in between.  This approach fits well with the
dataflow/multi-threaded model which considers the need to switch
thread a fundamental operation, rather than a high cost operation that
should rarely occur.\footnote{Compiled code could be structured to
check whether a global memory operation is indeed to a remote node
before performing the split-phase operation.  Global memory operations
that happen to fall onto the local node can then avoid the expenses of
the split-phase operation.  This requires a run-time test and is done
for implementations on machines that pay a large price to get onto the
network\cite{Nikhil-schezoid,cm5-tam}}.

Split-phase operations can also be used for requests to RTS, such as a
frame-request, to facilitate scheduling of execution by the RTS.  By
making the request split-phase, the RTS can easily decide to grant a
request at a latter time if the current moment is not a good time to
satisfy the request.  Finally, RPCs (remote procedure calls) can
similarly be viewed as a form of split-phase operation.

Putting aside the requirement for non-stricntess in some languages,
split-phase operations are essentially the language-independent
motivation for multithreading.  For the use of split-phase operations
to be profitable, the overhead of switching to another thread while
waiting for the result, and the synchronization to manage these must
be smaller than the waiting time.  This leads us into the other
requirements.

%----------------------------------------------------------------------------
\subsubsection{Context Switching}
%----------------------------------------------------------------------------

Multithreading depends on fast context switching.  If a context switch
takes longer than the total round-trip time for a split-phase
transaction, there is no performance advantage in doing the context
switch.  The computation should just wait for the result rather than
switching threads.  Fast context switching can be helpful for
providing other services, for example, servicing the network for
machines that rely on the compute processor for doing that, or
emulating instructions for novel instruction set architectures.  The
multithreading model attempts to reduce the cost of context switching
by using save/restore code customized for each thread.  This allows
only the essential registers to be saved/restored each time.

%----------------------------------------------------------------------------
\subsubsection{Sychronization}
%----------------------------------------------------------------------------

In addition to fast context switching, multithreading requires
synchronization.  Results return from split-phase operations in a
non-deterministic order, forcing dynamic scheduling of threads through
sychronization.  Do does results from threads that can execute in
parallel.  As described earlier, all the values necessary for a
thread to run must be present before the thread is actually run.
Thus, there must be some mechanism that counts the number of messages
destined for a specific thread, and schedules the thread once the
correct number of arguments have arrived. 

%----------------------------------------------------------------------------
\subsubsection{Queue management}
%----------------------------------------------------------------------------

The multithreaded model maintains the notion of a collect of threads
that are ready to be executed, much like tokens in a token queue in
Monsoon.  If threads are short, the overhead incurred in enqueuing and
popping off ready threads can become significant.  

%----------------------------------------------------------------------------
\subsubsection{Need for long threads}
%----------------------------------------------------------------------------

By making synchronization and forking (spawning of parallel threads)
explicit, the multithreaded model throws down a challenge that the
compiler has to generate threads of decent length.  Synchronization,
forking and thread scheduling costs varies according to the
implementation, but it will never be free.  While it is logically
possible to translate single-instruction, pure dataflow style code
directly into multi-threaded code, this will never be efficient.

The use of stock processors as nodes of the parallel machines provides
a further motivation to make the threads long.  Conventional
processors are optimized to run long sequential instruction threads
that have some instruction and data locality.  Longer threads allow
the compiler to make better use of the processor resources.  Standard
processors provide fast, high bandwidth state in the form of
registers.  Efficient usage of registers depends on temporal locality,
which is abundant in long threads, but is nearly non-existent in short
threads.  Register files in current processors allow {\em at least} 2
reads and one write every cycle.  If all the instructions in a thread
are required to read their arguments from memory, 2 loads and 1 store
are required for every instruction executed.  Clearly, the overhead is
substantial.  We also have to accounted for the effects of short
threads on the cache locality.  If stock processors are to be used,
threads {\em must} be long enough, probably at least 50 or so
instructions.

The area of generating long thread is still an active area of
research\cite{Traub,Satyan,EM-4}.  There is, however, some
preliminary evidence that using spit-phase accesses, which breaks code
up into different threads, for all global memory operations makes it
difficult to generate long threads.  

\bigskip


The rest of this section will first describe an abstract architecture,
which we call *T0, that would support the multithreaded model.  We
then describe *T1, a Motorola 88110 based implementation of *T0.

%----------------------------------------------------------------------------
\subsection{*T0: An Architecture for Multithreading}
%----------------------------------------------------------------------------

After our experiences with Monsoon, plans were drawn up for a new
architecture based on conventional RISC technology.  The final machine
design, based on many previous real machines and paper designs, was
called *T\cite{StarT92}.  *T is an attempt at correcting some of the
short-comings of pure-dataflow, while at the same time bringing
dataflow architecture closer to RISC architecture.  The architecture
can be viewed as an augmented RISC processor.

The original *T design, *T0, logically partitions a node into three
parts: the data processor (\dP), the sychronization processor (\sP)
and the remote memory processor (\rP).  (see Figure~\ref{fig:*T0})
% ----------------------------------------------------------------------------
 [*** Include *T0 block diagram, the one in ISCA '90 ***]
% ----------------------------------------------------------------------------
  Each processor is responsible for a different aspect of the
computation.  The data processor's job is to actually execute the
user's program.  The sychronization processor's job is to receive
messages from the network, writing incoming values into frame
memory for the data processor, sychronize, and notifying the data
processor when a thread is ready to execute by posting an (instruction
pointer, frame pointer) pair.  The remote memory processor's job is to
handle remote memory requests from other nodes.  

The actual implementation of a *T0 node can be done in many ways, one
of which is described next.  We call this implementation *T1.



% ----------------------------------------------------------------------------
\subsection{*T1: a Concrete Realization of *T0}
% ----------------------------------------------------------------------------

*T1 was based on a modified Motorola MC88110, called the MC88110MP and
the Artic\cite{Boughton93} network routing chip.  In addition to the
standard MC88110, the MC88110MP contains a network interface built
into the processor as a functional unit, and hardware support for
thread scheduling.  The network interface is accessed via register
operations and is thus very fast.  It also takes advantage of the
MC88110's dual issue capability and wide internal datapath so that a
large number of bits (up to 256 bits) can be moved into the network
buffer each cycle.  A simple message could be formatted and lauched in
6 cycles.  Accessing the data in a received message is also done
with simple register operations, at a slightly lower bandwidth of 128
bits/cycle.  

\begin{figure}
\illustrationpercent{start1}{50}
\caption{A *T1 node}\label{fig:start1}
\end{figure}

*T1 had two 88110MP processors per node, where the two processors
could communicate through their shared memory bus and through the
network (see Figure~\ref{fig:start1}.).  The preliminary plans had one
node acting as a remote memory processor while the other node would
act as both data and sychronization processor.  The remote memory
processor would handler remote memory requests from other processors.
The data processor would read messages from the network, run the
inlets associated with them and run ready threads from its queue.

*T1 would run very similarly to the TAM implementation on the
CM-5\cite{jpdc-tam93}.  The superior network interface would have
given *T1 a great advantage over the CM-5.  Unfortunately, the 88110MP
project was canceled by Motorola, due to their support for the PowerPC
architecture.

In the remainder of this section, we will compare the approach taken
by *T1 to provide the multithreaded operations described in
Section~\ref{sec:multithread-ops}.

%----------------------------------------------------------------------------
\subsubsection{Network Interface}
%----------------------------------------------------------------------------

The network interface on *T1 is much more aggressive then those
available on other RISC style machines.  *T1's short message launch
time of approximately 6 cycles is an order of magnitude better than
the CM-5's 40 cycles\cite{jpdc-tam93}.  It is however worse than
Monsoon's, where (very short) messages are sent in a single cycle.  A
good network interface is probably the single largest improvement that
can be made to a processor to support
multithreading\cite{Supercomputing93-start}.

%----------------------------------------------------------------------------
\subsubsection{Context Switching}
%----------------------------------------------------------------------------

No special hardware support is provided in *T1 for context switching.
It adopts a software solution, relying on the compiler to generate
code for saving registers value at the end of a thread, and loading
registers at the beginning of a thread.  The effect of this choice is
not clear.  On the one hand, it seems that if threads are short, the
number of values to be saved or restored for each thread is not very
large.  Since the save/restore code is compiler generated, only the
relevant register values are saved/restored, not the entire register
file.  On the other hand, threads are not expected to be very long,
making such switches frequent.  Further study, with actual
experimental data is needed to see if this is an adequate
``solution''.  

Thread switching also requires a switch in instruction stream.  If
threads are short, such switches become frequent.  It would have been
better if the hardware prefetches the instruction stream for the next
thread to execute.

The length of threads will have a big impact on how important context
switching is.  However, to the extent that multithreading depends on
frequent context swiches, it would have been nice to have some
hardware support here.  Its absence is a result of the difficulty of
incorporating it into a stock microprocessor rather than the position
that it is not needed.  Fast context switches have been discussed in
previous literature\cite{P-RISC}.  There are countless
implementations.  One method would be to have multiple hardware
register files, such as on Monsoon and Alewife.  A more aggressive
implementation of this would permit one register file to be loaded
while another was used by the executing thread.  One could also try to
speed up the process by providing a wide data path between the cache
and the registers, thus permitting the loading/storing of a cache line
worth of register values at a time.  Yet another method is to have a
context with very little state, such as in Monsoon.  


%----------------------------------------------------------------------------
\subsubsection{Sychronization}
%----------------------------------------------------------------------------

*T1 does not have full hardware support for synchronization.  It has a
conditional post instruction, {\tt cpost}, that conditionally performs
a post based on the value of a register.  However, no support is
provided for atomic update to a synchronization counter.  The essence
of sychronization is an atomic read-modify-write to a memory location,
then a branch on the result.  Synchronization is best viewed as a
memory-to-memory operation because it is not often that the same
synchronization counter is used several times in a thread.  The
read-modify-write to memory can be performed in 4 instructions on a
standard RISC processor, but can take more cycles depending on whether
the read hits in the cache.  Executing sychronization on the processor
has the same problem as swapping contexts --- it adds to the parallel
overhead.  The memory-to-memory and atomic nature of updates to
synchronization counters does not match RISC style execution exactly,
and some specialized hardware support in this area would have been
good.

\bigskip

Overall, *T0 and *T1 addresses many of the shortcomings in Monsoon:
\begin{itemize}

\item{
Since we are using stock processors, or close derivatives, single
threaded performance will be extremely good.  Thus, the threads we
generate should run quite quickly, assuming the threads are long
enough to make effective use of the processor.  Code segments that
need to be sequential, such as critical sections (especially prevalent
in run-time system code), will run very well on these processors.  An
additional benefit of single threaded performance is that more
conventional parallel codes will run well, giving us a truly general
purpose machine.  Single threaded performance will also allow us to
run normal sequential codes (though not in parallel) efficiently.
}
\item{
There are inherent advantages to using sequential threads of code
running on sequential machines.  In traditional dataflow code,
instruction level parallelism is expressed in the dataflow graph,
requiring forking and sychronization.  Sequential processors exploit
instruction level parallelism in hardware using a variety of
non-trival mechanisms.  Thus, the code can be sequentialize into a
thread, eliminating sychronization requirements within a thread, and
the processor will extract the parallelism it needs to keep itself
busy.  Some forking is still required, but not to exploit instruction level
parallelism.
}
\item{
The issue of memory hierarchy is brought to the forefront on such a
machine.  Even if the conventional memory hiearchy is not the best for
multithreaded execution, much can be learned from it; the good parts
can be retained, and innovations can be made without a long evolution.
As mentioned before, if compilation technology can be developed such
that threads can become reasonably long, registers, the most efficient
member of the memory hierarchy, can be made good use of.

*T also remove the need for specialized type of memory.  Token queus, frame
and heap all share the same physical memory.
}
\item{
Finally, it is possible to have more control over thread scheduling in the *T
model than in the Monsoon model, since there may be opportunities to
do scheduling in software.  Scheduling during run-time, however,
unless very simple, can become very inefficient very quickly.
}
\end{itemize}
