%%------------------------------------------------------------------------
\section{A Reference Model for Designing Deadlock Free \ccdsm/}
%%------------------------------------------------------------------------
\label{sec:dl-free-model}
%%------------------------------------------------------------------------

The previous section shows many examples of hardware deadlocks that
can arise if an implementation of \ccdsm/ is not careful.  This
collection of examples is by no means an exhaustive list of deadlock
scenarios and raises the question of how one can ensure that a \ccdsm/
implementation is free of hardware induced deadlocks.  It is
worthwhile to note that in general, there are two cateogries of
deadlock problems: those arising from logical error in the protocol,
and those due to sharing of hardware resources in a blocking
fashion.\footnote{Sharing of hardware resource in a blocking manner
means that once the resource is acquired for use during a stage of
protocol processing, is held until the next stage of the protocol
processing can proceed.  Examples of hardware resources that can be
shared this way include both buffer space, and processing logic.  As
an example, for a bus operation to be accepted on the initiating site,
the capture device must have buffer space for it.  This buffer space
is held at least until the request can be forwarded to the home site.
It is thus used in a blocking manner.  If this buffer space is shared,
for example with data that is returned in respond to a read (which is
unsafe sharing), the latter cannot happen until the request currently
occupying the buffer has been sent out.} All the problems we described
earlier are due to the latter.  We call these {\em hardware induced
deadlocks} as they can exist even though no the protocol is free of
logical deadlocks.

\outline{Considering particular deadlock examples does not go very far}

In this section, we will describe how we dealt with the problem of
hardware induced deadlock only.  We assume that the protocol is free
of logical deadlock to start with.  (Cite Xiao Wei's work as an
example of proving protocol correctness at the logical level.)

Each example in the previous section describes the sequence of events
that lead to a cycle of dependences which clearly shows that a
deadlock has occurred.  However, this view is not very useful in
dealing with the deadlock problem for two reasons.  Firstly, it does
not show clearly the root cause of the problem.  Secondly, even if
someone comes up with a solution that solves the particular problem
instance, it is not clear that the proposed solution is indeed free of
all deadlocks.  Each dependence cycle described in the last section
represents only one particular dynamic instance.  If we consider
systems that can scale to arbitrary sizes, and in which arbitrarily
many number of mc-ops can be happening concurrently, there are simply
too many cases (essentially infinite number of cases) to consider them
separately.

\outline{The way to go is to consider a static dependence graph; give
a quick view of what it does}

In designing \start/, we dealt with this problem by using a {\em
static dependence graph}\cite{our-sdg-memo} which provides a way of
analysing {\em all} the potential dynamic dependences using a graph
which captures the this information as static dependences.  The static
dependence graph condenses the dynamic information into a static form
in a conservative way, ensuring that if dynamic dependence cycles are
possible, static dependence cycles must exist in the static dependence
graph.  Thus, if we can ensure that there is no cycle in the static
dependence graph, the system is deadlock free.  


\outline{Propose a simple protocol used in the examples}

We will illustrate the use of static dependence graph with reference
to a very simple cache coherence protocol.  There are only three
processor initiated bus operations in this protocol: (1) cache line
read only (r-read); (2) get cache line for write (w-read); (3)
write-back of dirty cache line (w-back).  One other bus operation is
supported to allow implementation of \ccdsm/: a flush bus operation
which when issued on a snoopy bus, removes the cache line from all the
cache of all processors on the snoopy bus.  If the cache line is dirty
in one of the processors' cache, the flush operation is retried, while
a write-back is initiated.  The flush operation is allowed to complete
only after the write-back has been accepted on the bus.  If there is
an outstanding r-read or w-read when the flush is issued, the flush is
allowed to complete right away as no copy of cache line is present
yet.  (Any assumption on bus type?)

To simplify the protocol, we will assume that the network maintains
FIFO ordering for messages between any pair of source and
destinations.  

The \ccdsm/ protocol is a simple extension of snoopy bus protocol,
with the home site serializing and arbitrating between concurrent
conflicting accesses to the same cache line.  The typical sequence of
action starts with the processor putting a requests on the snoopy bus.
This is captured and buffered at the requesting site.  Next, this
request is forwarded to the home site.  The home site checks the
directory and depending on the directory state and the type of
request, may either not need to reply at all, as in the case of
write-back; be able to reply immediately; or initiate one or more
flushes.  

