%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{*T: Modified Stock Processors}
%% ----------------------------------------------------------------------------
\label{sec:Start0-1}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

*T is an attempt to build a truly general building block for a
parallel computer, one that will run any type of parallel code
reasonably well\cite{StarT92}.  It also tries to correct 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 a RISC processor augmented with coprocessors for
handling various types of messages.  *T supports the multithreaded
model which was introduced in the dataflow community towards the end
the 80s\cite{Iannucci90,Nikhil88d,Sato92} and gained wide acceptance
over the past few
years\cite{jpdc-tam93,schauser91,traub91c,KP-multithread91}.

From a parallel system building view point, using a commercial
microprocessor with very limited changes allows the use of software
and hardware built for the commercial microprocessor.  Changes will
have to be made for the parallel machine, but substantial reuse of
many components is likely.  The effort of the project can thus be
focused on relevant research issues rather then spent on bringing up
the system from ground zero.

Another motivation for using stock processors is to build a general
purpose machine that can easily support other parallel execution
paradigms.  As most other styles of parallel execution are
characterized by fairly coarse grain parallelism with long sequential
threads between synchronization points, a RISC style microprocessor
will execute them efficiently.  Finally, as stated in the previous
section, the rapid rate at which stock microprocessors are improving
makes it difficult for projects that build custom hardware to
demonstrate a clear advantage as they will be obsolete by the time
they are built.

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

% this figure stolen from Nikhil's /jj/nikhil/docs/92-02-isca
\begin{figure}
\illustrationpercent{fig-start-node}{100}
\caption{A *T node (taken from \protect{\cite{StarT92}})}
\label{fig:start0}
\end{figure}

The original *T design logically partitions a node into three parts:
the data processor (\dP), the synchronization processor (\sP) and the
remote memory processor (\rP) (see Figure~\ref{fig:start0}).  Each
processor is responsible for a different aspect of the computation.
The synchronization processor's job is to receive messages from the
network, write incoming values into frame memory for the data
processor, synchronize the values with other input values for waiting
threads, and notify the data processor when a thread is ready to
execute by posting a continuation.  The remote memory processor's job
is to handle remote memory requests from other nodes.  The data
processor's job is to actually execute the user's program.

The {\sP} must be able to implement the functionality of four new
instructions: {\start}, {\post}, {\next}, and {\join}.  The {\start}
instruction starts a new thread in a different context by sending
arguments to that new thread.  If the context in question is on a
different processor, a message is automatically formatted to start the
thread on that processor.  The {\post} instruction takes a
continuation (instruction pointer-frame pointer pair) as its argument
and puts it into the {\dP}'s continuation queue, essentially passing
work to the {\dP}.  The {\next} instruction terminates the current
thread, finds the next thread in the continuation queue and starts
that next thread running.  The {\join} instruction increments a memory
value and conditionally on the resulting value jumps to a given
instruction pointer.  {\sP} may be viewed as a stripped down dataflow
processor or a processor designed to execute short threads to completion.

The {\rP} needs to be able to send a message to resume a thread on the
requester.  {\rP} essentially behaves like the I-structure controller
in Monsoon.  The {\dP} implements the functionality of the {\start}
and {\next} operations as well.  It must also be able to initiate
remote loads {\rload} and stores {\rstore}.  The {\rload} operation
takes a global address and a continuation.  Its effect is to pass the
contents of the address to the continuation.  The {\rstore} operation
is basically the same as the {\rload} --- an acknowledgment after the
store has been completed is sent to the continuation.

This design is motivated from the need to cater to both long and short
threads.  Fine-grain parallel execution introduces many frequent
interrupts in the form of incoming messages from other processors.
Stock microprocessors are however optimized to run long threads.  To
resolve this problem, any functionality that would require the {\dP}
to switch contexts often has been moved to the {\sP} or {\rP}.  This
allows the functionality requirements of the {\dP} to match that of
stock microprocessors more closely.

% ----------------------------------------------------------------------------
\subsection{88110MP: A Realization of *T}
% ----------------------------------------------------------------------------

The 88110MP *T was based on a modified Motorola MC88110 (88110MP) and
the Arctic\cite{Boughton93} network routing chip.  The 88110MP
contains a MC88110 core along with an internal network interface
operating as a functional unit and hardware support for thread
scheduling.  A diagram of an 88110MP processor is shown in
Figure~\ref{fig:88110MP}.  The network interface is accessed via
register operations, and is thus very fast.  It utilizes the MC88110's
dual instruction issue capability and wide internal datapath allowing
up to 256 bits to be moved into the network buffer each cycle.  A
simple message could be formatted and launched in 6 cycles.  Reading
an incoming message is also done with simple register operations,
albeit at a slightly lower bandwidth of 128 bits/cycle.



