%%!!----------------------------------------------------------------------

\section{Introduction}


\header{Coherency: why?}

Cache-coherent global shared memory is a desirable feature for
distributed-memory machines.  It makes programming easier and
automatically exploits locality if present.  hardware support for
caches found in virtually all current processors, research or
commercial.

Hardware support for coherency is provided at two levels: at
page-level granularity or at cache-line-level granularity.  The two
sizes are supported by most processor hardware.  Of course, other
granularities can be supported but will have to be supported in
software unless with a custom architecture.  In this paper, we are
concerned with cache-line granularity

\header{What is coherency?  Explain basic directory CC}
\header{CC protocols are complex, implying software}
Efficient cache coherency protocols are very complex and are difficult
to prove correct.  For most, if not all, modern designs, the protocol
processing (maintainence of the directory) is done in software.  We
call the processing elements that perform protocol processing,
protocol processors or pP for short.  

\header{How is it supported on StarT, high level}
\header{Simple ACD + stock processor}
Less aggressive but much cheaper implementations coexist on the bus
with the memory controller.  A small piece of hardware (called the
address capture device or ACD) captures addresses destined for global
memory and finish the transaction for the computation processor.
Again, a protocol processor as well as some sort of processor to
support the hardware that captures the addresses must be provided.
Machines of this class include Stanford's DASH and MIT's \start/.  Of
course, within this range there are different levels of hardware
commitment.  \start/ will actually use a peer computation processor as
the pP and the service processor for the the ACD.  DASH had a special
``processor'' on the same board as the ACD.