The home site maintains
the following state for each cache line:
\begin{itemize}
\item 
home : the cache line is not cached anywhere
\item 
Shared [Set of readers] : the cache line is cached for read only by
the sites recorded in the set of readers. 
\item 
Modified [owner] : the cache line is cached by owner which is also
allowed to write to it.   
\item 
Flushing-data-pending [pending op, $n$] : this is a transient state.  Flushing
is in progress in order to support the pending op.  $n$ more flush
acks expected. 
\item 
Flushing-only [pending op, $n$] : this is a transient state.  Flushing
is in progress in order to support the pending op.  $n$ more flush
acks expected. 
\end{itemize}

Messages accepted by home site: 
\begin{itemize}
\item
r-read req:
\item
w-read req:
\item
w-back req:
\item
flush ack:
\end{itemize}

Messages sent by home site:
\begin{itemize}
\item
flush req:
\item
r-read reply:
\item
w-read reply:
\item
retry op:
\end{itemize}

The home state transition diagram is:
\begin{center}
\begin{tabular}{|l|p{1.2in}|p{1.2in}|p{1.2in}|p{1.2in}|}
\hline
  		&\multicolumn{2}{c|}{Home}	&\multicolumn{2}{c|}{Shared[S]}
\\\hline
		& action & next state 		& action & next state 
\\\hline
r-read req	& r-read reply	& Shared	& r-ready reply & Shared 
\\\hline
w-read req	& w-read reply	& Modified	
		& flush(S)	& flushing-only(req, sizeof (S)) 
\\\hline
w-back req	& --	& error			& --	& error 
\\\hline
flush ack	& --	& error			&  --	& error
\\\hline
\end{tabular}

\begin{tabular}{|l|p{1.2in}|p{1.2in}|p{1.2in}|p{1.2in}|}
\hline
		&\multicolumn{2}{c|}{Modified[m]}
		&\multicolumn{2}{c|}{Flushing-data-pending(p-op,n)}
\\\hline
		& action & next state 		& action & next state
\\\hline
r-read req	& flush(m)	& flushing-data-pending(req, 1) 
		& retry op	& flushing-data-pending(p-op,n)

\\\hline
w-read req	& flush(m)	& flushing-data-pending(req, 1)
		& retry op	& flushing-data-pending(p-op, n)
\\\hline
w-back req	& 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)
						
\\\hline
flush ack	& --	& error			
		& --	& flushing-data-pending(p-op, n-1)
\\\hline
\end{tabular}

\begin{tabular}{|l|p{1.2in}|p{1.2in}|}
\hline
		&\multicolumn{2}{c|}{Flushing-only(p-op,n)}
\\\hline
		& action & next state 		
\\\hline
r-read req	
		& retry op	& flushing-only(p-op,n)
\\\hline
w-read req	
		& retry op	& flushing-only(p-op,n)
\\\hline
w-back req							
		& --	& error
\\\hline
flush ack	
		& 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}

\outline{What is a static dependence graph?}

Each node of the static dependence graph represents a set of the same
type of blocking hardware resources.  Arcs in the graph represent
potential dependences between the resource sets that comes from the
coherence protocol.  If a node $x$ represents resources that is used
to buffer the $i^{th}$ step of protocol processing, and node $y$
represents resource used for the $(i+1)^{th}$ step, then there is an
arc from node $x$ to node $y$ in the static dependence graph.
Strictly speaking, this indicates that the resource in $x$ is held
until the resource in $y$ is allocated.  At this point, it is
deallocated.  If the resource from node $x$ is only deallocated at a
later state, for example, after resource $y$, $z$ is needed, and then
$w$ before $x$ is deallocated, arcs $(x, z)$, and $(x, w)$ are needed.
In general, because the dependence arcs are transitive, and the
delayed deallocation invariably occurs later in the chain of
dependences, the additional arcs are redundant.