\begin{figure}
\illustrationpercent{basic-mp-datapaths}{100}
\caption{The 88110MP.  (taken from \protect{\cite{Supercomputing93-start}})}\label{fig:88110MP}
\end{figure}


\begin{figure}
\illustrationpercent{start1}{50}
\caption{An 88110MP *T node}\label{fig:start1}
\end{figure}

The 88110MP parallel machine consists of {\em nodes} connected by the
Arctic network.  The Arctic network is related to the Monsoon network
but provides twice as much bandwidth per link (200 MBytes/sec/link).  Each
node consists of two 88110MP processors sitting on a shared memory bus
(see Figure~\ref{fig:start1}) --- one node acts as a {\rP} while the
other acts both as a {\dP} and an {\sP}.  The remote memory processor
would handle remote memory requests from other processors.  We used a
full 88110MP as an {\rP} for simplicity's sake.  Since a memory
controller, arithmetic operations and network capabilities are
required of an {\rP}, it was easier and cheaper, at our quantities, to
use a full 88110MP rather than build a separate part.  The data
processor would read messages from the network, run the message
handlers associated with them, and also enqueue and run the ready
threads.  Of course, this division of labor is arbitrary and can
easily be changed.

The 88110MP *T could execute the TAM execution model, based on {\em
active messages}\cite{active-message}, in a fashion similar to the
implementation running on the CM-5\cite{jpdc-tam93}.  *T's superior
network interface would give it a significant advantage over the CM-5.
Other parallel programming models were also considered and partially
implemented for the 88110MP *T.  Unfortunately, the 88110MP project
was canceled by Motorola because Motorola has shifted their emphasis
from the 88110 architecture family to the PowerPC architecture family.

\subsection{Evaluation of the 88110MP *T Architecture}

In this section we will evaluate the 88110MP *T architecture on the
criteria enumerated in Section~\ref{sec:id-on-stock}.  We will also
compare the 88110MP *T to Monsoon.  *T and Monsoon are very different
machines, and not surprisingly, each is superior in some area.  Monsoon
is clearly better at switching contexts, synchronization, and accessing
the network.  *T is much better at single threaded performance.
Though *T has fewer of the desirable traits to run multithreaded
codes than Monsoon, it allows us to see how well multithreaded code
will run on an almost stock processor, and how they should be
augmented further.

%----------------------------------------------------------------------------
\paragraph{1. Network Interface:}
%----------------------------------------------------------------------------

The network interface on the 88110MP *T is much more aggressive then
those available on other RISC style machines.  Its short message
launch time of approximately 6 cycles is an order of magnitude better
than the CM-5's 40 cycles\cite{jpdc-tam93}.  Additional hardware
support is provided to aid in message construction.  Its performance,
however, is still worse than Monsoon's or EM-4's, where short messages
are sent in a single cycle.

%----------------------------------------------------------------------------
\paragraph{2. Thread Creation:} 
%----------------------------------------------------------------------------
The 88110MP *T supports the instruction {\fork} which pushes a
continuation specified in registers onto a continuation stack
(described later in this section).  It also contains some special
features in the network interface that facilitate header construction.
Even though Monsoon can fork a thread in fewer cycles than *T, the
superior single thread performance of *T reduces the need for forks,
as explained below.

In traditional dataflow code, instruction-level parallelism is
expressed in the dataflow graph, requiring forking and
synchronization.  Sequential processors exploit instruction-level
parallelism in hardware using a variety of non-trivial mechanisms.
Thus, the code can be sequentialized into a thread, eliminating
synchronization requirements within a thread.  The processor is able
to dynamically extract this parallelism.  Forking is still required,
but not to exploit instruction level parallelism.



%----------------------------------------------------------------------------
\paragraph{3. Synchronization:}
%----------------------------------------------------------------------------

The 88110MP *T 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.
No support, however, is provided for atomic update to a
synchronization counter.  Just as in thread creation, however, the
need for synchronization in the 88110MP is less because of superior
single-thread performance.  Within a thread, synchronization between
each instruction is implicit.  Though Monsoon has better
synchronization capabilities, it does not necessarily translate into
superior overall performance.

*T also does not have hardware supported presence bits for
I-structures.  It is easy to simulate presence bits by allocating them
out of ordinary memory.  I-structure-like synchronization can be
performed by a {\rP}.  This may not be too inefficient because we
expect network access overhead and network latency will dominate the
extra instructions executed by the {\rP}.

%----------------------------------------------------------------------------
\paragraph{4. Context Switching:}
%----------------------------------------------------------------------------

No special hardware support is provided in the 88110MP *T 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, fine-grain 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 (jump) in the instruction
stream.  If threads are short, such switches become frequent.  The
88110MP *T has no modifications to its instruction fetch unit.  It
would have been desirable for the hardware to prefetch instructions
for the next thread to be executed, thus eliminating the possible
bubbles due to a jump.

