\section{Cache-Coherent Multiprocessors}
\label{CC}

Shared-memory multiprocessor architectures
based on memory coherence models start from an assumption
that the {\em sequential consistency model} of Lamport is the ideal
view of memory for the processors of a parallel computer.
It provides programmers with a memory model
familiar to them from working with
single-processor computers, and it is hoped that (multi-process)
software written for single processor systems may be
migrated to the parallel processor without
significant modification.
This philosophy of multiprocessor architecture is represented
by two main styles: the cache-coherent nonuniform memory
access architecture (CC-NUMA), and the cache-only memory
architecture (COMA)
Examples of CC-NUMA machines are the Stanford DASH
architecture~\cite{LenoskiEtAl90,LenoskiEtAl92} and the MIT Alwife
Machine~\cite{AgarwalEtAl90}, while examples of COMA machines include 
the KSR-1~\cite{KSR92} and the DDM~\cite{HagerstenLanHar92}.

In these systems, cache coherence is achieved by maintaining
a directory at each processor. The directory contains, for each block of
memory in its portion of the global address space, a record
of which processors hold cached copies of the block.
When a processor writes a location in a block, messages are sent to
all processors in the directory record to invalidate cached copies
of the block. An attempt to read an invalidated block causes the
block to be fetched from its home node. Some cached blocks
will be invalidated even though
there may be no future attempt to read them. Also, when an
invalidated block is read, there will be two additional messages to
request and retrieve the updated value.

In the execution model of this paper, a write operation causes the
written value to be delivered to all processors containing activities
that have pending reads. This protocol uses fewer messages (two
instead of three) to implement the transaction, and all messages
are productive (each request and its reply concern a word actually
used in the computation). Thus communication from a producer of
data to one or more consumers is more efficient. 

Let us illustrate this by a simple example.
Let {\tt X} be a shared location used to transmit data values between
a producer and a consumer. To implement this interaction,
a semaphore or lock, say {\tt S}, must be used
to ensure the correct synchronization.
The producer code may look like
\begin{verbatim}
      ...
    X := ...
    unlock(S)
      ...
\end{verbatim}
and the consumer code may look like:
\begin{verbatim}
      ...
    lock(S)
    .. := ..X..
      ...
\end{verbatim}
The lock and unlock operations can be viewed as playing the role of
semaphore operations such as the P and V operations of Dijkstra.
Since performing a semaphore operation requires at least
one (global) memory reference, this mechanism is less
efficient than when the synchronization is combined with
data transfer using I-struture operations. Moreover, implementation
of the lock operation calls for either busy-waiting or calls
to operating system scheduling routines if a long wait is
anticipated. Furthermore, given the network delays in a
shared-memory multiprocessor that utilizes a multistage network,
the implementation of locks is likely to be more expensive
than in a simple shared-bus architecture.
Note that if the above producer and consumer code is in
an innermost loop, the cost will be proportional to
the loop bound!

For the write to the shared variable {\tt X} itself, different
CC-NUMA cache-coherence protocols may incur different overhead.
Under a memory model based on (strong) sequential consistency, the write
to {\tt X} in the producer will need to send
invalidate signals to the consumers,
and wait for their acknowledgement before it proceeds.
Under a weaker memory model such as the release consistency model,
some optimization may be introduced to relax the order constraints.
For example, the write operation may proceed before receiving
the acknowledgement signals until the unlock operation
(called {\em release}) is performed. However, the overhead of
the semaphore operations must still be paid.

An advantage of our program execution model comes from combining data
transfer and synchronization, avoiding altogether any separate cost
of synchronization operations. In addition, our cache management scheme
involves no non-productive cache-coherence (invalidation)
traffic. Of course, the synchronization overhead may be reduced (per word) by
grouping data into blocks and synchronizing on each block.
The result is medium or coarse-grain parallelism, and suffers
from the increased delay of the start of processing by the
consumer.

Another issue deserving attention concerns the problem
of switching between jobs on a shared-memory computer.
The fact that continuations contain data frame
pointers and are sequestered in defer queues
that may have a long lifetime will make it
difficult to switch between jobs economically
unless the data frame pointers are in a universal
address space and can be guaranteed to be unique.
In a conventional multiprocessor, some version of ``gang
scheduling'' may be used in which all network
traffic pertaining to inactive jobs is
intercepted and either reinterpreted or held
in software queues until the corresponding job
is reactivated. This can be effective because
only a relatively short time is needed for network traffic related to
one job to die out. With pointers stored in defer queues that
may produce network messages at unknown times in the future,
a universal addressing mechanism will be essential.
 
