%%------------------------------------------------------------------------
\section{Cache Coherent Distributed Shared Memory on \start/}
%%------------------------------------------------------------------------
\label{sec:start-goals}
%%------------------------------------------------------------------------

\outline{Design philosophy of \start/}

\start/ is a medium size parallel machine built by augmenting
commercial SMPs with hardware to provide MPP class message passing and
experimental \ccdsm/.  The design of \start/ takes a layered approach,
with a collection of commercial SMPs forming the bottom-most layer.
Message passing is next built on top of this bottom layer.  Finally,
\ccdsm/ support forms the top layer and relies on the message passing
capability for its implementation.  The design philosophy of \start/
is to reduce the development effort by capitalizing on commercial
systems, and only extending effort to provide the facilities that turn
the basic building blocks into a parallel machine.  It is hoped that
such an approach will result in a machine that is cheap and that
delivers competitive performance.

Each SMP building block in \start/, called a {\em site}, supports four
processors connected via a snoopy bus.  Figure~\ref{fig:start-site}
shows the block diagram of such a site.  The white blocks of the
diagram are parts of the base commercial system, while the additions
to make it a parallel machine are shaded.

\outline{Message passing facilities in \start/}

Message passing capability is layered above the collection of SMPs by
adding hardware that supports high bandwidth, low overhead and latency
user-level message passing.  This is done through a fat tree network
built out of custom routing chips, the ARCTIC router\cite{Boughton94}
developed in our research group.  Every processors has direct access
to the network through a Network Interface Chip (NIU) that hangs off
the processor's L2 cache and coprocessor interface.  At this level,
\start/ looks like a message passing machine.  

\outline{\ccdsm/ support on \start/}

Support for \ccdsm/ is then built on top of the message passing
facilities with the addition of minimum amount of custom hardware.
The only hardware addition is a simple device called the Address
Capture Device (ACD) which provides the L3 bus interface of the
\ccdsm/ system.  As the name suggests, the ACD's primary task is only
to capture transactions on the L3 bus that involves globally shared
memory.  It relies on a generic processor on each SMP site, called the
service processor(sP), to perform most of the protocol processing.
The sP on different sites communicate among themselves using the
message passing capabilities that is already present in \start/.

Communication between the ACD and sP at the same site occurs mostly
over the L3 bus.  The ACD also has a single bit line into the sP's NIU
that triggers servicing of the ACD by the sP when the line is
asserted.  This choice, as opposed to providing another path of
communication between the ACD and the sP, for example through the sP's
L2 bus interface, is for ease of implementation.  The L2 bus interface
has very strict electrical requirements and it is not quite possible
to hang that many devices on it.  The number of pins that the ACD
would need in these more aggressive designs will also be substantial.