The non-interleaved pipeline on the 88110MP is of obvious benefit to
code segments that need to be sequential, such as critical sections
(especially prevalent in run-time system code).  Though 88110MP does
not have multiple register contexts, the total number of registers are
no less than Monsoon or any other microprocessor.  There is always
tension, when there are a fixed number of registers, between giving
all the registers to one thread or dividing the registers among
multiple threads.  We do not understand this tradeoff very well, but
sequential codes or parallel codes derived from them obviously benefit
from having the entire register state.

\paragraph{5. Thread/Message Queue Management:}

The 88110MP *T has hardware support for managing continuations.  A
{\fork} pushes a continuation onto a stack, while a {\sched}
instruction selects either an incoming message or the top of the
continuation stack.  It is also possible to explicitly read the
continuation stack, opening the possibility to explicitly control
thread scheduling.  Scheduling during run-time, however, unless very
simple, can become very inefficient very quickly.  There is much
opportunity for research in this area.

Monsoon's token queues do not require instructions to access, and thus
have higher performance.  *T's offers greater flexibility, however,
which could turn into a great advantage.

\paragraph{6. Global shared memory:}

The 88110MP *T only supported split-phase access to global memory.
{\start} instructions were to be used to initiate all phases of a
split-phase transaction.  *T includes an {\rP} processor that allows
access to the remote memory even if the data processor is busy; thus,
the {\dP} is not required to poll the network periodically.

Monsoon's support for split-phase operations, however, is superior to
the 88110MP *T's support.  Monsoon's split-phase operations are
primitive instructions; all the information needed for an access are
encoded within a single instruction.  On *T, the request is a generic
message which takes about 6 cycles to construct.

It is, however, not hard to design a RISC style instruction which
encodes all the necessary information so that initiating a request
takes only 1 instruction.  Consider, for example, {\tt rload rGAdd rIP
rFP}, which loads from the address specified in {\tt rGAdd}, and invoke
a continuation with ip = {\tt rIP} and fp = {\tt rFP} when the value is
returned.

Monsoon also has the advantage that for a read, the value that is
returned comes in the form of a token, and thus incurs no additional
processing cost.  *T relegates the task of dealing with the
returned value to the {\sP} which will store it into some frame slot.
To the extent that the {\sP} is considered ``extra hardware'' whose
cycles are ``free'', this task incurs no extra cost.  However, the
value has to be loaded into a register from frame memory before it can
be used by the {\dP}.  Depending on how code is generated, testing of
synchronization counters by the {\dP} may be needed.

The design of *T specifically states that global caching is an
orthogonal issue that would not be explored due to time constraints.
When the 88110MP was designed, global caching was again ignored for
expediency.  We feel that global caching has great potential to reduce
communication requirements which could reduce critical paths.  The next
section analyzes global caching and compares it to split-phase
operations when solving the DAXPY inner loop.

\subsection{Comparing Split-Phase and Global Caching on DAXPY}
\label{sec:daxpy}

The DAXPY loop may be written as follows in a high-level language.

{\tt
\begin{center}
\begin{tabbing}
\hspace{2in}fo\=r i = 0 to N-1 do \\
  		\>Y[i] = a * X[i] + Y[i]
\end{tabbing}
\end{center}
}

The assembly code for both a uniprocessor version of DAXPY and a
multithreaded version of DAXPY are taken from \cite{StarT92} and given
in Appendix~\ref{app:code}.  The assembly code for a global cache
coherent machine would look very similar to the uniprocessor version.


If we assume the loop is unrolled $k$ times, then in each iteration
there will be {\tt cmp + (fmul + fadd + add + add)*}$k$ arithmetic
operations, $2k$ {\rload}'s and $k$ {\rstore}'s, and 1 conditional
jump instruction.  The multithreaded version, in addition, will have 4
local loads for the loop constants, $2k$ local loads for the actual
values of $X[i]$ and $Y[i]$, and $2$ local stores to store back
pointers to $X[i+k]$ and $Y[i+k]$.  It will also have a {\next}
instruction, which we count as a branch instruction.

The behavior of remote memory references is very different between
global caching and split-phase operations.  In global caching, a
remote memory reference is actually made only when a reference misses
in the cache.  Let us assume that $l$ is the average latency of
accessing global memory through the cache, taking miss ratios into
account.  Therefore, the total number of cycles for a single iteration
of the inner loop on a global cached machine would be 

\[(1 + 4k) + (2kl + k) + 1\]
\[= 2kl + 5k + 2\]

