%%------------------------------------------------------------------------
\section{CCDSM Design Concerns}
%%------------------------------------------------------------------------
\label{sec:background}
%%------------------------------------------------------------------------

Certain characteristics of the processor, memory bus, buffering
strategy and network used in a system are very important to the
implementation of a \ccdsm/ on a network of SMPs, oftentimes affecting
its correctness.  This section briefly discusses important
characteristics of each component after reviewing a simple directory
based cache-coherence scheme.  Details of how they affect a \ccdsm/
system is found in Section~\ref{sec:ccdsm-issues}.

\subsection{Directory Based Cache-coherence Schemes}

Cache-coherence on distributed systems is usually maintained with
directory-based schemes.  ``Directory'' information on every
cache-line is kept by a ``home'' location.  Typical directory entries
are \us/ by any site; \ss/ among one or more sites and thus is
read-only at that moment; or \ms/ (and temporarily owned) in one site
and only that site can read and write that cache-line.  When a memory
operation misses in a processor's local cache, the request is
forwarded to the home location which checks its directory.  If the
cache-line is in the \us/ state, the request is satisfied and the
directory updated.  The home site can also satisfy a read request when
the cache-line is in \ss/ state.

A \rwitm/\footnote{\rwitm/ requests generally come out of a processor
as a ``read-with-intent-to-modify'' request rather than a ``write''
because the write may just be to one word in a cache-line.} request
will, however, require all the current readers to be invalidated.
Invalidation means that all processors holding that cache-line must
have that cache-line removed from their cache.  Regardless of the
request type, if the cache-line is in the \ms/ state, the home must
invalidate the cache-line at the current owner's site, forcing the
up-to-date cache-line to be returned to home, which then sends it to
the requester.  The directory is updated appropriately during this
process.  Though all directory-based cache-coherence schemes follow
this basic pattern, there are many variations and optimizations.  For
simplicity of discussion, this paper will assume a sequentially
consistent implementation of memory operations when they appear on the
memory bus.  The rest of this section gives an overview of the
building blocks of a \ccdsm/ system and the issues related to each
component.

\subsection{Memory Model}

A processor implements a specific particular memory consistency model.
Most current microprocessors, including PowerPC 620, will reorder
memory operations to improve performance; for example, giving loads
higher priority than stores since the instruction stream will stall
for want of a loaded value.  To preserve the semantics of sequential
execution on a processor, memory transactions from a processor to the
same location proceed in order.  However, memory transactions to
different locations do not necessarily have any fixed ordering.  This
consistency model is commonly called weak consistency.

Processors that implement weak consistency invariably provide
sequentializing instructions, such as the \sync/ instruction in
PowerPC, that provide a fence or barrier ensuring that all outstanding
operations complete before subsequent operations are issued.  In order
to implement sequential consistency, such sequentializing instructions
are inserted at appropriate places in the instruction stream.

Weak consistency is sufficient for correct execution most of the time.
An instance where weak consistency is insufficient is when dealing
with memory mapped I/O devices.  Generally, I/O devices require that
writes to their address space are performed in a specific order.
It becomes important, then, that memory operations appear on the
bus in the same order as their ordering in the instruction stream.
Since performance of superscalar processors degrades rapidly if
sequential consistency is maintained, the use of sequentializing
instructions should be avoided unless absolutely necessary.

\subsection{Memory Instruction Semantics}

We are using commercial processors to implement a \ccdsm/ system.
Because these processors are designed for the uniprocessor or SMP
setting, the semantics of some of their instructions are not
necessarily ``scalable''.  As another example, the PowerPC used in
\start/ has a data cache-block flush (\dcbf/) instruction which
flushes a specified address out of {\em all} processors' caches.  It
may be possible to implement the exact \dcbf/ semantics on a parallel
machine built from multiple indirectly connected buses by essentially
broadcasting every flush to all processors.  However, it is certain
that such a scheme would be inefficient.  The basic reason to maintain
directories to avoid broadcasting invalidations.  An alternative
semantics is to limit the scope of \dcbf/ to flush only processors on
the bus where the \dcbf/ is issued.  Using these semantics will allow
us to use the \dcbf/ instruction to perform invalidations within a
site to implement \ccdsm/.  These and related issues require the
designers of a \ccdsm/ system to examine the instruction set's
semantics carefully.

There is a class of privileged instructions, used to support
operating system activities.  One such instruction is the \tlbie/
which invalidates TLB entries across the snoopy bus.  Whether a
\ccdsm/ system supports global semantics of such instructions can have
an impact on the type of OS that can run on the system.  If each site
runs its own OS, these instructions do not have to be supported across
sites.  

\subsection{Memory Bus Implementation}

Like processor cache design, memory buses have gone through
refinements to improve performance.  Early memory buses permitted only
one bus transaction at a time.  If a processor issued a read, the
memory bus would block until that read was satisfied.  Later memory
buses allowed pipelining which increased bus throughput.  A pipelined
bus, however, cannot take advantage of memory operations that are
satisfied out of order.  If one operation takes longer to perform, all
of the operations that follow it must wait until it finishes.

A more general approach is provided in a split-phase bus, which allows
replies to return in an order different from that in which their
requests were issued.  This approach requires some way of associating
a reply to its request, making implementations more complicated but
promises better performance.  It appears that most microprocessors of
the near future will have split-phase buses.  As we shall see later in
this paper, split-phase buses are needed in the \ccdsm/ setting not
only to improve performance, but also to avoid certain types of
deadlocks.

It is important to note that when a processor issues a memory request
on the bus, it can be rejected (retried) by the memory system.  The
processor has to keep retrying until the request is accepted.  During
this time, the processor has to perform snooping operations and react
as though the request has not occurred.  Once a request has been
accepted by the memory system, however, the request is considered to
be ``committed'' and the processor, in general, does not allow
cancelation of the request.  The need for such cancelations does not
arise in SMPs.

On a split-phase bus, the time between the acceptance of a request and
the arrival of a corresponding response opens up a window during which
the semantics of interactions between new bus operations and the
outstanding memory operation is not obvious.  Generally there is no
problem if the two bus operations are to different cache-lines.
However, consider how a processor should respond to an Invalidate $x$
bus operation after the processor's Read $x$ request has been
accepted.  Should it allow the Invalidate to complete because it does
not yet have a copy of $x$ in its cache, or should it prevent the
Invalidate from completing until it gets back data $x$, and remove
that from its cache?  Both positions make sense in the SMP setting.
The proper choice, however, is crucial to a \ccdsm/ system as we will
see in Section~\ref{sec:ccdsm-issues}.

\subsection{Buffers and Networks}

Buffer management is important in a \ccdsm/ system as the amount of
buffer space in the processor, network, and coherency engine for
storing the state of in-progress requests is always limited.  If one
is not careful in the design of the system, concurrent processing of
multiple requests can lead to deadlocks due to insufficient buffers.

Another major concern is whether the network delivers
messages in FIFO order.  If the network is not FIFO, it is important
for the coherence protocol to know that and account for it, or for
some lower level software to ensure that FIFO ordering is observed by
the coherence protocol.  Generally speaking, non-FIFO networks offer
better raw performance but add significant complexity to cache
coherence protocols.

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