%%------------------------------------------------------------------------
\section{Issues in Designing \ccdsm/}
%%------------------------------------------------------------------------
\label{sec:ccdsm-issues}
%%------------------------------------------------------------------------

In designing \start/, we encountered a surprisingly large number of
complications from using a processor in the SMP as the \sp/.  In many
cases, the exact nature of the problems is dependent on the
microprocessor bus interface and the design of the snoopy bus itself.
Other problems deal with buffer management and allocation.  In the
following section, we outline the major problems we encountered and
their solutions.  We believe that these problems or the suggested
solutions to them are encountered in most \ccdsm/ implementations
today.

Before we discuss these examples, it should be noted that cache
coherence protocols tend to be quite complex in their actual
implementations.  That complexity is a compelling reason for doing
them in software instead of hardwiring them.  In this paper, we are
not presenting any specific protocols.  However, what the following
examples will illustrate is that without some cooperation from the
underlying hardware, implementing \ccdsm/ will be either impossible,
or so inefficient as to be practically uninteresting.  The following
examples will not describe any complete protocols, but will just show
protocol fragments to illustrate the problems encountered.  Except for
Section~\ref{sec:cmp-non-fifo}, all the sections assume a FIFO
network.

%%------------------------------------------------------------------------
\subsection{Need for a Split-phase Bus in SMP}
%%------------------------------------------------------------------------
\label{sec:sp-bus}
%%------------------------------------------------------------------------

A blocking bus, which locks up the bus until an operation is complete,
can cause deadlocks in a CCDSM system.  This problem is due to
concurrent events that have no immediate knowledge of each other.  For
example, consider processors $P_A$ and $P_B$ at sites $A$ and $B$
respectively.

\small
\begin{enumerate}
\item $P_A$ has $x$ in \ms/ state and now wants to read $y$.  The Read
$y$ request goes on its bus and is accepted.
\item At the same time, $P_B$, which has $y$ in \ms/ state wants to
\rd{x}.  It issues a \rd{x} request which is accepted on its bus.
\item Neither can proceed any further because each request needs to
get the cache-line from the other bus.
\end{enumerate}
\normalsize

A snoopy bus used in a \ccdsm/ system should therefore be split-phase
allowing processors to snoop the bus and service bus initiated
operations while waiting for its own requests to be fulfilled.  It is
true that as long as it is possible to retry bus operations, it is
possible to implement \ccdsm/ using either a blocking or pipelined
snoopy bus protocol.  However, the implementation complexity and the
performance penalty makes either an unreasonable engineering choice.
This was the main reason for us to select an SMP based on PowerPC 620
rather than PowerPC 601.

%%------------------------------------------------------------------------
\subsection{Interaction of Invalidates and Outstanding Reads}
%%------------------------------------------------------------------------
\label{sec:inv-vs-rd}
\label{ex2}
%%------------------------------------------------------------------------

Suppose a processor retries an Invalidation to $x$ if there is an
outstanding bus operation to $x$.  This processor could deadlock a
\ccdsm/ implementation that uses it.  For an example of the problem,
consider a simple scenario, shown in
Figure~\ref{fig:flush-vs-pending}, where an \inval{x} request
arrives at $A$ when there is an outstanding \rd{x}.

\begin{figure}
\illustrationpercent{flush-vs-pending}{70} \caption{This time-line
diagram illustrates the scenario described in the example of
Section~\protect\ref{ex2}.  Because of the concurrent initiation of
memory requests, the system must handle an invalidation request which
arrives at a site to find an outstanding Read request to the same
cache-line.} \label{fig:flush-vs-pending}
\end{figure}

\small
\begin{enumerate}
\item $P_{A}$ has $x$ in \ss/ state but replaces it in its cache.
\item $P_{B}$ wants to write $x$.  Invalidation sent to $A$.
\item $P_{A}$ reads $x$ again.
\item $P_{A}$ receives Invalidation.
\end{enumerate}
\normalsize