\header{Correctness, deadlock problems}
\header{Map to other architectures: Efficiency}
\header{Custom pP (Flash, Dash, Alewife}
There is a wide spectrum of hardware support for global cache
coherency.  The most aggressive implementations build special hardware
that provides a direct interface between the computation processor and
the protocol processor.  The hardware looks like a memory controller
to the computation processor and is augmented with network capability.
Generally the pP is integrated into that piece of hardware itself.
Machines that use such an architecture include MIT's
Alewife\cite{Alewife} and Stanford's Flash\cite{FLASH}.

\header{any others???}
Of course, other implementation strategies exist.  For example, if one
had fast interrupt capability\cite{Henry} and had a cache miss trigger
such an interrupt, cache-line misses could be treated the same as a
page fault.  

In order for cache-coherent shared memory to be supported efficiently
on a distributed-memory machine, very efficient, small
granularity message passing must be supported.

\header{Focus}
This paper will focus on cache-coherency support provided at the
memory bus level and thus will not address other solutions.


%%------------------------------------------------------------------------
\section{\start/ description from SM point of view}

\start/'s support for cache-coherent shared memory is minimal, as its
purpose is mostly for experimentation rather than raw performance.  As
we briefly mentioned in the previous section, \start/ has a hardware
device, called the address capture device or ACD, which sits on the
memory bus (see Figure~\ref{fig: acdconfig}.)  Each {\em site} of
\start/ will have such a device.  A site is the basic SMP building
block of the \start/ machine.  Global memory is mapped to the ACD, so
all global accesses that do not hit in the processor's cache will be
captured by the ACD.  The ACD has very limited buffering, so any
transactions that would overflow a buffer will be retried by the ACD.

\begin{figure}
\illustrationpercent{acdconfig}{80}
\caption{\start/ site configuration}\label{fig: acdconfig}
\end{figure}

Since the ACD is extremely simple, it has no ability to send messages
or do any protocol processing.  It cannot read any memory.  It only
has a single-bit line which is connected to the NIU of a 620 processor
on the same bus.  That processor, called the service processor or
\sp/, is assigned the task of servicing the ACD and will probably be
delagated to do protocol processing as well.  The ACD raises the
line when it captures an event.  The service processor then reads the
event from the ACD, does the appropriate actions to service the
request (which may include checking an L3 software cache and sending
messages), then returns the desired cache-line by writing it into the
ACD to be returned.  The ACD essentially allows us to break
abstraction, letting a processor actually see bus transactions and
return results to pending bus transactions.

The interesting point to note is that the service processor is a peer
processor on the same bus as the ACD and the computation processors.
In fact, if coherent shared memory is not necessary, that processor
can be used as a normal computational processor.  The service
processor and the ACD actually communicate over the memory bus as
well.  Though this limitation makes the system as simple as possible,
it also causes us a few problems. ** where should we list those
problems?  What are they? ***  Using a peer processor is also very
troublesome, since the peer processor obeys certain rules which are
not befitting a standard protocol processor.

\subsection{620 split phase bus (generic description)}

In order for us to implement such a scheme, we depend on the 620's
split-phase bus.  As described in Section~\ref{sec: smsupport}, a
split-phase bus splits all transactions that require a data response
into two parts: the request and the reply.  Requests can be retried,
while replies cannot.  Once a request is issued and accepted, the bus
is allowed to be used by other bus entities.

Clearly, the bus is arbitratied by an entity other than the processor
itself.

\subsection{Multiple Finite Buffers}

The 620 also has multiple, but finite buffers for loads and stores,
which allow it to have multiple outstanding read and writes to memory.
This allows the processors to make better use of the memory bus and
the 620 core, since it allows some elasticity between memory accesses
by the 620 core and the availability of the memory bus.  The memory
accesses can be reordered, that is, the order in which the buffers are
filled is not necessarily the order in which they appear on the bus.

Since buffers are not reserved for specific purposes, however,
operations can block other operations.  For example, if write-backs of
dirty cache-lines are filling up the store buffers of processor $a$
waiting for the ACD to free up, and the service processor wishes to
read a memory location that is modified in the cache of processor $a$,
deadlock will occur, since service processor cannot get the desired
data until processor $a$ can free a buffer.  The service processor
needs to read the ACD in order for the buffer to be freed.

\subsection{Weak consistancy}

The 620 implements {\em weak} consistancy, rather than sequential
consistancy.  Since load and store operations may be reordered within
the load and store buffers, sequential consistancy is not maintained.
Software needs to cooperate by inserting synchronization instructions
when necessary to ensure sequential consistancy.  Since
sequentialization instructions are expensive, we wish to use them as
little as possible, enticing us to try to live within a weak
consistancy model of memory.

\subsection{Advantages and Disadvantages}

This solution is extremely simple --- the bare essential hardware for
providing cache-line level cache-cohereny across distributed memory is
provided and the rest of the solution is implemented in software.  The
advantages and disadvantages to this scheme are obvious.  Clearly, the
hardware is almost trivial to design and build.  The software is not
so difficult to write, making the implementation very cheap.  The
disadvantage, of course, is performance and the dedication of one
processor to be used as a service processor.  The system we are
planning to use, however, will have a minimum of 1 megabyte of cache
per processor (probably more like 4 megabytes per processor) and a L3
software cache should contribute to very small miss rates.  Aggressive
prefetching could also help tremendously.  It is currently unclear how
well our scheme will perform.

%%------------------------------------------------------------------------
\section{Deadlock issues in coherency processing}
\subsection{microprocessor view of memory: sink and source}

During the course of \start/'s shared memory design, we repeatedly ran
into deadlock problems which seem to have arisen from either OS or 620
specific problems.  However, these problems can ultimately be traced
to our breaking the memory abstraction that the designers of most
microprocessors, including the 620, assume.  The key to this
abstraction are the assumptions that:
\begin{itemize}
\item{Memory is a {\em sink}, \ie cannot be blocked.  Once a memory
request is fully submitted to the memory system, the memory system
will deliver a result in some finite time.  The memory system is
permitted to retry a transaction if it is out of buffer space, but
forward progress must always be made within the memory system.  }
\item{Blocking bus operations must have a dependence path that
ultimately leads to one or more non-blockable sources that can {\em
always} reply.  
}
\end{itemize}

In order for us to demonstrate that {\em any} ACD design is deadlock
free, we must show that all memory requests, especially the ones
destined for the ACD, have a non-blocking path to some sink.  The rest
of this document is organized as follows.  Section~\ref{sec: basic
model} describes the abstract components that make up our model and
how the model works.  Section~\ref{sec: proof} proves that the model
is deadlock free for a variety of circumstances.  Section~\ref{sec:
implementation} shows how the model system may be folded into an easy
to build system which we intend to implement in \start/.

\subsection{possible deadlock on SMP}

*** Boon, what exactly is this section about? ***

\subsection{deadlock on DM systems}

%%------------------------------------------------------------------------
\section{Deadlock-free CCDSM}
\subsection{Base Model}
\label{sec: basic model}

In the context of \start/'s shared memory design, we need to
distinguish very carefully between blocking paths and non-blocking
paths so as to ensure that the above invariants are guaranteed by our
design.  As a reference, we have divided \start/'s support for
coherent shared memory into three pieces as shown in
Figure~\ref{fig:three-parts-sm}.

\begin{figure}
\illustrationpercent{site}{80}
\caption{The base model.}\label{fig:three-parts-sm}
\end{figure}

\subsubsection{Elements of the Basic Model}
The three elements are:
\begin{itemize}
\item{The ACD+NIU element.  This is a non-blocking element which
communicates only with pP's.  It provides the first part of the
non-blocking path for write-backs.  It also provides the first part of
the ReadC, or RWITM requests, and the last part of the reply path for
these requests.

In order to satisfy ReadC and RWITM requests, blocking operations such
as Flushes may need to be performed.  Blocking operations, however,
are isolated from the ACD+NIU stage so that the ACD+NIU is still
non-blocking.

We put the condition that the ACD has separate resources for read
requests, write-backs, and replies.  This separation is essential
because without it, it is possible for a read request to block a
write-back needed to satisfy the read!  We will examine this condition
in more detail later in this document.  I also believe that a separate
buffer is needed for cache-lines to be returned to the ACD's bus
(replies), otherwise a deadlock condition for control of a buffer may
be created.

The ACD is permitted to retry bus operations if it is out of buffers.

The ACD can free a buffer after it sends it to the network if it
desires.  
}

\item{The pP.  This is the only element that ACD+NIU talks to
directly.  The ACD+NIU sends messages to the pP and eventually
receives replies from the pP.  

The pP is also a non-blocking element.  The only memory pP uses is
unshared by other processors, and thus the pP will never be blocked
since memory is a sink.  If the pP cannot complete a transaction
immediately, it must buffer that transaction and switch to processing
other transactions, since the blocking transaction may depend on
future transactions to allow it to complete.

Note that the pP may have to buffer pending transactions, which,
assuming finite buffering, could lead to the pP blocking.  We will
discuss schemes that allow the pP to either always send messages to
the network (network has infinite buffering) or the amount of
buffering is bounded.
}

\item{The cC+NIU.  The cC+NIU is the only blocking element.  It
implements the potentially blocking operation, Flush.  The cC+NIU must
not back up the network when it is blocked.  The cC+NIU must buffer
Flush requests until they can be put on the bus and actually
completed.  The same buffering problem that exists for the pP exists
for the cC+NIU.
}
\end{itemize}

\subsection{How the Basic Model Works}

The basic model is shown in Figure~\ref{fig: model1} and
Figure~\ref{fig: model2}.  A dP on site 1 tries to read a cache-line
whose home is on site 2.  The cache-line is dirty on site 3.  The
following steps are taken to get the cache-line for the requester.

\begin{enumerate}
\item Requester reads a cache-line.  Request shows up on L3 bus.
\item $ACD_{1}$ captures the request.
\item $ACD_{1}$ sends the request to $pP_{2}$.
\item $pP_{2}$ checks its directories, finds that site 3 has the cache-line in a
dirty state and sends a Flush message to $cC_{3}$.
\item $cC_{3}$ performs a Flush on $L3_3$ bus, which could be blocking.  
\item Once the dirty cache-line is pushed-out,
$ACD_{3}$ captures it and sends it back to $pP_{2}$.
\item $cC_{3}$, having performed the Flush on $L3_3$ bus, may send a
Flush done reply to $pP_2$.
\item $pP_{2}$ then returns it to $ACD_{1}$ which then delivers the
cache-line to the processor that desires it.
\end{enumerate}

\begin{figure}
\illustrationpercent{model1}{40}
\caption{Request sent to cC.}\label{fig: model1}
\end{figure}

\begin{figure}
\illustrationpercent{model2}{40}
\caption{Reply returned.}\label{fig: model2}
\end{figure}

If the desired cache-line is shared by one or more sites, and the
request is simply for a shared copy, the home pP will satisfy that
request directly.  If the desired cache-line is shared by one or more
sites and the request is for a writeable copy of the cache-line, the
home pP will invalidate all outstanding copies and return a writeable
cache-line to the requester.  If the desired cache-line is writable by
one processor and the requestor wants a copy, the currently writeable
copy will be flushed back to the home site which will then pass the
cache-line and control of the cache-line to the requester.

In the next section, we will prove that this scheme is deadlock-free.

\subsection{correctness proof}
\label{sec: proof}

In order to prove that our scheme is deadlock free, we have to show
that all paths needed to satisfy any memory request all lead to sinks.
The only component that may deadlock is the cC+NIU, so we will be
focusing on that.  We also have to show that the scheme will not
deadlock or livelock the network.  In order to show that there can be
no deadlock, our proof will first examine the hypothetical situation
where there is infinite buffering in the network.  It is convenient to
view this buffering as appearing at the NIUs which we regard as part
of the network.  With infinite buffer space at the receiver NIU, we
have the property that messages cannot be blocked indefinitely in the
network, i.e.  we do not have the deadlock situation that a message
$A$ is blocked behind another message $B$ in the network, and $B$'s
processing cannot complete because it needs $A$ to be received.  $B$'s
processing can always be suspended and stored in the inifinite size
buffers.

After considering the inifinite buffer case, we will further refine
our model and the proof, making it handle more and more realistic
scenarios where buffering in the network is finite, and message
blocking in the network as described in the previous paragraph may
happen.

\subsubsection{Infinite Network Buffering}

If the network has infinite buffering, it is easy to see that the
scheme is deadlock free.  As long as the ACD+NIU and pP keep on
servicing requests by reading and writing to the network, which is
guaranteed since there is infinite buffering, the cC+NIU part will
eventually be allowed to Flush cache-lines since their corresponding
ACD+NIU's will always be moving.  Thus, all parts of the model get
real work done, indicating that the scheme does not deadlock or
livelock.

\subsubsection{Finite Network Buffering}

%\subsection{Finite Network Buffering: Preallocated Buffers}
%\subsection{Finite Network Buffering: Dynamic Buffer Allocation}


Using flow control and destination buffering, we can guarantee that
all messages have a place to go and thus deadlock will not occur.  Of
course, it is desireable to minimize or eliminate explicit
point-to-point flow control and destination buffering to reduce
overheads.  Completely eliminating flow control and buffering,
however, seems to be impossible.  In this section, we will give basic
buffering schemes that will allow us to show that the model will not
deadlock the network, thus allowing us to prove that our ACD model
will not deadlock as a whole.

The ACD+NIU has a set number of buffers which is defined by the amount
of hardware it has available.  If the ACD should capture a bus
transaction, but does not have sufficient buffering, it will retry the
bus transaction.  Write-backs are sinkable, since they are directed
towards memory.  Reads (which may require a write-back) are limited in
blocking mode and do not affect the ACD buffers (unless there is a
write-back which are sinkable).  If we are running in blocking mode,
there is a small finite number of read transactions that can be
outstanding at any one time (limited to the total number of read
buffers of all 620's in the machine.)  Thus, sufficient buffering for
read requests can be preallocated.  Another solution, of course, is
for the ACD and the pP to communicate about how many buffers are
available.  If the pP has no more buffers available, the ACD could
retry further read requests until the pP has buffers available,
providing flow control.  If a response to the ACD is necessary,
buffering for the response message should be allocated when the
request arrives (you could use the same buffer that was allocated for
the request since the request and reply will never coexist in the pP.)

The pP is the unit which must be most careful about buffering.  It is
clear that the pP-ACD link can either be exhaustively buffered (all
possible buffering allocated) or flow controlled.  The link between
the pP and cC must have either exhaustive buffering or flow control as
well.  Exhaustive buffering is probably impractical, unless the cC is
implemented by a 620 and even then, since the total number of messages
destined for the cC could be as large as the number of cache-lines on
a site.  Clearly some sort of flow control is necessary between cC's
and pP's.  The cC will have to control its buffers by flow controlling
pP's.  This flow control, however, is implementable, and will avoid
having pP to cC traffic deadlock the network.

Since there is no deadlock within the units (ACD+NIU, pP and cC+NIU)
and there are ways to avoid deadlocking the network, we have shown
that the model is deadlock free.

\subsection{mapping to \start/}
\label{sec: implementation}

The \start/ implementation that we are now proposing has only two
elements (as shown in Figure~\ref{fig:start-sm}):
%----------------------------------------------------------------------
\begin{figure}
\illustrationpercent{implement}{80}
\caption{Basic implemenation.}\label{fig:start-sm}
\end{figure}
%----------------------------------------------------------------------
\begin{itemize}
\item{A custom piece of hardware sitting on the PCI chip that
implements the cC and ACD functionality.  However, this does {\em not}
include any NIU capability.  
}
\item{A 620 service processor which serves not only as pP, but also
provides the NIU service for the cC+ACD.  

The service processor will {\em not} at any moment share any physical
memory with the other 620s (dPs) at the same site.  (They can take
turns to access the memory as long as there is a way to ensure that no
concurrent accesses happens.)  This is to prevent the service
processor having to wait for the dPs, e.g. for push-out from the dP
due to a ReadC/RWITM by the service processor.  

The implication here is that while it is probably possible to write
some custom OS to run on the service processor, we will more likely
run it without OS support.  This means either we change/augment the
virtual memory manager in AIX or there is essentially no virtual
memory (just use direct translation) for global memory.  
}
\end{itemize}

We will now show how such a design can be made to respect the
requirements of the base design.  The key is that the various pieces
that are put onto the same entity must be able to non-blockingly
multiplex between its different roles.  

For the cC+ACD, this means that when a Flush is retried, the cC+ACD
must be able to service other requests and not blocked on the Flush.
This includes continuing to accept write-backs, and (just to be safe;
I'm not sure that this is definitely needed) return the data part of
any ReadC or RWITM bus operation.

For the service processor, all the roles multiplexed on it are
non-blocking.  It will have to manage the buffering requirements
stated earlier, but it should not be hard to supply it will a certain
amount of memory, which it divides among its triple roles as NIU for
ACD, NIU for cC, and as the pP.  Because all its roles are
non-blocking, we can view the service processor as time slicing
between its different roles.  



%%------------------------------------------------------------------------
\section{Implementing Deadlock-free CCDSM}

This section discusses necessary hardware features to support global
shared memory.

\subsection{Stock Microprocessors}

Most parallel systems today are built from stock microprocessors.
In order to support cache-coherent distributed shared memory, it is
important that the microprocessor building block has certain features.

\subsubsection{Memory Bus Requirements}

In order for cache-coherent distributed shared memory to be
implemented with stock processors, the processor interface to memory
must have a specific characteristic.  An external-to-the-processor
event must be able to invalidate a cache-line of a processor, even
while the processor itself is trying to do a memory operation.
Without this requirement, the system can deadlock.

To see how such a deadlock may occur, please refer to Figure~\ref{fig:
bus}.  Basically, each processor has issued a read that exists in
Modified state in the other's cache.  In order for either access to be
satisfied, the other must return the cache-line.  Thus, a processor
must allow other operations to occur even though it wishes to read.
The processor cannot be the absolute master of the bus; others must be
allowed to use the bus even though the processor still wants to do a
memory transaction.

\begin{figure}
\illustrationpercent{site}{80}
\caption{Bus Requirements for Deadlock-Avoidance}\label{fig: bus}
\end{figure}

Virtually all modern processors have some provisions for this support.
If a processor is to used in an SMP, cache-coherent setting, it must
follow these guidelines.

There are a few ways to implement such a bus.  One way is to simply
allow an external device retry memory requests that a processor makes.
The semantics of retry must be such that other bus transactions
(notably an Invalidation) can occur before the original bus
transaction is retried.  Using such a memory bus, a device could force
a processor to continuously retry while it is doing the necessary work
to deliver the desired cache-line to the retried processor.

A more elegant solution would be to make the bus completely
split-phased, that is, the request is separated from the reply.  After
a request is issued, other operations that could fetch data from the
requester's cache must be allowed to proceed.  An interesting question
here is what happens if a Read occurs, then a Flush occurs from
another processor to the same location.  A simple solution is that the
Flush is retried by the reader until that reader gets its desired
cache-line.  A better solution would allow the Invalidation to
complete, but having the read be marked and invalidated once the
cache-line returns to it.

\subsubsection{Snoopy bus CC imposes constraints}

\subsection{Support Required for SM}
\label{sec: smsupport}

Clearly, some hardware support is necessary for cache-line
cache-coherency using stock microprocessors\footnote{Of course, the
Wisconsin Wind Tunnel does not add any hardware support to the CM-5,
but uses special hardware only found in the CM-5.}.  The most common
CCDSM hardware replaces the memory controller.  The MIT Alewife
project and Stanford Flash project are both examples of this
architecture.  The memory controller is augmented with a network
interface, allowing it to send and receive messages directly.

Another form of hardware support for CCDSM lives on the bus in
parallel with the normal memory interface.  From this point, there are
two possibilities: the global memory can be mapped into the local
memory, and the hardware will intervene with data if necessary
(Stanford's Dash) or the global memory will be mapped to the hardware
itself, which will then take care of the accesses (MIT's \start/).

Replacing the memory controller is generally a better choice than
putting hardware support on the memory bus in parallel with a standard
memory controller.  The computation processor sees only what the
memory controller wants it to see.  The memory controller also
controls all of the memory resources, making management of those
resources more convenient and centralized.  The disadvantage of such a
scheme is that it is expensive.  The memory controller must provide 
high bandwidth access to the memory as well as process protocols and
provide the networking capability to maintain cache-coherence.  It is,
essentially, the entire support for parallel processing rolled into a
single entity.  Since the modified memory controller must have more
pins to support the network interface, the system board generally has
to be rebuilt.

By putting the cache-coherency hardware on the memory bus, the system
as a whole does not have to change much.  An additional slot with
perhaps some special capbilities (need to be able to map the memory to
it in the \start/ implementation), but generally not a complete board
rework.  It is also possible to get other processors on the same bus
to do some of the coherency protocol processing.  The cost of this,
however, is more headaches, dealing with other entities that may exist
on the bus.  The processor's view of the world, in this case, is not
controlled by the hardware anymore and can get complicated.


%%------------------------------------------------------------------------
\section{Efficient Message Passing}
\header{Try to be terse, cite a lot of stuff.}

In order to be efficient, cache-coherent distributed shared memory
systems must support fine-granularity (on order of a cache-line)
message passing.  Without efficient message passing at this size,
cache-line misses cannot be serviced in a reasonable time, increasing
the miss penalty.

Efficient message passing in this case requires low overheads {\em as
well as} low latency.  Unless a computation processor can switch
threads when missing in its cache, latency matters a great deal.
Latency is a function of the network and thus will not be discussed
here. 

\subsection{NIU placement}

Overheads to access the network are controlled by where the network
interface (NI) is placed relative to the processor\cite{HenryJoerg92}.
There are four places where a network interface can sit (see
Figure~\ref{fig: niuloc}.

\begin{figure}
\illustrationpercent{niuloc}{80}
\caption{NIU Placement}\label{fig: niuloc}
\end{figure}


\header{Register level} 

The best support for sending a message is having an NI integrated into
the processor itself.  Messages are sent by operations operating on
registers.  Machines that have such network support have been built,
notably Monsoon\cite{Papadopoulos90}, EM-4\cite{Sakai89}, MDP\cite{MDP}.  The
88110MP\cite{StarT-88110mp} was a commercial processor that was modified to
have the same level of integration.  All of these machines are
research machines, however.

\subsubsection{Cache-level}

The next best place to put a network interface is at the cache-level.
Though it is not as fast as register operations, cache interfaces
generally can accept input as fast as the processor can write it.
Though processors can generally move more data (by a factor of 2 or
more) via registers than through the memory subsystem, this method is
still quite fast.

Which level of cache the NI sits on also affects latency and
potentially throughput.  In the Alewife machine, the NI sits in front
of the cache, making it the fastest possible of this class.  

\subsubsection{Memory bus level} 

The NI can sit on the memory bus of the processor trying to
communicate.  This scheme, of course, has longer latency than the
previous two, but can be easier to build since memory buses tend to
run at slower speeds than the processor and cache clock rates.  The
memory bus also tends to have relaxed timing constraints.

There are advantages to putting the NI at this level, notably the
ability to do DMA transfers.  By putting the NI closer to the
processor, the processor has to become involved in order to receive
messages (unless there are alternative paths out of the NI to memory.)

It is important to note that for systems that integrate the NI and
service/protocol processor into the memory controller, communication
for the master processor is memory bus level while communication for
the service/protocol processor is generally either register-level or
cache-level.  Thus, sending protocol information and cache-lines are
done in a very efficient manner while sending messages between
computation processors is memory bus level.

\subsubsection{Peripheral bus-level}

The furthest that the NI can sit from the computation processor is on
the peripheral bus.  This placement is by far the easiest to build,
and there are several companies which make products to do
so\cite{Atomic}.  In fact, a simple Ethernet connection is an example
of a peripheral bus network interface.

Peripheral buses, however, tend to be extremely slow to access.

\subsection{Kernel versus user mode}

Messages can be send and received in kernel or user mode.  The
advantage of messaging in kernel mode is simply that protection can be
maintained --- the kernel can make sure a message goes to the process
that should receive it.  The disadvantage of messaging in kernel, of
course, is the high overhead required to get in and out of the kernel.

User mode requires some sort of hardware protection mechanism if more
than one process may be running on a particular network end-point, in
order to maintain protection.  Since user-level messaging avoids
entering and exiting the kernel, however, and avoids checking message
tags (presumably it is done in hardware), it is potentially much
faster.

\subsection{Send and Receive mechanisms}

Making the NI close to the processor is not necessarily a good thing.
The closer the NI is to the processor, the more likely the processor
must spend some of its own time servicing the network.

For example, if the NI is at the register-level, either additional
hardware must be inserted to handle blockages for sending and
receiving messages or the processor itself must handle these problems
itself.  Basically, the processor will have to receive messages from
the network every so often.  If this is not done, the network will
eventually back up and dramatically decrease performance.

One can argue that if the NIU is placed at the memory bus or
peripheral bus levels, either special hardware or another processor
can handle network flow control problems.  The special hardware
handling network access would accept messages to be sent through a
buffer and deliver messages through another buffer.  Since those
buffers can be built in memory and thus be large, the computation
processor can spend more time working and less time servicing the
network.  Of course, the latency becomes longer and overhead becomes
higher, so code that sends and receives messages frequently may find
this additional latency unbearable.  Code that sends and receives
frequently can probably afford to service the network frequently.
Code that only sends large amounts of data infrequently may be better
off with an NI at the memory level or lower.  Of course, if a
processor is dedicated to servicing the network, it may as well live
as close to the processor as possible.

\subsection{\start/ message passing}

\start/'s message passing support is in the form of a network
interface unit (NIU) at the L2 cache-level, the closest that one can
get to the processor core on the 620 processor.  By living on the L2
bus, processors can send messages without interfering with its
neighbors on the snoopy bus.  The latency is also very short.  These
reasons make the 620 L2 interface superior to the memory bus or
peripheral bus for an NIU in our configuration.


%%------------------------------------------------------------------------
\section{Conclusions}

%%!!----------------------------------------------------------------------

\outline{}

Maintaining coherence on distributed machines is challenging 

It is clear that non-blocking actions must be
guaranteed a minimum amount of resources that is not shared with
blocking actions.  As an example, write-backs are non-blocking and
must have a path of resources -- buffering and access to network links
and buses -- from each microprocessor all the way to the main memory
of every site that cannot be blocked by blocking operations.


\outline{Designe of \ccdsm/ have to start with microprocessor's view
of memory.}

The key to this problem is to start with the memory abstraction that
microprocessors assume of all memory.  Simply stated, 
\begin{itemize}
\item 
The memory system is an {\em infinite sink} which will always process
a dirty cache line write-back issued onto the memory bus by the
processor within a finite amount of time.  In particular, it is safe
for a microprocessor to block {\em all} processing, including refusing
to perform snooping by retrying bus operations initiated by other
masters on the bus, while waiting for this to happen.
\item 
Similarly, the memory system is an {\em infinite source} which will
always service a read request and return the requested data in a
finite amount of time.  It is okay for a microprocessor to stop almost
all processing while waiting for this to happen, except that it must
continue to provide snoop responses to bus operations initiated by
other bus masters, and to do so in a way so that these other
operations can make progress within finite amount of time that is not
dependent on the completion of the pending read unless these bus
operations are to the same cache line as that of the pending read.
\end{itemize}
The memory system is permitted to retry a bus operation if it is out
of buffer space.  However, forward progress must be made by the memory
system so that eventually, buffer space will free up and the retried
bus operation can then be accepted.  

\outline{Mention good vs bad semantics of flush/read conflict}

Different microprocessors make slightly different assumptions about
the memory system as an infinite source.  While some stick to the
stronger demand that it is alright for the microprocessor to retry all
other bus operations to the same cache line as the pending read,
others allow a flush request to the cache line to complete, noting
that it does not, at that moment, have a copy of the cache line.
While \ccdsm/ can be implemented for both positions, we will see later
that things are simpler for the \ccdsm/ designer with the latter, more
relaxed position.  Section~\ref{sec:needed-support} discusses some
choices in the snoopy bus protocol that can affect the ease or
difficulty of implementing \ccdsm/.

\outline{Implications of the memory abstraction}

The memory abstraction as described above has several implications.
The first is that it introduces the notion of {\em blocking} vs {\em
non-blocking} actions.  A non-blocking action is one that does not
require any response from any microprocessor in order to complete.
Non-blocking actions include:
\begin{itemize} 
\item
write-back requests from a microprocessor to the memory system; 
\item
return of requested data by the memory system to the requesting
microprocessor.  
\end{itemize} 
In contrast, a blocking action is one that can potentially require
another microprocessor to respond.  These include: 
\begin{itemize}
\item 
read requests from a microprocessor to the memory system; 
\item 
a flush operation initiated by the memory system to recover dirty
cache lines from processors; 
\item 
an invalidate operation initiated by the memory system to recover
remove cache lines from processors.
\end{itemize}

\outline{Avoiding deadlock at the protocol level}

At the protocol level, a \ccdsm/ system has to ensure that dependence
cycles do not form between the blocking operations.  A safe technique
to go about this is to classify the blocking actions into different
categories with a complete ordering between the categories.  A
blocking action in category $X$ can depend on blocking actions in a
category $Y$ only if $Y$ comes later than $X$ in the ordering.  A
blocking action can also depend on any non-blocking action.  This
makes sure that dependence cycles cannot form.

Unfortunately, this technique does not always work because the
decisions taken in the snoopy bus coherence protocol, which we are
taking as given, may prevent such a complete (and hence non-cyclic)
ordering of blocking operations to be done.  A case in point is when
the snoopy bus protocol blocks a flush to a cache line for which some
processor on the bus has a pending read.  A read now depends on a
flush, which can depend on another read.\footnote{For the astute
reader who may be thinking that there seems to be a contradiction
since a read from a site means that the cache line is not present
there while a flush means that the memory system thinks that a cache
line is present at that site, remember that most caches do not report
removal of a clean cache line.}

Such cases can be dealt with by still ordering the actions, but noting
that some actions violate the ordering.  Dynamically checking of the
action that violates the ordering is performed to detect cases where
this may introduce a cyclic dependence.  When such a case is detected,
the action is not carried out, and the \ccdsm/ protocol will have to
handle the situation.  Oftentimes, these checks are tricky because of
race between the potential blocker and the potentially blocked
operation.  Dealing with this efficiently may require the ability to
{\em withdraw} an operation, such as a flush, after the operation has
been submitted for bus arbitration if a read to the same cache line is
detected in the mean time.  The morale of the lesson here is that the
snoopy bus protocol should try to make life simpler for the \ccdsm/
implementor.

\outline{Dealing with deadlocks arising from sharing of hardware
resources} 

The hardware that implements a \ccdsm/ protocol may introduce its own
deadlocks because of sharing of hardware resources.  Hardware
resources like buffer space, and access right to the bus is limited
and has to be shared.  However, in the presence of \ccdsm/, this has
to be done with care to avoid introducing deadlocks.  To address this
deadlock problem, each action, which we have regarded at an abstract
level in the previous section, needs to be broken down into the actual
``steps'' of the implementation.  For example, a write-back which is
non-blocking at the protocol level, is broken down into: (i)
write-back accepted by the \ccdsm/ element on the initiator's site,
(ii) sending the write-back message to the home site, and (iii) the
home site's \ccdsm/ component performing the actual write-back.  The
steps also define a linear dependence between them.  

The detailed actions should again be ordered by their dependences, and
divided into categories.  Again, the goal is to make sure that there
is on cycles in the dependence graph.  The \ccdsm/ hardware has to
ensure that actions in different categories do not share resources in
a blocking manner.  (Strictly speaking, this is only true if the the
set of categories is a minimal set.  We should try to define this
whole thing better, using a partial ordering, and provide more exact
definitions and rules for safe sharing of resources.)  In this
context, we no longer consider ``non-blocking'' actions separately but
just viewed it as a category of actions which happen to be the final
category.

\outline{A quick note about how network is viewed: switching fabric
is non-blocking; think of James' ack/nack style protocol.} 

We have chosen to regard the network fabric itself as non-blocking,
although buffering at the sender and receiver end is limited.  (To
word this differently, we do not consider tree blocking effects.)
This is a convenient abstraction which can be implemented on any
network, even blocking ones, by introducing another layer of protocol
or transforming the cache coherence protocol in a mechanical way via
adding retrys.  \cite{our-network-paper} has a complete description of
how this network abstraction can be achieved.

\comment{The paper is getting disorganized.  The ``guideline'' for
ensuring correctness is not clear cut, and quickly degenerating into
``identify all actions, every single little step, and order them.
Those in the same partial order ``depth'' can share resources.''}

\outline{Let's describe the model now}

The technique that we have described for arriving at a safe \ccdsm/ is
fairly tedious.  This section proposes a model that summarized the
requirement for a typical \ccdsm/ implementation.  The model, shown in
Figure~\ref{fig:model} has three elements: (i) the ACD+NIU; (ii) the
pP+NIU; and (iii) the cC+NIU.  Each element is discussed in detail
below.

\comment{
Several things are very confusing at this point of time:
 (i) the base model as we used to think about it is really meant for
dealing with operations like flush/read that will block a 620 if they
are issued and cannot complete. 
 (ii) the model does not deal with sufficient details; issues like
separating resources for actions in different categories that happen
to congregate at the same element is only vaguely mentioned.  
 (iii) As a result, it is hard to claim that the model, as it is
defined, has general, useful applicability to other \ccdsm/
implementations.  
}

\outline{The ACD+NIU}

The ACD+NIU provides the first part of the non-blocking path for
write-backs.  It also provides the first part of the ReadC, or RWITM
requests, and the last part of the reply path for these requests.


The ACD+NIU is a non-blocking element which communicates only with
pP+NIU's in the system.  


In order to satisfy ReadC and RWITM requests, blocking operations such
as Flushes may need to be performed.  Blocking operations, however,
are isolated from the ACD+NIU stage so that the ACD+NIU is still
non-blocking.

We put the condition that the ACD has separate resources for read
requests, write-backs, and replies.  This separation is essential
because without it, it is possible for a read request to block a
write-back needed to satisfy the read!  We will examine this condition
in more detail later in this document.  I also believe that a separate
buffer is needed for cache-lines to be returned to the ACD's bus
(replies), otherwise a deadlock condition for control of a buffer may
be created.

The ACD is permitted to retry bus operations if it is out of buffers.

The ACD can free a buffer after it sends it to the network if it
desires.  


\outline{The pP+NIU}  

The pP+NIU is the only element that ACD+NIU talks to directly.  The
ACD+NIU sends messages to the pP and eventually receives replies from
the pP.

The pP is also a non-blocking element.  The only memory pP uses is
unshared by other processors, and thus the pP will never be blocked
since memory is a sink.  If the pP cannot complete a transaction
immediately, it must buffer that transaction and switch to processing
other transactions, since the blocking transaction may depend on
future transactions to allow it to complete.

Note that the pP may have to buffer pending transactions, which,
assuming finite buffering, could lead to the pP blocking.  We will
discuss schemes that allow the pP to either always send messages to
the network (network has infinite buffering) or the amount of
buffering is bounded.


\outline{The cC+NIU}  

The cC+NIU is the only blocking element.  It implements the
potentially blocking operation, Flush.  The cC+NIU must not back up
the network when it is blocked.  The cC+NIU must buffer Flush requests
until they can be put on the bus and actually completed.  The same
buffering problem that exists for the pP exists for the cC+NIU.  


There are two ways in which we can use a static dependence graph.  One
is to use it to check if a particular \ccdsm/ is deadlock free.  The
other is a more constructive usage, in which safe sharing of hardware
resources is derived with the help of a static dependence graph.  




\outline{Approach this problem by looking at dependences}

A deadlock in the memory system occurs when dependences between
dynamic instances of memory/coherence operations, which we will call
mc-ops, develop into a cycle.  Our examples of the previous sections
describe sequences of actions that all give rise to a cycle of
dependencies.  

Dependency between mc-ops comes from two sources: (i) logical
dependence, and (ii) dependence due to shared physical resources which
are shared in a blocking fashion.

A logical dependence by mc-op $Op_i$ on mc-op $Op_j$ indicates that
the protocol requires $Op_i$ to wait for $Op_j$.  These are dictated
by the cache coherence protocol and are in general quite few.  An
example is when a cache line read request arrives at the home site to
find that the data is dirty in the cache of a remote site.  The return
of the cache line data to the read request cannot happen until the
dirty cache line has been flushed from the remote site.

\outline{Using the static dependence graph in a constructive way}

While the static dependence graph can be used to check a final design,
it can also be used to derived safe sharing of hardware resources.  We
start with a design where every hardware resource type used in the
protocol is put in a different set.  This set must not have any
cycles, otherwise the protocol itself has to be changed.  We can then
merge the sets when sharing of resources is desired, subjected to the
condition that no cycle is introduced.

\outline{The sequence of action for each operation}

\comment{With rewrite this part later.}

\begin{verbatim}
R-read : directory 
          check
         at home : return data 
                 & send flush : flush remote : return data  
                 & send flush : flush remote :  w-back : returned 
                                                         to home  : return data 
W-read : directory 
          check
         at home : return data 
                 & send flush : flush remote : return data  
                 & send flush : flush remote : w-back : returned 
                                                        to home  : return data 
W-back : directory
          check 
         at home 
\end{verbatim}

\outline{Examples of static dependence graph for previous examples}

First example: (w-back) and (w-read) resources grouped together, forming
cycle. 

Second example: (flush remote) and (return data)

Third example: (returned to home) and (w-back)

Fourth example: This one is much trickier.  It actually introduces an
		extra class of resources, writable-cacheable-OS
     	        data-structure, which has arcs from everything that
		runs on the sP, and is grouped via shared hardware
                buffers to w-back (in the push-out case).  

\begin{center}
\begin{tabular}{|l|p{1in}|p{1in}|p{1in}|p{1in}|p{1in}|p{1in}|p{1in}|p{1in}|p{1in}|p{1in}|}
\hline
  		&\multicolumn{2}{c}{Home}	&\multicolumn{2}{c}{Shared[S]}
		&\multicolumn{2}{c}{Modified[m]}
		&\multicolumn{2}{c}{Flushing-data-pending(p-op,n)}
		&\multicolumn{2}{c}{Flushing-only(p-op,n)}
\\\hline
		& action & next state 		& action & next state 
		& action & next state 		& action & next state
		& action & next state 		
\\\hline
r-read req	& r-read reply	& Shared	& r-ready reply & Shared 
		& flush(m)	& flushing-data-pending(req, 1) 
		& retry op	& flushing-data-pending(p-op,n)
		& retry op	& flushing-only(p-op,n)
\\\hline
w-read req	& w-read reply	& Modified	
		& flush(S)	& flushing-only(req, sizeof (S)) 
		& flush(m)	& flushing-data-pending(req, 1)
		& retry op	& flushing-data-pending(p-op, n)
		& retry op	& flushing-only(p-op,n)
\\\hline
w-back req	& --	& error			& --	& error 
		& write main memory & Home	
		& write main memory; if n=0, reply to p-op & if n=0, then
					 (if p-op = r-read then Shared
							   else Modified) 
				     else flushing-only(p-op,n)
						
		& --	& error
\\\hline
flush ack	& --	& error			&  --	& error
		& --	& error			
		& --	& flushing-data-pending(p-op, n-1)
		& if n = 1, reply to p-op 	& if n = 1, then 
						     (if p-op = r-read
							 then Shared
							 else Modified)
\\\hline
\end{tabular}
\end{center}

\ccdsm/, with the presence of many independent buses, allows
more concurrent requests and actions to be in progress and thus faces
a more complex situation.



Again let us consider a two-processor, two-site system with sites $A$
and $B$, and processors $P_A$ and $P_B$ respectively.  Consider the
following scenario:
\begin{enumerate}
\item 
Processor $P_A$ reads a cache line $x$, which has its home at site
$B$.  It obtains the cache line without problem and puts it in its
cache.
\item 
Next, processor $P_B$ tries to write this cache line.  The directory
at the home site indicates that it has to flush the cache line from
$P_A$, and proceeds to send a flush request to site $A$.  Assuming that
we are implementing sequential consistency, $P_B$'s attempt to obtain
the cache line for writing has to wait for the flush to finish before
continuing. 
\item 
At about the same time, processor $P_A$ tries to write this cache
line, finds that it does not have ownership even though it is in its
cache, and sends a request for ownership to the home site.
\item 
When the flush request arrives at site $A$, there is an outstanding
read request to this cache line.  What should happen at site $A$ now
to deal with this flush request?  
\item
In the mean time, if $P_A$'s read request arrives at the home site, it
will notice that processor $P_B$ is actually trying to obtain the cache
line to do a write, and a flush has been sent to its home site.  What
should happen here?
\end{enumerate}
If we apply the rule that whichever operation reaches the home site
gets to go first, $P_B$'s request should be the one to go first.  How
to achieve this is, however, somewhat tricky.  

The implementation must get site $A$ to relinquish its cache copy and
allow the flush to be completed despite its outstanding ownership
request.  Having done this, site $A$ sends a flush acknowledge to the
protocol processor at $B$, which then allows $P_B$'s read to proceed.
With this approach, $P_A$'s read request can either be buffered
temporarily at site $B$ if space is available, or retired back to site
$A$ if no buffer space is left.

This is not always easy to implement.  Most snoopy bus protocol treats
obtaining ownership as a single step operation on the bus.  

However, most snoopy bus protocol will not allow the flush to complete
while its ownership request is outstanding.  

%----------------------------------------------------------------------

\comment{The rest of this section was ``old'' and has not been
``reprocessed''.} 


Designing a correct \ccdsm/ system is a nontrivial task due to the
many possible concurrent events.  There are two basic challenges
encountered in CCDSM system design: logical correctness and finite
hardware resources.  Categorizing the problems allows the problems to
be examined and solved independently.

Logical correctness challenges are solved under the assumption that
infinite hardware resources, both buffering and blocking hardware, are
available.  Under this assumption, the concurrency of events does not
have to be considered unless the concurrent events interact in a
logical fashion.  Thus, only concurrent operations to the same
cache-line have to be considered.  Logical correctness problems are
discussed in detail in Section~\ref{sec:logical-correctness}.

Given a logically correct \ccdsm/ protocol, the problem of mapping the
protocol onto hardware and firmware remains.  During this process, the
designer has to deal with finite hardware resources, such as
buffering, and the possibility of the network blocking if it is not
used properly.  If the mapping is done incorrectly, deadlocks and/or
livelocks will be introduced.  Mapping a protocol to realistic
hardware is called the finite hardware resource problem and is
elaborated in Section~\ref{sec:hardware-deadlocks}.

%%------------------------------------------------------------------------
\subsection{Logical Correctness of \ccdsm/ Protocols}
%%------------------------------------------------------------------------
\label{sec:logical-correctness}
%%------------------------------------------------------------------------

Logical correctness problems in \ccdsm/ protocols are attributed to
three sources: concurrent initiation of memory operations, the
presence of multiple processors at a sites, and a non-FIFO network.
Only the first problem is found in all CCDSM systems.  In this
section, we will illustrate specific logical correctness problems from
each source, and how they interact to create further complications.

\subsubsection{Concurrent and Distributed Initiation of Memory
Operations} 
\label{sec:cdi-mop}

Concurrent initiation of memory operations is not unique to
distributed systems, but is also present in snoopy bus systems.  On
snoopy bus systems, however, maintaining coherency is simplified since
all operations are serialized on the snoopy bus.  This
sequentialization of bus operations imposes a {\em strict ordering of
memory operations} that is {\em immediately visible to every
processor}.

In the \ccdsm/ setting, it is tempting to view a \ccdsm/ system as a
type of snoopy bus, where bus operations are sequentialized through
sequential protocol processing at the home site.  While this principle
is used in most \ccdsm/ implementations, the problem that concurrent
operations and their {\em serialization through the home site, are not
instantaneously visible globally} still remains.  A snoopy bus
protocol is not sufficient for a CCDSM system.  The next few examples
will illustrate the difficulty of retrofitting a snoopy bus protocol a
CCDSM system.  Examples in this section will assume that each site
(which has a single memory bus) has only one processor and the network
is FIFO.

%%------------------------------------------------------------------------
\subsection{Dealing with Finite Hardware Resource Induced Deadlocks
and Livelocks}
%%------------------------------------------------------------------------
\label{sec:hardware-deadlocks}
%%------------------------------------------------------------------------

Mapping a high level specification of a \ccdsm/ cache coherence
protocol onto hardware is fraught with pitfalls.  It is generally
assumed that correctness at the logical level is the most difficult
part of implementing \ccdsm/.  Avoiding deadlocks in the actual
implementation is also non-trivial because the sharing of hardware
resources introduces dependencies between operations that are
logically unrelated.  The key to a robust solution is to track the
dependences between different types of buffers in the protocol, and
then divide the buffers into separate categories so that the
dependences can never develop into cycles at run time.  Because there
is very limited buffering in the network, we will assume that the
buffering in the network itself is zero and all buffers are under
protocol management at the ends.  The network switch fabric is assumed
not to block\footnote{Certain protocols\protect\cite{Hoe94} provide
guaranteed non-blocking access using a request/reply network.}.

%%------------------------------------------------------------------------
\subsection{\start/ specific \ccdsm/ Issues}
%%------------------------------------------------------------------------
\label{sec:start-ccdsm-issues}
%%------------------------------------------------------------------------


If pages are not migrated, the virsical addresses can remain constant
throughout a program run.  In this case, virtual to physical
translation can be one-to-one and be done with block translation
rather than on a page level.  Our first implementations will probably
not migrate pages to simplify the implementation.  In fact, the very
first and simplest implementation will probably not page at all by
pinning global memory pages down.



 
The memory request must be satisfied in
order for it to be retired.  This implementation decision can cause
problems when coupled with a processor design that does not allow
other bus operations to the same cache-line to be initiated until 
after the first one has been satisfied.  We will see why when
discussing Invalidations in Section~\ref{sec:flush}.

%Using these assumed numbers, the miss penalties from Figure~\ref{fig:
%miss penalties} and numbers from the \flash/ paper, we came up with
%the following graphs.  In Figure~\ref{fig:start-flash} we plotted
%\start/'s performance relative to \flash/'s performance in terms of
%cycles (for absolute performance \flash/ will perform even better due
%to its faster clock rate.)  For a 0.06\% miss rate (Barnes), \start/
%and \flash/ are quite comparable.  Of course, if we hit in the cache
%very often, our numbers should be essentially the same as \flash/'s.
%For a 0.78\% miss rate, \flash/ starts to pull ahead, and by a 6.00\%
%miss rate, \start/ is 70\% slower than \flash/.  In the limit, we
%should be no more than a factor of 3 away from \flash/ performance,
%because all of our penalties are about a factor of 3 away from \flash/
%numbers. 

%%\begin{figure}
%%\illustrationpercent{chart1}{130}
%%\caption{\start/ performance relative to \flash/ performance, where
%%\flash/ is 1}
%%\label{fig:start-flash}
%%\end{figure}

%The next chart in Figure~\ref{fig:start-flash-noglobal}, however,
%shows another side of the story.  This chart plots the ratio of
%\start/ CPI and \flash/ CPI relative to a single processor.  There is
%substantial slowdown for both due to a poor miss rate (6.00\%.)
%Though \start/ runs almost 9 times slower than a sequential processor,
%\flash/ also runs about 5.5 time slower than a sequential processor.
%Therefore, at a miss rate like 6.00\%, one really has to want speedup
%from a particular algorithm to pay that kind of slowdown from {\em
%either} machine.


%%\begin{figure}
%%\illustrationpercent{chart0}{130}
%%\caption{\start/ and \flash/ performance relative to a single processor}
%%\label{fig:start-flash-noglobal}
%%\end{figure}

%These numbers are probably overly pessimistic for \start/ for several
%reasons.  One is that it does not take the SMP nature of \start/ sites
%into account.  This may reduce the number of remote accesses for some
%programs.  It can also be seen that the effective use of the L3 cache
%can change performance by more than a factor of three.  These numbers
%assume that all memory accesses are to global memory.  For \start/,
%misses for local memory has much lower miss penalty.  

%In terms of overall performance, it is clear that unless the miss rate
%is under 1\%, the performance of \start/'s shared memory system is
%quite poor.  We hope that for these programs the use of the
%split-phase caching techniques will reduce the penalties by bounding
%the miss penalty to around 400 cycle range.

Cache-to-cache transfer of \ss/ can be avoided if some form of L3
cache is provided.  Depending on the implementations, either can
perform better than the other.



%Buffering and blocking hardware should be divided in a manner that
%avoids deadlocks.  Using dependency graphs, it is easy to see where
%deadlocks may occur.  Then, either by splitting up groups of buffers
%or by preallocating buffers when required, deadlocks can be avoided.


%%%%%%
%  This stuff doesn't quite fit anywhere

%\begin{figure}
%\illustrationpercent{ccdsm-model}{65}
%\caption{This is a logical model of the various components of
%\start/'s \ccdsm/ at each site.  The shaded pieces indicate the
%different blocking resources.  This model has the dependence graph
%shown in Figure~\protect\ref{fig:flush-ok}.  }
%\label{fig:ccdsm-model}
%\end{figure}

%During the design of \start/, we found the model shown in
%Figure~\ref{fig:ccdsm-model} useful for typical protocols.  It is able
%to accommodate many variations in protocols because most protocols do
%not involve more than three categories of sites: the initiator site,
%the home site, and remote sites.
%
%The division into 3 parts is based on functionality.  The BI
%interfaces to the snoopy bus on the requesters end, the pP performs
%all home site functionality, while the cC performs remote site
%blocking operations.  We have not combined the different parts as any
%combination is either impossible due to hardware constraints (the 620
%cannot act as a BI) or will result in static cycles and hence deadlock
%unless preallocation of resources is done.
%
%This model is mapped on \start/ hardware by having the \sP/ perform
%most of the functionality in a {\em non-blocking} manner.  The \sP/ is
%not given any task that may be blocking.  Access to network always
%goes through the \sP/.  All the buffers are software buffers managed
%by the \sP/ in six different categories (***enumerate categories***)
%to avoid out-of-buffer deadlocks.  The only thing that the \sP/ cannot
%do are blocking operations like Invalidation.  Thus the cC cannot be
%multiplexed on the \sP/ but is instead provided by extra hardware as
%part of the ACD, which also includes the BI.  

%%------------------------------------------------------------------------


%\begin{verbatim}
%* summarize issues in implementing MPP with CCDSM from SMP:
%  2 Categories:
%  - correctness issues: 
%    what the snoopy bus protocol can do to help.
%  - performance issues:
%    what are the parts that if improved will have the most impact 
%    on performance.
%\end{verbatim}