The static dependence graph is finite since there are only finite sets
of hardware resources.  The static dependence graph summarizes the
potential dynamic dependences in a conservative manner, i.e. if
dependence cycles can form dynamically, there will be cycle(s) in the
static dependence graph.  Thus, if we can ensure that there is no
cycle in the static dependence graph, the system is deadlock free.  In
general, a cycle in the static dependence graph suggests that deadlock
cycles are possible, given sufficient number of concurrent activities.
In a particular implementation, it may be possible to prevent dynamic
dependence cycles from arising by bounding the number of concurrent
activities and providing a sufficient number of buffers to cater for
the controlled number of concurrent activities.

\outline{Show the static dependence graph for an example
implementation of our simple protocol.}

To illustrate the static dependence graph method, we need an actual
example implementation where all blocking hardware resource sets are
clearly defined.  We will suggest an implementation with 6 types of
hardware resources, and they are used in the protocol action sequence
as shown below.  The arcs therefore also represents the dependence
arcs in the static dependence graph. 
\begin{itemize}
\item 
r-read: 
\newline
req capture-buffer \ra home-buffer \ra returned-data buffer
\newline OR \newline
req capture-buffer \ra home-buffer \ra flusher \ra returned-data buffer
\newline OR \newline
req capture-buffer \ra home-buffer \ra flusher \ra w-back
capture-buffer \ra w-back home buffer \ra returned-data buffer 
\item 
w-read: goes through the same sequence as r-read
\item 
w-back: 
\newline
w-back capture-buffer \ra w-back home buffer \ra returned-data buffer
\end{itemize}
The returned-data buffer category is also used for processing
flush-acknowledgements.  

\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-memo} has a complete description of
how this network abstraction can be achieved.

The static dependence graph is shown in Figure~\ref{fig:sdg-0} and has
no static cycles, indicating that it is a safe design.  If we start
sharing different types of buffers, however, we may run into trouble.
For example, if we group req capture-buffer with w-back
capture-buffer, which seems to be a reasonable thing to do, the static
dependence graph now has cycles.  To see an example of this deadlock,
consider 4 sites, $A$, $B$, $C$ and $D$.  Site $A$ caches in modified
state many cache lines, $x_i$'s for different $i$, all of which have
their home at site $C$.  Site $B$ caches in modified state many cache
lines, $y_j$'s for different $j$, all of which are from site $D$.
Now, supposed site $A$ decides to read $y_j$'s, while site $C$ decides
to read $x_i$'s.  As the read requests from $A$ go to $C$, they
trigger flush requests to $B$, which in turn triggers write-backs from
$B$ back to $C$.  Now the same thing is happening with requests from
$B$, which goes to $D$, and then to $A$ to flush cache lines back to
$D$.  With enough requests going on, we can get into the situation
where all of $A$ and $B$'s capture buffers are all used for read
requests.  These requests cannot move forward because all the buffers
along the subsequent paths are used up.  One path goes from $A$ to $C$
to $B$.  Another path goes from $B$ to $D$ to $A$.  The paths of used
up buffers both lead up to the flush buffers where the flushes cannot
complete because the write-back triggered by the flushes cannot be
captured since there are no capture buffer left.

This deadlock is very similar to first deadlock example in the
previous section.  The second deadlock example of that section
combines the flusher and the w-back home buffer.  Again, this creates
a cycle in the static dependence graph.  The third example describes a
case that is different from our simple protocol.  It introduces a
dependence arc from w-back home buffer to w-back capture-buffer.
Finally, the fourth example also introduces new dependence arcs in the
static dependence graph through the use of shared, writable, cacheable
OS data structure.  All these arcs end at w-back capture-buffer, and
begin at any buffer that is accessed via the sP, which in \start/'s
case includes just about every single type of buffering!

\comment{We will add diagrams for all the static dependence graphs.}

\outline{Limitations of the static dependence graph technique}

Although a cycle in the static dependence graph means that deadlock
cycles are possible given sufficient number of concurrent activities,
a particular implementation may prevent dynamic dependence cycles from
arising by bounding the number of concurrent activities and providing
a sufficient number of hardware resources to cater for the controlled
number of concurrent activities.  It is also possible that an
implementation logically prevents certain mix of operations from
occuring at the same time and thus avoid the dynamic dependence cycles
that the static dependence graph indicates.  The static dependence
graph technique is currently incapable of handling these additional
information.