Since the processor does not allow the Invalidation to complete until
the Read completes, the Invalidation of $x$, if put on the bus, will
deadlock as it has to wait for the outstanding \rd{x} to complete.
This depends on $B$'s Write $x$, which in turn depends on the
Invalidation completing.  In this case, the \ccdsm/ implementation
{\em must} track outstanding operations, intercept invalidation
requests and send back a message indicating that the invalidation is
completed. Skipping the actual invalidation is legal, since we know
that the cache-line does not exist at the requesting site.

This problem is also solved if the snoopy bus protocol allows an
\inval{x} bus operation to complete even if a processor on the
bus has an outstanding \rd{x}.  The read request is satisfied as
normal when the cache-line is returned.  This solution is preferred as
it also solves the problem described in the next section, but has to
be implemented by the snoopy bus protocol.

%When the read cache-line returns, it is the read request is satisfied.

%%------------------------------------------------------------------------
\subsection{Complications from Multi-processor Sites}
%%------------------------------------------------------------------------
\label{sec:cmp-mp}
%%------------------------------------------------------------------------

Multiple processors at a site create problem situations in \ccdsm/
systems which an inclusive cache shared by all site processors
eliminates.  A variation of the example in Section~\ref{ex2} with two
processors $P_{A1}$ and $P_{A2}$ at site $A$ explains why.

\small
\begin{enumerate}
\item $P_{A1}$ reads $x$, $B$ is the home site of $x$.  $P_{A1}$
obtains $x$ and caches it.
\item Processor $P_B$ tries to write $x$.  The directory indicates
site $A$ has a copy.  An invalidation is sent to site $A$.
\item Meanwhile, $P_{A2}$ tries to \rd{x}, misses in its cache, and
sends a \rd{x} request to the home site.
\item When the \inval{x} request arrives at $A$, there is an
outstanding read request to cache-line $x$.
\end{enumerate}
\normalsize

Unlike the example in Section~\ref{ex2}, there is a cache copy of $x$
in $P_{A1}$ which {\em must} be invalidated by an invalidation bus
operation.  If the snoopy bus protocol allows the invalidation to
complete despite $P_{A2}$'s outstanding operation, there is no
problem.  Otherwise, an inclusive shared cache avoids the problem
altogether by eliminating the situation where there is an outstanding
\rd{x} from a site and $x$ in some cache of that site.

An extra cache is not necessary if the snoopy bus protocol supports
cache-to-cache transfer of all ``non-local'' data.  Cache-to-cache
transfer when a \rd{x} occurs while $x$ is in the \ms/ state in some
processor's cache is currently supported on many snoopy buses.
Extending it to happen when $x$ is in the \ss/ state will allow all
the caches to function as a combined per-site cache.


%%------------------------------------------------------------------------
\subsection{Need to Separate Buffers by Functionality}
%%------------------------------------------------------------------------
\label{sec:sep-bufs}
%%------------------------------------------------------------------------

Assuming our protocol is logically correct, another source of deadlock
is a finite number of buffers.  The sharing of hardware resources can
introduce dependencies between operations that are logically
unrelated.  There is no system that requires unbounded buffering; it
is possible to estimate the number of buffers needed given the size of
the machine and the protocol.  This limit may even be acceptable in
certain cases.  The limit is not satisfactory, however, if buffer size
is directly proportional to the number processors per site or the
number of sites per machine or the number of read/write buffers in the
microprocessors because the smallest change in machine configuration
can make the system deadlock prone.  We will show that separating
buffers by functionality is a better idea.

Consider an implementation with four types of buffers: (i) Capture
Buffers, used for storing captured requests until they can be
forwarded to the home site; (ii) Home Buffers\footnote{Entries
do not have to be serviced in FIFO order.  In particular a Home
Request Buffer containing a currently blocked transaction does not
block transactions in other Home Buffers on the same site.},
which hold requests at a home site until they are processed; (iii)
Invalidation Buffers, which hold invalidation requests until they
complete; and (iv) Reply Buffers which allow the protocol to return a
cache-line to the requester.  Our example will deal with three sites,
$A$, $B$ and $C$ with processors $P_A$ and $P_B$ on sites $A$ and $B$
respectively.  Assume each site has two Capture Buffers, four Home
Request Buffers, one Invalidation Buffers, and one Reply Buffer.