\outline{\start/'s view of memory space}

\start/ supports the notion of dividing the address space
into local and shared memory, where local memory cannot be accessed
from a remote site through normal load/store operations.  \ccdsm/
deals only with shared memory and hence the ACD is only involved in
operations to this address space.  This division of memory fits most
programming models nicely, with code and (stack) frame memory residing
in local memory, and heap objects in shared memory as they are the
data structures that are often shared between different (and parallel)
parts of a program.  In addition, the division allows servicing of
cache misses to local memory to proceed very quickly, independent of
the \ccdsm/ system.  

\outline{Comparison with other \ccdsm/ implementation: \dash/}

It is instructive to compare \start/'s \ccdsm/ implementation to that
of other similar machines, such as the Stanford \dash/, the MIT
Alewife, and the Stanford \flash/.  

Stanford's \dash/ is very similar to \start/ in that it connects
together a collection of SMPs.  However, \dash/ only provides shared
memory and not message passing capabilities.  A network is still
needed for shared memory communication, but this is not directly
accessible for message passing.  Figure~\ref{fig:dash-site} is shows a
site in \dash/.

The biggest difference between \start/ and \dash/'s \ccdsm/ lies in
the implementation strategy.  \ccdsm/ in \dash/ is provided with
dedicated hardware that implements the directory and all the protocol
processing in hardware.  Directory memory is provided with special
fast memory on a board that also houses the protocol processing
hardware.  The board communicates with the SMP bus on one side, and a
2D mesh routing network on the other side.

From a logical point of view, the important difference is that once a
request, for example a cache line read request, is captured from the
snoopy bus in \dash/, the shared memory board takes care of all the
processing without having to go over the local snoopy bus again until
a result is returned.  It may have to send a request to a remote
site's shared memory board, which then accesses memory over the remote
site's SMP bus.  However, none of this requires crossing the local
snoopy bus.  In constrast, \start/'s implementation requires crossing
the local L3 bus multiple times during the processing of any bus
operation to shared memory.

Another important difference is that on \dash/, access to shared
memory that happen to reside on the same site as the requestor can
happen directly to memory, unless coherence action on remote sites are
needed.  In contrast, because directory information is managed in
software by the sP on \start/, all accesses to shared memory, even
resident shared memory, has to go through the local ACD and sP.  
(In Section~\ref{sec:performance}, we will suggest ways of improving
it when the program exhibits certain favorable access patterns.) 

\outline{Comparison with other \ccdsm/ implementations: Alewife and
\flash/} 

The MIT Alewife and the Stanford \flash/ machines are very similar in
terms of the place where the \ccdsm/ support is added.  In both cases,
this is placed in the memory controller sits at the cross-road between
the processor, main memory, and network.  Figure~\ref{fig:alewife}
shows the block diagram of an Alewife node, while
Figure~\ref{fig:flash} shows that of Flash.  In the case of Alewife,
the memory controller, which they called CMMU, also controls the off
chip L1 cache.  For \flash/, the chip is called MAGIC, and also
controls access to the PCI peripheral bus.  The \ccdsm/ support on
Alewife and \flash/ differs in that in the case of Alewife, most of
the support is provided in hardware, although it is possible to
interrupt the processor to provide further processing.  In \flash/,
MAGIC includes an augmented RISC core and all processing is under
software control.

Interesting features of this placement of the \ccdsm/ support include:
\begin{itemize}
\item 
Accesses from remote sites comes into the CMMU/MAGIC chip from the
network, and has direct access to the main memory.  In certain cases,
coherency action has to be done to the local processor's cache, but
this is not always needed.
\item 
All accesses to memory has to go through the CMMU/MAGIC chip.  Thus
this path has to be very fast when no coherence action is needed since
there is no notion of local memory.
\end{itemize}
In general, this approach provides a more integrated way for
supporting \ccdsm/, and will probably yield better performance.
However, it requires extensive development effort.  Development of the
CMMU chip took many (4 or 5?) years, while the MAGIC chip will be a 6
million transistor chip, about as big as the processor that it
supports.  Machines built this way also have to be built from scratch.
In \start/, we would like to build our system with entire SMP as the
building block.  This design point is therefore not available to us.

\outline{Why do we choose to implement \ccdsm/ on \start/ this way?}

\ccdsm/ is provided on \start/ as an experimental feature.  We are
interested in finding the cheapest way of providing \ccdsm/ on \start/
kind of setting, where the commercial building block imposes strict
constraint on what can be done.  For a very low cost, this
experimental implementation will allow us to learn much about
\ccdsm/ in general.  As this paper shows, the work is already yielded
better understanding.  We are also interested in exploring the virtual
memory management (VMM) aspects of \ccdsm/.  Unlike traditional shared
memory machines, where the entire machine runs one copy of OS, we
would like each site of \start/ to run its own copy of OS.  There are
many reasons for doing this, including better fault tolerant behavior.
Coordination of VMM across multiple sites, and scheduling of work
across multiple sites will be done as a layer on top of the per-site
OS.  \start/ will provide the platform for pursueing this research
work.

It will also be interesting to see what sort of performance we can get
out this extremely low-cost implementation.  Although there are some
doubts about the performance of \start/'s \ccdsm/ implementation, we
will suggest in Section~\ref{sec:performance} some ways of improving
the performance.  Even if the performance turns out to be lack lustre,
we will learn what are the important sources of overhead, and provide
better implementations in the future.

\outline{Now, let's transition to the next section}

In this section, we have provided a brief overview of \start/ and its
\ccdsm/ implementation.  We also provide the motivation for taking our
approach.  In the next section, we will look at the hardware deadlock
problems that can occur in incorrect \ccdsm/ implementations.  

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