We assume that all arithmetic instructions take one cycle.  In the
split-phase case, every remote memory reference goes to the network.
Assuming there is enough parallelism, the processor only sees the
number of cycles it must spend formatting and sending the messages.
Again, assuming that arithmetic and local memory operations take one
cycle, and it takes $n$ cycles to format and send a message, the total
number of cycles for a single iteration of the inner loop on a message
passing machine would be

\[(1 + 4k) + (2kn + kn) + 1 + (4 + 2k + 2) + 1 \]
\[= 3kn + 6k + 9\]

This information is summarized in Figure~\ref{tab:daxpy}.

%$k$ is the degree of unrolling, where $k = 1$ is no unrolling.  The $1
%+ 4k$ arithmetic operations are the {\tt cmp + (fmul + fadd + add +
%add)*k} operations.  The global cached machine requires a single {\tt
%jle} while *T requires the {\tt jle} and a {\next}, which we
%categorize as a branch.  The global cache machine does not need to do
%any local loads or stores, while *T requires 4 loads for the loop
%constants and the pointers to $X$ and $Y$ along with $2k$ for
%the actual values of $X[i]$ and $Y[i]$.  Both models need to do $2k$
%remote loads and $k$ remote stores, but the global cache machine takes
%$2kl$ cycles to complete its average load, where $l$ is the average
%latency, and *T takes $2kn$ cycles and $kn$ cycles to perform the
%necessary reads and store, where $n$ is the number of cycles to send a
%message.  We assume, of course, that cache coherency is completely
%supported in hardware and that the next instruction takes a single
%cycle, which would indicate it has hardware support as well.
%
%
%Figure~\ref{tab:daxpy} classifies the number of instructions executed
%in the loop body by each model into several categories.

\begin{figure}
\begin{center}\small
\begin{tabular}{|l|c|c|cc|cc|}
\hline
             & Arith  & Br  & \multicolumn{2}{|c|}{Local} & \multicolumn{2}{|c|}{Remote} \\
             &        &     & Load     & Store    & Load    & Store  \\
\hline
Global cache & $1+4k$ & $1$ &  $0$   &  $0$  & $2kl$ & $k$ \\
processor    &        &     &        &       &       &     \\
\hline
*T           & $1+4k$ & $2$ & $4+2k$ & $2$   & $2kn$ & $kn$ \\
\hline
\end{tabular}\label{tab:daxpy} 
\caption{Instruction cycles in the inner loop of DAXPY unrolled $k$
times, where $l$ is the average latency and $n$ is the cost of sending
a message.}
\end{center}
\end{figure}


To see where *T beats a global cached machine, we simply add up the
two rows and see when *T's row is less.  For *T to win, the following
equation must be true.

\[3kn + 6k + 9 < 2kl + 5k + 2\]
\[ 3kn + k + 7 < 2kl \]

Clearly, the performance of the global cached machine is tied
directly to its miss ratio and the amount of time it takes to get a
global value.  If the miss ratio is low and the time to get a global
value is reasonable, there is no way for *T to win in terms of the
number of cycles.  *T can win if $l$ is large or if $n$ is especially
small.  

Let us assume that $k = 4$.  Now the equation can be rewritten to 

\[ 12n + 11 < 8l \]

For *T to beat the global cached machine, \(n < 2/3l - 1\).  If the
miss ratio is an optimistic 1\% and the global fetch latency is 100
cycles, there is no way for *T to win.  For reasonable values of $n$,
such as 6, $l$ must be more than 10, which would imply miss rates
close to 10\% on global cached machines with global round-trip
latencies of 100 cycles.  There is no temporal locality, {\ie} if $Y$
is not reused soon, it is very possible for the cache to never hit,
favoring *T.  If $Y$ is reused, however, *T will most likely lose.  If
you had a processor where memory accesses can be overlapped, which is
very likely in the next generation of processors, then it will be even
harder for split-phase transactions to beat global caching in
accessing global memory.  For stock processors, global caching is
likely to win, because $n$ is generally closer to 60 than to 6.

This analysis shows that dynamic program behavior has to be taken into
account.  This example is too simple to show the full potential of
efficient message passing and split-phase transactions.  Split-phase
operations hide communication latency, but do not reduce
communication.  Global caching reduces communication, but does not
hide communication latency.  The former requires some hardware support
to run well while the later requires some hardware support to run at
all.  Clearly the two methods are complementary, solving different
problems.  A machine with the ability to perform both kinds of remote
accesses would be much more flexible, performing better on a larger
set of problems, than a machine with just one sort of access.  Others
have come to exactly the same conclusion\cite{Agarwal93,flash93} as
well.  Therefore, our next machine, described in the following
section, will support both split-phase transactions and global
caching.

%----------------------------------------------------------------------------
%  end of this section.
%----------------------------------------------------------------------------