\small
\begin{enumerate}
\item
$P_A$ writes cache-lines $x_1$, $x_2$, $\dots$, $x_{10}$, (all of whose
home is site $C$), caching them in the \ms/ state.  
\item 
Similarly, $P_B$ writes cache-lines $y_1$, $y_2$, $\dots$,
$y_{10}$, (whose home is also site $C$), caching them in the \ms/ state
in $P_{B}$.

\item 
$P_A$ and $P_B$ ``exchange'' the data that they work on, \ie, $P_A$
reads cache-lines $y_1$, $y_2$, $\dots$, $y_{10}$, while $P_B$ reads
cache-lines $x_1$, $x_2$, $\dots$, $x_{10}$.  If the bus is
split-phase or if there are many processors per site, many requests
can be outstanding from sites $A$ and $B$.

\item 
All the read requests are buffered in Capture Buffers at the
respective requesting sites, before they are buffered in site $C$'s
Home Buffers.  Invalidation requests are issued to sites $A$ and $B$.

\item 
When the invalidation requests, Inval $x_1$ and Inval $y_1$ arrive at
sites $A$ and $B$ respectively, invalidation bus operations are
performed.  However, in order for the \ms/ data to be invalidated and
written back, there must be Capture Buffers to accept them.
Unfortunately, all the Capture Buffers have been used up by
outstanding read requests, so the invalidations cannot complete.

\item
Worse yet, no Capture Buffers will free up at $A$ or $B$ until there
is space in the Home Buffers of $C$.  But all the Home Buffers in $C$
are in use, and will not free up until the invalidations are done.  A
deadlock has now occurred.  This situation is illustrated by
Figure~\ref{fig:dl1-animation}, where the arcs indicate dependence.
\end{enumerate}
\normalsize

\begin{figure}
\illustrationpercent{dl1-animation}{60} 

\caption{A deadlock caused by limited buffering.  Both
sites $A$ and $B$ have initiated many read requests to site $C$, and
in so doing filled up their own Capture Buffers and $C$'s Home
Buffers.  These reads require invalidation operations to be performed
at both sites $A$ and $B$.  Unfortunately, the invalidations cannot
complete until Capture Buffers are available for write-backs triggered
by the invalidations.  In the mean time, the invalidation buffers at
sites $A$ and $B$ fill up, and deadlock occurs.}
\label{fig:dl1-animation}
\end{figure}

The above deadlock scenario arises purely from the constraints of
finite buffering.  If the home site, $C$, or the capture buffers has
infinite buffering, this problem will not occur.  

This deadlock is easy to see with a static dependence graph, which,
for the example, is shown in
Figure~\ref{fig:merged-buff-problem1}\footnote{We have developed this
technique for illuminating deadlock possibilities.  It is very similar
to techniques used to show networks are deadlock free.  An article
will be written on the technique in the near future.}.  Each node of
this graph is a pool of hardware resources used by the \ccdsm/
implementation in a blocking fashion.  An arc, such as from the
Capture Buffers node to the Home Buffers node indicates that a Capture
Buffer in use is not released until a Home Buffer is obtained.  If
this graph does not contain any cycles, no deadlock due to sharing of
hardware resource can occur dynamically.  Unfortunately, a cycle
exists for the example.  This indicates that deadlock can occur if too
many concurrent events are outstanding\footnote{It is possible for a
particular implementation with cycles to avoid deadlock by
constraining the number of concurrent actions.}.

\begin{figure}
\illustrationpercent{sdg-merged-buff-bad1}{60}
\caption{Static dependence graph for the system described in
Section~\protect\ref{ex4}.  Each solid box represents a pool of
resource, while the arcs indicate potential dependences.  The presence
of a cycle between Capture Buffers, Home Buffers and Invalidation
Buffers, indicates that deadlocks are possible.  }
\label{fig:merged-buff-problem1}
\end{figure}

