%%------------------------------------------------------------------------
\section{Introduction}
%%------------------------------------------------------------------------
\label{sec:intro}
%%------------------------------------------------------------------------

\outline{Briefly state we believe that shared memory, and cache
coherent shared memory are important}

%\outline{Shared object space}

Researchers generally agree that a machine that supports both a global
address space and message passing simplifies the task of parallel
programming\cite{Kranz93}.  If the processors have caches, some effort
must be expended to present a coherent memory model.  The effort in
designing the custom hardware and coherence protocols is
large\cite{Argawal93}\cite{Kuskin94}.  The problem of coherence
protocols is further excerbated by the fact that there is more than
one memory consistency model.  Since cache-coherence protocols are
complex and rarely bug-free, current implementations tend to provide a
fully programmable processor to implement them.

Experience has also shown that efficient
message passing is required for implementing various shared memory
models on distributed memory machines.  However, the extra complexity
of implementing a shared memory model on top of a pure message passing
machine 


The \start/ project is about building an efficient message passing
machine which is also suitable for experimenting with different memory
models.  An important goal of the project is to maximize the use of
commercially available hardware and operating systems.  For various
technical and non-technical reasons we have chosen to connect PowerPC
based SMPs together by a fast network of our own design. Following
the idea presented in *T \cite{Nikhil92}, one processor in each SMP is
dedicated to handling memory requests from other SMPs.  Though we
expect to implement additional features required by different memory
models in software, each SMP is augmented with a simple address
capture device (ACD) to make the implementation of a global address
space possible. In this paper we will discuss some of the interesting
issues that had to be resolved to design such a machine.

The most important issue in the implementation of a memory model is
whether several copies of a memory location are permitted or not.
Currently, by far the most popular approach to reducing memory latency
and bus bandwidth is to rely on caches.  Since in a parallel system
there are potentially multiple readers and writers of a cache-line, it
is possible for a cache to have an out-of-date or ``stale'' copy of
that cache-line.  Protocols to keep the copies of replicated data
consistent with each other as dictated by a memory model is a major
concern in the implementation of any parallel machine built using
commercial microprocessors.

However, there are machines without caches where each memory reference
always goes to the physical memory location.  In such systems, memory
references to a location are automatically serialized in a fixed
manner for all processors. The most notable example of such a machine
is Cray X-MP. Most dataflow and multi-threaded machines
also do not cache global data (See for example, HEP~\cite{Smith81},
Tera~\cite{Alverson90}, EM-4~\cite{Sakai89}
Monsoon~\cite{Papadopoulos91}).  Such machines rely on {\em
split-phase transactions} to absorb memory latency, and provide
efficient mechanisms to support word-level synchronization throughout
the global memory. The major criticism of machines without caches is
that they demand higher bandwidth memory systems than machines with
local caches.

Some machines, such as the Cray T3D, pass on the burden of keeping the
caches coherent to the user-level software.  This position, however,
is not always desirable. The oldest way to keep the caches coherent
comes from bus based multiprocessors (dual processor IBM 370 systems
from the early seventies). The solution, which is also used in all
current SMPs, is to ``snoop'' on the address bus during a cache
miss. On a write operation, the data is automatically invalidated from
all caches to maintain consistency.  Bus-based shared memory machines,
however, are not scalable because the bus bandwidth is shared between
all the processors.

Cache coherent distributed shared memory (\ccdsm/) systems have been
advanced as a solution to the scalability problem.  \ccdsm/ systems
consist of multiple snoopy buses connected via an interconnection
network.  Some form of a directory-based cache-coherence protocol is
used to maintain cache coherence across multiple sites.  Machines in
this class include the Stanford
\dash/\cite{Lenoski90,Lenoski&others92}, the Kendall Square Research
KSR1\cite{Burkhardt92}, and the MIT \alewife/\cite{Agarwal91}, which
are all operational, and machines under design such as the Stanford
\flash/\cite{Kuskin94} and the University of Wisconsin
\typhoon/(a paper architecture).  All these machines are characterized
by a substantial amount of custom hardware to support directory based
cache coherence protocols.

The amount of hardware required to implement shared memory depends to
a large degree on the desired performance on a class of applications.
At one extreme, the underlying system supports only message passing.
Some have written compilers or libraries that can give the illusion of
shared memory.  Those schemes, however, use global memory in a highly
stylized manner and generally avoid coherence issues.
Others\cite{Li86,Li89a,Li89b} have implemented coherent shared memory
at page granularity by modifying the virtual memory manager to allow
demand paging from remote nodes.  These schemes work well in limited
contexts and are not suitable for building general purpose parallel
programming models. 

The \start/ project does provide a minimal amount of custom hardware
(\ie, ACD) to support directory-based cache-coherent shared memory on
a network of SMPs.  We hope to have extreme flexibility in
experimenting with cache coherence protocols by using one of the
processors in each SMP for protocol processing.  Our approach will
also allow us to explore the virtual memory management (VMM) aspects
of \ccdsm/, and to pursue language driven memory models such as
I-structures. Since almost all of the \ccdsm/ support is in software,
performance is invariably going to be compromised.  However, at this
stage it is not clear how much improvement in overall performance can
be expected from a more aggressive implementation.

Unlike traditional shared memory machines, where the entire machine
runs one copy of the operating system (OS), \start/ will run a
separate copy of the OS on each SMP site.  We believe that the
hardware resources at each SMP should be managed separately for fault
tolerance\footnote{Crashes due to the operating system occur more
frequently than crashes due to the hardware!} and scalability reasons.
Coordination across multiple SMPs, such as for work scheduling or VMM,
will be done as a layer on top of the standard OS running on each site.

%\outline{Message passing is still very important because extra
%capabilities, and basis for implementing \ccdsm/}

Although this paper is about \ccdsm/ on \start/, the message passing
capability of the machine is still of fundamental importance.  The
performance of the message passing system will have a direct impact on
the performance of the \ccdsm/ system.  User-level message passing
also provides additional capability -- the arrival of messages can be
used as a means of activating computation or performing
synchronization.  Other researchers\cite{Kranz93} have pointed out the
synergy between shared memory and message passing.  \start/, like
\alewife/ and \flash/, will support both.

\outline{Outline of paper}

The rest of this paper is organized as follows.  The next section
provides some background for the rest of the paper.
Section~\ref{sec:start-design} describes \start/ and outlines how we
plan to implement CCDSM.  Estimates for the performance of \start/'s
\ccdsm/ are included in that section.  In
Section~\ref{sec:ccdsm-issues}, we discuss the issues that we
encountered while implementing \ccdsm/.  Approaches for dealing with
the issues are discussed.  Most of these problems are not specific to
\start/.  The main contributions of this paper are the exploration of
very simple hardware for supporting cache-line granularity
cache-coherence, the identification of the problems of this and other
approaches, and the development of solutions for those problems.

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




%For programming purposes, however, one also needs to specify a {\em
%memory model}, \ie, how memory accesses are viewed and ordered by
%processors in the system. The most well known memory model is
%Lamport's strongly consistent sequential model where only an
%interleaving of sequential memory reference streams from processors is
%permitted.  For improved performance, people have designed ``weaker''
%consistency models.  There is yet another class of memory models, such
%as I-structures, which are motivated by concerns for parallelism.
%Though there is no general agreement on what is the best memory model
%for parallel programming, strong sequential consistency is a
%requirement for running most operating systems (including Unix) on
%Symmetric Multiprocessors (SMPs).

