%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The New Start}
% ----------------------------------------------------------------------------
\label{sec:realizable-machine}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We plan to build another parallel machine in collaboration with
Motorola, *T the Next Generation({\archname}).  The machine design is
heavily influenced by the *T work described in the previous section.
The fundamental difference between the original *T and {\archname},
motivated by analysis similiar to that present in the previous
section, is the addition of coherent caching for global shared memory.
Full messaging support is retained in this new model.

This section will first describe a high level, abstract view of
{\archname}, independent of implementation.  It will then discuss our
thoughts on the actual implementation.  

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

As stated, {\archname} is *T + global cache coherency.  Since
{\archname} is essential a superset of *T, all of *T's functionality
will be available on {\archname}, though the actual implementation may
differ.  {\archname} incorporates the dominate feature of *T, a fast
network interface, which allows us to implement the *T's namesake, the
{\start} operation.  The {\start} operation is a message passing
primative, allowing us to implement virtually any message passing
operation.  We will use {\start}, or some derivative, to implement
split-phase transactions and to communicate between threads.

Multithreading will be supported on {\archname} by the *T {\next}
operation, which terminates the current thread and schedules and
starts another thread.  Multithreading is essential to avoiding
deadlocks and will allow the machine to tolerate latencies.  Of
course, multithreading depends on fast context switching and a fast
network interface.  It is hoped that a combination of hardware and
software mechanisms and compiler support will allow us to context
switch and access the network at an acceptable rate for our level of
multithreading.

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, eliminating split-phase overheads like thread
switching, synchronization, and motion through the memory hierachy of
the requested value.  Global cache coherent shared memory greatly
reduce the latency and overhead of accessing a global location when
there is good locality, reducing network and home location traffic.

Adding cache coherent global shared memory does not create a
fundamental shift in our software model --- coherency has always been
considered an othogonal issue.  Compiler implementations, however,
will have to take this new feature into account.  Global locations
that are known to be already written and will be reused should
probably be accessed through the cache coherency interface, while
locations that do not have good locality should probably be accessed
via split-phase operations.

We hope to extend the functionality of our global coherent caching to
allow a thread switch if there is a miss in the cache.  We call this
model the {\em hybrid} approach.  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 then
executed.  Converting a cache miss to a split-phase transaction would
allow us incorporate synchronizing global memory into caching and
would allow us to better mask latency.  Without such a feature, we
could not, in general, cache I-structure memory that was not known to
already be written.  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} allows switching
threads upon a global cache miss, but since the switching is done in
hardware, only a small constant number of switches can occur.  

% ----------------------------------------------------------------------------
\subsection{{\archname} Hardware}
% ----------------------------------------------------------------------------

We plan to implement the model described above in the near future.  We
are constrained, however, to using an unmodified commercial processor.
All hardware support must be built around the processor and use
existing datapaths in and out of the processor.  We will also try to
minimize the amount of external hardware, using software mechanisms
unless it is absolutely essential to have hardware support.  This
machine design is very minimalistic and thus incorporates a few
compromises.  Since we are still in the design stage, we cannot
describe the machine with total accuracy.  The design specified in
this document should therefore be understood to be a conceptual model
rather than an accurate description of the machine.

The processors used will be members of the IBM and Motorola PowerPC
architecture, due to their strong performance and our association with
Motorola.  The network will be based on the Arctic\cite{artic} chip
designed at MIT.  The basic building block, called a {\em site}, will
consist of several PowerPC processors connected by a snoopy bus to
memory.  A Shared Memory Unit with network access will also sit on the
snoopy bus.  Some set of the processors will have network access via a
Network Interface (NI).

An abstract block diagram of the processing node is shown in
Figure~\ref{fig:start2}.  The diagram shows one possible configuration
of a site.  It consists of two PowerPC processors sharing a snoopy bus
with an SMU and some memory.  One of the shown processors has an NI
attached to it, and is thus called an {\nP}, while the other processor
has no network interface.  The actual number of {\nP}'s per site and
the total number of processors per site is not yet set.  There will be
a minimum of two processors per site.  It is possible for all
processors to be {\nP}'s, that is, they would all have direct access
to the network.  We hope to be able to build sites where all
processors are {\nP}'s, since such a configuration would offer the
highest flexibility.

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



The network interface must be memory mapped, since the significant
datapaths in and out of the processor are memory datapaths.  We hope
to include recovery for network errors into the NI as well.  The NI
will use fixed sized packets and will contain at least some of its own
buffer space.

Some of the mechanisms described in the previous section, such as the
{\start} and {\next} instructions, must be emulated in software, since
we are not permitted to change the processor architecture.  The
network interface should be fast enough to allow us to support the
{\start} instruction reasonably well.  We can, of course, optimize
each instance of the {\start} instruction to execute as efficiently as
possible in its context.