A solution for the example requires not only separating write-back
capture buffers from read capture buffers, but also the home read
request buffers from the home write-back request buffers.  The
deadlock-free dependency graph is shown in Figure~\ref{fig:sdg-good}.
Intuitively, this means that write-backs of cache-lines have a
dedicated path to memory which read requests cannot block.  Reads are
only blocked if write-backs triggered by invalidations are blocked, so
avoiding write-back blocking avoids deadlock altogether.  Splitting
buffers into separate categories requires the capability to retry
selected types of bus accesses that use buffers that are temporarily
unavailable while allowing others to proceed.  This selective retry
capability is provided in our ACD.

\begin{figure}
\illustrationpercent{sdg-good}{60} 
\caption{By dividing the Capture Buffers into Read Capture Buffers and
Write-back Capture buffers and Home Buffers into Read Request Home
Buffers and Write-back Request Home Buffers, we are able to remove the
dependence cycle.}
\label{fig:sdg-good}
\end{figure}


%%------------------------------------------------------------------------
\subsection{Why Our \sp/ Cannot Issue Invalidates}
%%------------------------------------------------------------------------
\label{sec:flush}
%%------------------------------------------------------------------------

Blocking shared resources include more than just buffers.  In \start/,
the \sP/ is capable of executing invalidations (using a Flush
command).  Unfortunately, an Invalidation is not allowed to complete
until any write-back it triggers completes.  An \sP/ performing an
Invalidation operation can thus be blocked.  This would make the \sP/
a blocking resource, leading to deadlocks because of the \sP/'s other
roles.

We can see why Flushes could cause a deadlock in the following
scenario.
\small
\begin{enumerate}
\item Write-back capture buffers on a site are full.  Store buffers in
the \dP/ are also full.
\item \sP/ initiates \inval{x} which \dP/ has in \ms/ state.
\item \dP/ cannot push-out $x$ because all store buffers are full
waiting to go to ACD.
\end{enumerate}
\normalsize

Deadlock occurs because completing the \sP/'s Invalidation depends on
the write-back occuring.  The write-back cannot occur until the \sP/
services the ACD.  The \sP/ cannot service the ACD until its
Invalidation is unblocked -- Deadlock!  This problem can be seen with
the static dependence graph of Figure~\ref{fig:sP-flush-dep-graph},
with the \sP/ modeled in the graph because it is used in a blocking
fashion to perform the invalidation.

\begin{figure}
\illustrationpercent{sdg-flush-problem}{60}

\caption{When the \sP/ is used to perform invalidation operations, it
becomes a blocking resource that has to be modeled in the static
dependence graph.  In doing so, many cycles are immediately
introduced.  The dash arcs represent dependences on \sP/ that utilize
the \sP/ in a non-blocking fashion.  The addition of the arc from the
\sP/ to the Write-back Capture Buffers introduced by the
\sP/ performing invalidations causes cycles.}

\label{fig:sP-flush-dep-graph}
\end{figure}

This problem is solved by providing extra hardware that performs the
invalidation.  This gives rise to the static dependence graph shown in
Figure~\ref{fig:flush-ok} that has no cycles.  In \start/, we have
chosen to implement this within the ACD hardware, though it functions
independently of all other functionalities of the ACD.

\begin{figure}
\illustrationpercent{sdg-flush-sol}{60} 
\caption{By providing extra
hardware that performs the invalidation, the arc linking the \sP/ to
write-back capture buffers node is removed.  Now no cycle is present
in the static dependence graph of the system.} \label{fig:flush-ok}
\end{figure}

\subsection{Difficulty in Sharing Cacheable Data between \dP/s and \sP/}
%%------------------------------------------------------------------------
\label{sec:dp-sp-sharing}
%%------------------------------------------------------------------------

The snoopy bus protocol should allow cache-to-cache transfer of \ms/
data to a processor performing a Read {\em without requiring a
write-back to main memory.} This requires supporting a {\tt Shared
Modified} state, where the data is shared among multiple caches, with
one cache which holds it in the {\tt Shared Modified}
state\cite{Thacker87} given the responsibility of eventually updating
main memory.

