%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{StarT, the Next Generation}
% ----------------------------------------------------------------------------
\label{sec:realizable-machine}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We plan to build another parallel machine called {\archname} (StarT,
the Next Generation) in collaboration with Motorola.  The machine
design is heavily influenced by the *T work described in the previous
section.  The main difference between the original *T and {\archname},
motivated by the analysis presented in the previous section, is the
addition of coherent caches for global shared memory.  Full support
for message passing is to be retained in this new model.

Adding global caches does not create a fundamental shift in our
software model for *T.  Cache coherency has always been considered an
orthogonal issue.  Compiler implementations, however, will have to take
temporal locality of memory references into account to exploit this new
feature.  Global locations that are known to be already written and
likely to be reused should be accessed through the cache coherency
interface, while locations that may not have been ``filled'' should
probably be accessed via split-phase operations.

We plan to implement {\archname} within the next two years, using some
64-bit processor from the IBM and Motorola PowerPC family.  This
choice is natural given our collaboration with Motorola, and the
expected cost/performance of these processors.  We are constrained to
make no modification to either the processor or the operating system.
Thus, all the hardware support for the desired features must be built
around the processor.  The PowerPC architecture has no on-chip network
interface.  Thus an external network interface unit (NIU) that
communicates via existing memory datapaths must be provided.

In order to support global caching, we must provide an external piece
of hardware to detect requests for a global location and to satisfy
those requests.  We call this piece of hardware the Shared Memory Unit
(SMU).  The logical place for the SMU is off the main memory bus of
the processor.  For reasons that will become clear shortly, the SMU
will also have an NIU for accessing the network.

\begin{figure}
\illustrationpercent{start2}{50}
\caption{A {\archname} site}\label{fig:start2}
\end{figure}


The basic building block, called a {\em site}, will consist of several
PowerPC processors connected by a snoopy bus to memory and an SMU (see
Figure~\ref{fig:start2}).  Some of the processors will have NIU's,
which may be connected through the second-level cache interface.
There are many possible configurations for a site.  For discussion
purposes, we will assume that a site contains two processors and both
processors have an NIU.  Furthermore, we will designate one of the two
processors as the compute processor ({\dP}) and the other as remote
memory processor ({\rP}) which will also provide the functionality of
the synchronization processor ({\sP}).  An entire processor is not
required for an {\rP}.  Using a full processor, however, is the
simplest and cheapest solution in terms of the engineering effort
required, since it already contains the memory bus interface required
to access local memory, and has the computation power to run cache
coherency protocols and operate on presence bits in software.

Sites will be connected through a network built from the same
Arctic\cite{Boughton93} chips that we had planned to use in the
88110MP-based *T machine.  As stated earlier it will have at least
double the bandwidth (200 MBytes/sec/link) as the Monsoon network.
The network will probably be configured as a FAT tree.

Before we describe how message passing and global caching will be
supported on this machine, we want to emphasize that our approach is
minimalist.  For example, we will not consider any external custom
device whose complexity may approach that of the processor.  However,
we still have several options for site configurations which we will
discuss at the end of this section.

\subsection{Message Passing and Split-Phase Transactions on {\archname}}

% Start operation: send side
Our basic message passing primitive is the {\start} operation.  The
{\start} operation takes a continuation and some arguments and sends
those arguments to the processor specified by the continuation and
executes that continuation with the arguments.  Since we are not
permitted to change the processor architecture, {\start} must be
emulated in software.  We can, of course, optimize each instance of
the {\start} instruction to execute as efficiently as possible in its
context.  However, the efficiency of the {\start} instruction
crucially depends upon the overhead of accessing the network through
the NIU.

The NIU must be memory mapped since that is the only way to get large
amounts of information in and out of the processor.  The NIU may have
its own memory to provide some message buffering. It will have an
input queue and an output queue that allows the processor to send and
receive messages respectively.  The NIU has to be able to function at
the processor's clock rate as well as the network's clock rate.

To execute a {\start} operation, the processor must communicate data
to the NIU by writing it to the memory mapped locations assigned to
the output buffer on the NIU.  Once the message is completely written,
the processor then writes to some special location to indicate that
the message is ready to be sent.  Since many modern microprocessors do
not preserve ordering on memory operations, care has to be exercised
to ensure that the {\send} command is not seen by the NIU before the
message is fully written to the NIU buffers.  Ensuring correct order
may require execution of processor synchronization instructions.

