%%------------------------------------------------------------------------
\section{The Design of \start/}
%%------------------------------------------------------------------------
\label{sec:start-design}
%%------------------------------------------------------------------------

This section gives a brief description of the \start/ hardware and
how we plan to support global cache coherence.  A block diagram of a
\start/ site is shown in Figure~\ref{fig: start}.  A site consists of
a slightly modified commercial SMP (unshaded in the diagram) built
from PowerPC 620 processors.  One modification is the addition of a
network interface unit (NIU) to each processor.  Each 620 is connected
to an NIU through its L2 cache interface.  The NIU is being designed
and implemented by Motorola and its partners and was heavily
influenced by the MSU functional unit of the
88110MP\cite{Papadopoulos93}.  The NIUs provide access to a Fat-tree
network built out of Arctic\cite{Boughton94} routing chips.  Currently
under development at MIT, the Arctic router is a 4x4 router that
provides 200 megabytes/sec/link bandwidth.

In addition, an address capture device (ACD) is added to the coherent
interconnect to help support \ccdsm/.  When the machine is running in
the mode that supports global cache-coherence, a 620 from each SMP,
which we call the service processor (\sp/), is dedicated to running
the coherence protocol.  The rest of the processors, which are used
for computation, are called data processors (\dP/).  Parallel programs
running on
\start/ can communicate through both message passing and shared
memory, whether they are executing on one site or across multiple
sites.

\begin{figure}
\illustrationpercent{jhoe-start}{50}
\caption{\start/ block diagram}\label{fig: start}
\end{figure}

%\subsection{Network and Network Interface Unit}


\subsection{ACD}

%A block diagram of the ACD appears in Figure~\ref{fig:acd}.  

The ACD has three basic functions: (i) ``capture'' global bus
transactions and pass it to the \sp/, (ii) allow the \sp/ to return
data to the requesting processors, and (iii) Invalidations.  Capturing
means to recognize a global memory transaction, store away a complete
copy of the transaction (including the address, transaction type and
bus tag to return a value if necessary) and respond accordingly to the
processor that initiated that transaction.  If the ACD buffers are
full, \ie, have not been emptied by the \sp/, it forces the processor
to retry the transaction.  Because of limited ACD buffering, the \sp/
should remove captured transactions as quickly as possible.

The ACD can be instructed by the \sp/ to selectively flow-control
(retry) certain types of transactions.  This is needed for buffer
management because the ACD hardware buffers are backed by software
buffers under the \sp/'s control.

The ACD also performs Invalidations (flush bus operation).  It has
hardware support that allows it to interleave a Flush operation with
the other functions it performs.  We will examine the reasons for
having the ACD do the Flush bus operation in Section~\ref{sec:flush}.

%\begin{figure}
%\illustrationpercent{acd}{50} 
%\caption{ACD Block Digram}
%\label{fig:acd}
%\end{figure}

It is possible to build the \sp/ into the ACD or provide some
dedicated path between the two.  Either design requires substantially
more hardware than our design wherein the \sp/ communicates with and
commands the ACD over the SMP bus.  In the current design, the ACD has
a one bit line to the \sp/'s NIU, allowing the \sp/ to poll its NIU
for ACD events.

\subsection{Supporting CCDSM with the ACD and \sp/}

%\subsubsection{ACD Global Address space}

The address space in \start/ is divided into four disjoint parts: (i) \dP/
local; (ii) \dP/ global; (iii) \sP/ local; and (iv) ACD command
spaces.  The \dP/ local space is private to each site, directly
accessible by load/store operations only from the \dP/s of that site.
The \dP/ global space is the address space supported by \ccdsm/.  Bus
operations to this address space are captured by the ACD.  The global
physical address that is seen by the ACD is not really a physical
address but encodes information that will allow the \sp/ to get to the
real physical address of the cache-line.  We call this address a {\em
virsical} address.  Part of the virsical address indicates the current
home site and the rest of the virsical address is a virtual address in
the \sp/ local address space of the home site.  Finally, the ACD
command space is used by the \sP/ to communicate with the ACD.

The ACD and the \sp/ support CCDSM as follows.  When a processor
accesses a global location and misses in its cache, the request
propagates to the memory bus and is captured by the ACD.  The ACD then
signals the \sp/ by setting a bit in its status word as well as
asserting a line connected to the \sp/'s NIU.  The \sp/ either polls
the ACD directly or through the NIU.

The \sp/ then reads out the captured transactions, clearing the
transactions from the buffers.  
%The \sp/ will inform the ACD of the types of bus transaction to be
%retried, if necessary.
%
%We plan to implement an inclusive L3 cache in software for performance
%and correctness.  
%
The \sp/ will take appropriate action to satisfy the request by
checking an inclusive, software L3 cache which it maintains, and
sending messages to the home site if necessary.  The \sp/ will also
serve as a protocol processor, receiving messages from other sites
requesting cache-lines whose home is its site.  It is important,
therefore, for an \sp/ to continue to serve incoming requests even
though it has outstanding requests.  When the response to the remote
request returns, the \sp/ updates whatever state it needs to,
including L3 cache state, and returns the data through the ACD to the
requesting processor.

\subsection{Planned Features}

We plan to try the following ideas in the implementation of \ccdsm/ on
\start/.  

\header{Software L3 Cache:}
%
A large software L3 cache, implemented in main memory is essential to
the design.  The \sp/ can implement an inclusive software cache which
stores all remote data brought to the site.  Various, caching strategy
can be implemented at this level, including automatic prefetching,
presending and update protocols.

\header{Split-phase Cache Accesses:}
%
During a {\em split-phase} cache access, a processor switches threads
when an access to global memory misses in its cache.  The tough part
is how to indicate that there was a cache-miss.  We plan to implement
this idea by having every load of global locations checked against a
``miss pattern''.  The miss pattern would be returned by the
\sp/ to the requesting processor after not finding the desired
cache-line in its L3 cache.  If a load returns a miss pattern, a
cache-miss is assumed and the current task is swapped out.  Part of
the swap-out would be a request to fetch the cache-line.  A
microthread descriptor (an instruction pointer/frame pointer pair),
which would allow the task to restart, would be included in that
request.  The cache-line could be delivered to the requesting
processor's \sp/ for insertion into the L3 cache, while the desired
value sent directly to the requesting processor along with the
microthread descriptor.  When the desired value returns to the
requesting processor, the thread wakes up, and continues with the
value it requested.  If another processor requests the same cache-line
in the near future, the \sp/ can satisfy the request directly from the
L3 cache.

\header{Supporting Coherence from Page Level to Cache-line Level:}
%
During the time when a global page is accessed by only one site,
``localizing'' the page temporarily allows cache miss processing to
by-pass the ACD and \sP/, resulting in a lower cache miss penalty.
``Localization'' is achieved by incorporating Virtual Shared
Memory\cite{Li86} techniques.  A global page can either have its
coherence managed at the page-level or cache-line level, with dynamic,
and possibly automatic, switching between the two schemes based on
access patterns.

\header{Integrating I-structure Semantics into Cache Coherence
Protocols:}
%
Our research language relies heavily on I-structures\cite{arvind90},
data-structures with synchronizing semantics.  These are write-once,
read-many-times memory locations that allows reads to be issued before
the locations are written.  Since they never need to be invalidated
unless storage is reused, coherence protocols for these locations may
become significantly easier.  We plan on investigating these and other
custom protocols tailored for specific applications.

%%------------------------------------------------------------------------
%%                              Section End
%%------------------------------------------------------------------------