Without this capability, the \sP/ cannot share cacheable, writable
data with the \dP/s.  If the \sP/ reads data that is \ms/ in a \dP/,
it will block until the \dP/ is able to push the \ms/ data out with a
write-back.  Although this write-back is to local memory, it may be
waiting behind write-backs that are going to global memory.  Hence,
the write-back may be blocked because all the write-back capture
buffer resources are in use, and can only be freed by the \sP/.  In
the static dependence graph, sharing of writable, cacheable data
between the \sP/ and the \dP/s introduces an arc from the \sP/ to the
write-back capture buffers resource, resulting in a cycle reminiscent
of that cause by \sP/ performing Invalidations.  Thus, data sharing
between the \sP/ and \dP/, if desired, must be through uncached
memory.  

It is important to note that since operating systems data-structures
on SMPs are usually cacheable and writable by any processor, this
prohibition on sharing cached, writable memory between the \dP/s and
the \sP/ means that the \sP/ cannot use the same operating system
services used by \dP/s.  For this reason, the \sP/ will in most
likelihood have to run firmware code without virtual memory, although
it is conceivable that the \sP/ could run a simple operating system of
its own that does not share any resource with the main operating
system.

%%------------------------------------------------------------------------
\subsection{Complications due to Non-FIFO Network}
%%------------------------------------------------------------------------
\label{sec:cmp-non-fifo}
\label{ex4}
%%------------------------------------------------------------------------

A non-FIFO network introduces considerable complexity since messages
can get arbitrarily out of order.  Although the protocol can use
acknowledgments to serialize its actions and hence avoid the effects
of a non-FIFO network, such a solution is unattractive because of the
additional overhead and latency.  Better solutions use more states in
the protocol to handle possible out-of-order situations, sending extra
messages only when necessary.  Keeping track of outstanding
operations, which is required in the example of Section~\ref{ex2}, is
also necessary here.  Let us consider the scenario below which is
related to the example in Section~\ref{ex2} (see also
Figure~\ref{fig:overtake}).

\begin{figure}
\illustrationpercent{overtake}{70}
\caption{This time-line diagram illustrates the scenario described in
Section~\protect\ref{ex4}.  Owing to a non FIFO network, a
invalidation request overtakes the data that it is trying to flush.}
\label{fig:overtake}
\end{figure}

\begin{enumerate}
\item $P_{A}$ sends a \rd{x} to site $B$, home of $x$.
\item $B$ sends back data $x$.
\item $B$ writes $x$, sending $A$ \inval{x}. 
\item Invalidation arrives before data $x$!!!
\item Data $x$ arrives. 
\end{enumerate}

Because the arrivals of Data $x$ and \inval{x} at $A$ are
reversed, it is not correct to process them in their arrival order,
since the home processor might then believe that site $A$ does not
have a copy of $x$.  Simply having the invalidation wait while there
is an outstanding operation will potentially deadlock since it is
possible that the \inval{} {\em should} come before the Data and the
Data won't come until the \inval{} completes as in the example of
Section~\ref{ex2}. 

If there is an outstanding operation to the same cache-line on site
$A$, an \inval{} can wait at site $A$. The home site $B$, upon
receiving a \rd{x} request from a site to which it has already sent
an invalidation {\em must} reply with a Retry \rd{x}.  If this retry
gets back to site $A$ and finds a pending invalidation, the
invalidation can then be allowed to complete without being put on the
bus.  Should the sequence of events be that described in
Section~\ref{ex2}, the reply data returns to find a waiting
invalidation.  The outstanding read is first completed, then the
Invalidation is done on the bus.  Proving this solution works is
involved because other messages can overtake each other.  For example,
the Retry \rd{x} can overtake the \inval{x}.  Another
document\cite{shen94} describes cache coherence protocols we intend to
implement on \start/ and proofs of their logical correctness.

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