On receiving the {\send} command, the NIU formats the message for the
network and negotiates with its Arctic to send that message.  The NIU
may support the retransmission of messages to provide fault-tolerance
for the network.  It may also be able to enforce end-to-end FIFO
transmission of user messages.

% start operation: receive side

Receiving a message is trickier than sending one.  Either the NIU must
interrupt the processor or the processor must poll the NIU
sufficiently frequently to avoid buffer overflows.  Interrupts in fast
processors are generally extremely expensive; thus, we will probably
rely on polling to service the network.  A software convention, that
polls sufficiently frequently, will have to be obeyed by {\dP}
threads.  Since we expect the data processors to execute long threads,
even polling can be both expensive and disruptive.  In cases when a
message is detected, even minimal handling may be disruptive, due to
cache thrashing, context switching, etc.

A simple solution to the polling problem is to not accept incoming
messages on the {\dP}.  All messages intended for a {\dP} must be sent
to the {\rP} associated with that {\dP}.  If {\rP}'s are programmed to
execute only short threads, and they poll the network at the
termination of each thread, polling will not be disruptive to the
{\rP}.  However, the {\rP} has to pass on at least some of the
messages to its {\dP}.  Message passing between processors on the same
site can be done via the normal (snoopy) bus-based shared memory.  The
latency to receive a message would be much higher, but the processor
receiving a message would not be forced to poll periodically.  Many of
the returning messages may not require immediate action, such as those
messages that unsuccessfully synchronize.  If an {\rP} is delegated to
performing those tasks, the overhead on the processor receiving the
message is reduced.  Each task passed from the {\rP} to the {\dP} thus
has more ``weight'' and will probably be, on average, a longer thread.
The problem with this scheme is that thread operands must be copied at
least once, from the {\rP}'s cache to the {\dP}'s cache, thus
increasing overall overhead.

Split-phase operations are special cases of the {\start} instruction.
Essentially, a split-phase operation is a {\start} operation from the
request processor to the home processor, and another {\start}
operation from the home processor back to the request processor.
Split-phase handlers must be written to provide the desired
functionality.  Active Messages\cite{active-message} provide a good
abstraction for handling all incoming messages, including split-phase
operations.  An Active Message contains an instruction pointer for a
handler which will process the message.


\subsection{Global caching on {\archname}}

To implement shared memory, we will assume two things: the address
space, both virtual and physical, is partitioned into local and global
memory, and every global address has an owner site, which we will call
the home site of the address.  For simplicity, we will only consider
the case where the home node of a global memory location does not
change during the execution of a program.  However, it should be
possible to build software/OS that supports migration of global memory
addresses at the page level.

The SMU's together with the {\rP}'s implement global caching.  The SMU
detects a memory operation to global shared memory, and carries out
the necessary action to complete the operation.  It must be able to
capture a global address, and format and send the message to
fetch/store the requested/supplied data.  Most of the processing
needed to run cache coherency protocols is done in software on the
{\rP} at the home site.  To the first order, the complexity of the SMU
is not related to the complexity of the cache coherence protocols.

The {\rP} maintains the coherence directory for all the addresses it
owns, runs most of the coherence protocol, and supplies the requested
data or performs the requested write.  Memory for keeping the
coherence directory will be part of the user's virtual memory.
Implementing the coherence protocols in software will allow us to fix
bugs and to experiment with different coherence protocols.

If a global address makes it to the memory bus, the corresponding memory
operation could not have been satisfied in the on-chip cache or the
second level cache.  Completing the operation requires sending a
request to the {\rP} that owns the cache line.  If a reply to the
operation is expected, the SMU receives the reply and puts it onto the
processor bus.  

The SMU behaves like a cache on the processor bus.  In addition to the
tasks mentioned earlier, it keeps track of operations in progress, and
associates some state with each active operation to keep the cache
coherent protocols manageable.  The SMU will also handle cache
coherence requests arriving from the network from the various {\rP}'s,
such as requests to flush/invalidate cache copies of global data.
Because of the need to send and receive remote requests, the SMU will
need network access and will be provided with its own NIU.

\paragraph{Implementing Suspendable Global Loads}

