%%------------------------------------------------------------------------
\section{Related Work}
%%------------------------------------------------------------------------
\label{sec:related-work}
%%------------------------------------------------------------------------

In this section, we compare \start/'s \ccdsm/ implementation to that
of other similar machines, including the Stanford \dash/, the MIT
\alewife/, and the Stanford \flash/.

%%------------------------------------------------------------------------
\subsection{Comparison with the Stanford \dash/}
%%------------------------------------------------------------------------
\label{sec:dash}
%%------------------------------------------------------------------------

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 by code executed on the processors for message passing.
%Figure~\ref{fig:dash-site} shows a site in \dash/.

The biggest difference between \start/ and \dash/'s \ccdsm/
implementations 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.  We
have suggested in Section~\ref{sec:performance} that through the
use of localized global pages we may be able to ameliorate this
disadvantage in programs that exhibit favorable access patterns.

The implementors of \dash/ are well aware of the potential for
deadlocks.  As reported in \cite{Lenoski90}, the approach taken
is to fit the protocol messages into the two categories, request and
reply, and to use two networks.  It was not stated very clearly in the
paper, but buffering space seems to be associated with the network,
giving rise to 4 categories of buffer space for protocol processing: 
(1) request send; (2) request receive; (3) reply send; and (4) reply
receive.  Unfortunately, the presence of flush results in request
messages giving rise to request messages.  The approach taken in
\dash/ is to use time-out when a request that is being
forwarded cannot be sent out after a certain amount of time, and retry
the original request.  While this approach breaks the deadlock, there
is no guarantee that livelock does not results.  The approach that we
described in this paper, of using more categories of buffering, and
multiplexing of different types of requests over one request network
through the use of retry, will not have such problems.  

%%------------------------------------------------------------------------
\subsection{Comparison with the MIT \alewife/ and the Stanford 
\flash/} 
%%------------------------------------------------------------------------
\label{sec:alewife&flash}
%%------------------------------------------------------------------------

The MIT Alewife and the Stanford \flash/ machines are very similar in
terms of the placement of hardware to support \ccdsm/.  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 controls
access to the PCI peripheral bus too.  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 four to five years, while the MAGIC chip is currently
under development.  It will have about 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.

Like all other \ccdsm/ implementations, deadlock, particularly from
lack of buffer space, is possible for both machines.  \alewife/
assumes infinite buffer space in the network\cite{Agarwal91}.  They
``implemented'' this by timing out and interrupting the processor when
the a network (NIU) send queue has been full for a while.  The
processor then uses main memory to provide more buffer space.
However, any such extension will only provide a finite amount of
buffer space, particularly since \alewife/ does not support virtual
memory.  While it may be the case the deadlock does not arise very
often, there is no guarantee that it will not happen.  

The description of \flash/ in \cite{Kuskin94} talks about deadlock
problems in some detail.  It is based on the approach in \dash/ but
with a fair amount of extensions.  Separate request and reply networks
are used, as in \dash/.  In addition, they attempt to have request
messages indicate the resources it needs so that MAGIC can selectively
service those messages whose resource requirements can be met.
However, this choice is only limited to those messages that have
already been accepted into the message receive buffer space in MAGIC.
MAGIC can also backed theses schemes up with software buffers.  They
can use the scheme suggested in this paper of maintaining different
categories of software buffer, but this was not mentioned in
\cite{Kuskin94}.  They did talk about using negative acknowledgement,
but without keeping different categories of buffer space, it is not
clear that the system is guranteed to be free of lack-of-buffer
deadlock.


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