\outline{Intuition of why static cycle means dynamic cycle}

It may appears mysterious why a static cycle suggest dynamic cycle,
especially since resources are deallocated once the next one on the
dependence chain is available, and there may be multiple copies of the
same resource.  The way to think about it is that we can construct a
scenario with multiple concurrent activities, enough to exhaust each
resource set, and fill up the dependence chain.  

Static dependence graph without cycles will not have dynamic cycles
because those resource sets that have no out-going arcs are connected
to sinks, which continuously absort incoming requests, freeing up the
resources in the last set.  This then allows requests further
up-stream of the dependence chain to move.  

\outline{The Model}

Using the static dependence graph approach, and the simple protocol
that we described above, it is straight forward to derive a model
\ccdsm/ site.  Although this model is derived from the simple protocol
described above, it is in fact able to accomodate many variations of
the protocols.  Several of these will be described later.

The model, as shown in Figure~\ref{fig:ccdsm-model}, has 3 main
pieces, with 6 groups of resources.  The main pieces and their
resources are:
\begin{itemize}
\item 
The ACD+NIU: Resources: (i) buffer for out-going requests excluding
write-backs (the req capture-buffer); (ii) buffer for out-going
write-backs (w-back capture-buffer); (iii) buffer for data returned in
response to r-read or w-read requests. (returned-data buffer)
\item 
The pP+NIU: Resources: (i) buffer for r-read and w-read requests
coming from ACD+NIU (home-buffer); (ii) buffer for write-back
requests (w-back home buffer).
\item 
The cC+NIU: Resources: (i) buffer and logic for performing flush
requests. (flusher)
\end{itemize}
The static dependence graph of this model is exactly the same as that
in Figure~\ref{fig:model-sdg}.  The grouping into the 3 main pieces
are based on similarity in functionality.  The ACD interfaces to the
snoopy bus on the requester's end, the pP performs all home site
functionality, while the cC performs remote site, blocking operations.
We have not done any combining of the different groups of resources as
any combination will result in static cycles and hence deadlock.  


\outline{Variants of protocol that can fit into this model}

The simple protocol that we have described above can accomodate both
sequential and weaker forms of consistency without introducing
additional dependencies.  Supporting forwarding is straight forward
too, as the dependence arc introduced by forwarding is already
transitively there.

As a more radical change, let us consider allowing producer initiated
caching at a remote site.  The resources needed for the different
possible sequence of actions are:
\begin{quote}
send data request capture \ra directory check at home \& send data
\ra remote store 
\newline OR \newline
send data request capture \ra directory check at home \& send data
\ra remote store \ra w-back replaced \ra return replaced to home 
\newline OR \newline
(1) send data request capture \ra (2) directory check at home \& send
flush \ra (3) flush remote \ra (4) w-back \ra (5) returned to home \&
send data \ra (6) remote store \ra (7) w-back replaced
\ra (8) return replaced to home
\end{quote}

The static dependence graph suggests that we need to add more resource
types as the longest chain has 8 types of resources on the chain.
Sharing of any resources along this chain will lead to deadlocks.
However, we can avoid the problem by pre-allocating buffers, which
helps to break dependence chains by acting as sinks.  By
pre-allocating, during step (2), the buffer needed to store the state
in step (5) as it waits to go on to (6), (7) and (8), we essentially
break the dependence of (5) on (6), (7), and (8).  Note that because
the resource allocated at (2) now cannot be deallocated until (6) is
available, we need to add dependence arcs (2, 6), (2, 7) and (2, 8).
(The last two are redundant due to transitivity.)  But this is fine as
a possible grouping of resources is [3, 6], [4, 7] and [5, 8].

Referring back to our previous categories of hardware resources, (1)
uses req capture-buffer; (2) and (5) use home-buffer; (3) and (6)
use flusher; (4) and (7) use w-back capture-buffer; and (5) and (7)
use returned-data buffer.  

\outline{Correctness ``proof'' for the model}

The model follows from the application of static dependence graph.  

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