{\archname} supports coherent cached global shared memory with a
minimal amount of hardware support.  The SMU, which provides the
hardware support, is currently designed to be very simple.  Most of
the processing needed to run cache coherency protocols is done in
software at the home site's {\rP}.  The SMU and {\rP} together
provides the coherent-cache shared memory service.  This configuration
allows us to experiment with and debug different coherency
protocols.  The SMU will also support the hybrid {\gload}, but
probably in the simplest fashion possible.

The next few sections describe the SMU, message passing, and using
{\archname} in greater detail.  

\subsubsection{Shared Memory Unit}

The SMU is a device on the processor bus of each site which detects a
memory operation to shared memory, and carries out the necessary
action to complete the operation.  This will usually require sending a
request to the node owning the data, which we will call the home
node\footnote{For simplicity, we will consider a 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 at the page level.}.  If
replies are expected, the SMU receives it and relays it onto the
processor bus.  The SMU is in essence a memory mapped device and local
and global memory space has to be partitioned appropriately, both at
the logical (virtual) and physical level.  This is not difficult to
achieve.

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 on-going operation.  The latter is
necessary for keeping cache coherent protocols manageable.  The SMU
will also handle 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 it with its own
NIU.

The SMU will implement the hybrid {\gload}.  The hybrid {\gload} can
be implemented in many ways, with varying degree of hardware support,
and different resulting characteristics.  The least amount of hardware
needed is the ability to notify the user code when a miss has
occurred; all the other required action can be done in software.  In
the other extreme, the hardware provides the illusion of multiple,
unlimited number of register contexts, and switches among them
transparently.  There are many possible design points between these
two extremes.  We chose the simplest for this instance of the SMU.

The SMU is designed with the ability to return a predefined pattern
for certain cache line read requests to global memory that go on the
processor bus.  This, together with an appropriate software
convention, will allow threads to test for cache misses and switch
thread on miss.  Caching support for I-structures in Id needs this
functionality, which can also be useful for general global memory
accesses. This design is very much a hack made necessary by of our
need to use a stock microprocessor.  Performance will be far from
optimal but will allow our ideas for caching I-structures to be tried
without changes to the microprocessor core and the on-chip cache.

The {\rP} processor on the home node keeps track of the coherence
directory.  It 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 user's virtual memory.

\subsubsection{Split-phase and message passing on {\archname}}

Split-phase operations are special cases of message passing.
Essentially, a split-phase operation is a message from the request
processor to the home processor, and another message from the home
processor back to the request processor.  If all {\dP}'s are also {\nP}'s,
message passing can be performed through the NI of each processor.  A
processor could communicate directly with any other processor, very
quickly.  This method, however, would require each processor to also
poll the network periodically for messages.  If polling is not
performed, the network could become congested or even blocked.

A simple solution to the polling problem, when all {\dP}'s have NI's, is
to send messages via the {\dP}'s NI but receive messages via a {\rP} on the
same site.  The latency to receive a message would be much higher, but
the {\dP} would not be forced to poll periodically.  Many of the
returning messages may not require immediate action, such as those
messages that unsuccessfully synchronize, and thus message traffic
could be handled by the {\rP} and only be submitted to the {\dP} when work
can be done, thus increasing the ``weight'' of the messages actually
received by the {\dP}.

Another method is to have {\rP}'s act as gates to the network by having
the {\dP} send and receive messages through the {\rP}.  This method is
required for message passing when the {\dP}'s do not have NI's.  The {\dP}
would write out a message using normal memory writes, then sending a
``send'' signal to a {\rP}, letting it know that the message is fully
formatted and ready to send.  Writing out messages from one processor
to the other is not straightforward.  The problem lies in the fact
that the order in which data leaves a processor may not be the order
in which the stores were performed.  We believe, however, that the
problem is solvable by a combination of instruction ordering and
snoopy cache coherency.

\subsubsection{Using {\archname}}

Our current thinking divides processors into two groups: {\dP}'s which
are dedicated to running user code and {\rP}'s which are dedicated to
handling split-phase requests for memory and global caching protocols.
In actual implementations, we expect the {\nP}'s to double as {\rP}'s as
well.  If {\dP}'s are provided with NIUs as well, there is no real
distinction between them and {\nP}'s.  The processors at a site
communicate through shared memory via snoopy bus cache coherency.  It
is currently unclear where synchronization will be done.  Performing
synchronization on the {\dP}'s will allow incoming values to be written
into non-shared memory, thus reducing the required cycles to access
memory, but will increase the amount of overhead that must be run on
the {\dP}'s.

In some sense, 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.  A processor 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.  Though the full power of the processor is
not used (notable the floating point), such a design provides
flexibility since software can be changed easily, and avoids the need
to design a separate chip to perform the desired functionality which
would require too much effort.


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