We hope to extend the functionality of our global coherent caching to
allow a thread switch in case of a cache miss.  A cache miss would
effectively be turned into a split-phase transaction; the current
thread would be suspended until the value is returned and another
thread is scheduled in its place.  We call this hybrid approach to
caching the {\em suspending} approach, and name the corresponding load
instruction {\sgload}.  Converting a cache miss to a split-phase
transaction will allow us to cache locations of I-structure memory as
well, and will provide a better means of masking latency.  Without
such a feature, in general, it is not possible to cache I-structure
memory.  Of course, it would be desirable to have the option of using
normal, blocking cache coherency as well as normal split-phase
transactions.  Alewife\cite{Alewife-overall} already has a feature
that allows thread switching on a global cache miss, but since the
switching is done in hardware, only a small constant number of
switches can occur.  Our scheme will allow the user to retain control
over thread switching.

The SMU will support the {\sgload} instruction in the simplest fashion
possible.  If the SMU can notify the user code when a miss has
occurred, the software on the requesting processor can take all the
other required actions.  Since the processor cannot tell if its
{\sgload} request was satisfied from the cache or through the SMU, a
predefined pattern will be used by the SMU to indicate a missing
value.  The software tests the returned value against the predefined
pattern, and switches the thread in case a missing value is detected.
If the processor initiates a split-phase transaction for the missing
value, the scheme can be made to work even if the predefined pattern
is the actual content of the requested location, since the handler for
the return of the value will not check the value against any pattern.
The main cost is an unnecessary global cache line fetch.  With the
proper selection of the predefined pattern, we hope to avoid this
problem all together.

Another possible implementation of the {\sgload} instruction could
have the SMU interrupt the processor when a miss occurs.  We expect,
however, that interrupts will be quite expensive.  This solution also
requires the SMU has the ability to interrupt the processor.  If the
miss ratio is very low, however, this scheme will probably perform
better than the first one.

More sophisticated implementations of {\sgload} seem to require much
more hardware support on the processor side.  In one extreme the
processor can provide the illusion of multiple, unlimited number of
register contexts, and switch among them transparently.  However,
since we cannot modify the processor, we will not explore these
variations here.

Our {\sgload} implementation is very much a hack made necessary by our
need to use a stock microprocessor.  Performance will be far from
optimal, since each {\sgload} must be checked at some point to make
sure the obtained value is valid.  It is also possible for the test to
fail, if the value is actually the test pattern.  The implementation,
however, will allow our ideas for caching I-structures to be tried
without changes to the microprocessor core and the on-chip cache.

\subsection{Alternative Site Configurations}

Up to this point, we have assumed that there are exactly two
processors per site and that both processors have NIU's.  It is
possible that there may be more processors per site, and that not all
processors will have NIU's.  If there are more than two processors per
site, but all processors still have NIU's, {\archname} can run pretty
much the same as described in the previous sections.  The correct mix
of {\dP}'s and {\rP}'s will have to be determined, but the ratio is
changeable in software. 


\begin{figure}
\illustrationpercent{start2a}{50}
\caption{An alternative {\archname} site}\label{fig:start2a}
\end{figure}

If there are processors that do not have an NIU, certain problems
arise.  Such a configuration is shown in Figure~\ref{fig:start2a}.
There must be at least one processor per site that has an NIU to
communicate with other processors.  {\rP}'s must have a NIU, to
perform their duties; thus, at least one of the processors with an NIU
will be assigned to being the {\rP}.  The SMU's NIU will probably be
usable as well in this case.  A processor without an NIU cannot send
or receive messages directly, and must rely on an {\rP} or the SMU for
messaging capabilities.  All message traffic must go through the
snoopy bus, however, further degrading performance.  A processor that
wants to send out a message in this case would write out a message
using normal snoopy bus memory writes, then writing a ``send'' signal,
again on the bus, to indicate that the message is fully formatted and
ready to send.  Again, writing out messages from a processor to the
snoopy bus is not straightforward, due to the fact that the issue
order of the writes may not be the order in which the stores are seen
on the bus.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%----------------------------------------------------------------------------
%\subsection{The New Start Model}
%----------------------------------------------------------------------------

%As mentioned, global cache coherent shared memory will also be
%provided.  Most likely, both strong and weak consistancy models will
%be supported.  In a basic form of cache coherent global memory, the
%requested value is automatically loaded directly into a register and
%the local cache. This eliminates the split-phase overheads like thread
%switching, synchronization, and motion of the requested value through
%the memory hierachy.  Global cache coherent shared memory greatly
%reduces the latency of accessing a global location when there is good
%locality. It also reduces network traffic and home location memory
%traffic.
%







