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

This paper describes some of the challenges we faced in designing a
parallel machine based on commercial SMPs.  Like most other
researchers\cite{Kranz93,Kuskin94}, we believe that a machine must
provide both a global address space and efficient message passing for
short messages to support a general programming model.  From an
implementation perspective, there is synergy between these two
requirements because creating the illusion of a global address space
across a network of SMPs or workstations requires efficient message
passing for short, particularly cache-line size, messages.  However,
due to the presence of caches in microprocessors, supporting shared
memory abstraction on a distributed memory machine is significantly
harder than pure message passing.

Researchers have devised a whole spectrum of techniques to implement 
shared address spaces on distributed memory machines.  At one extreme,
Li\cite{Li86,Li89a,Li89b} has implemented coherent shared memory at
page-level granularity without any hardware support beyond message
passing.  He does so by modifying the virtual memory manager to allow
demand paging from remote nodes.  This scheme has been reported to
work well in certain application areas.

At the other extreme are machines that provide extensive hardware
support for shared memory.  Some machines, such as the Cray T3D, allow
the user to access global memory in a cached or uncached fashion;
however, the hardware does not maintain cache coherence.  Machines
that support cache coherence beyond single-bus systems invariably need
some processing power to execute directory-based coherence protocols.
This has traditionally been provided by dedicated, and mostly custom
hardware.  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 the Stanford \flash/\cite{Kuskin94} and the
University of Wisconsin \typhoon/\cite{Reinhardt94} which are under
design.

We are currently undertaking the \start/ project to build an efficient
message passing machine using commercial SMPs based on PowerPC 620
microprocessors as the building blocks.  Each processor directly
connects to an MPP-class network via a network interface unit.  In
addition to supporting message-passing applications, \start/ supports
shared memory by augmenting the memory bus in each SMP with a simple
address capture device (ACD) which can be used in conjunction with one
of the processors to support various shared memory models.  Each SMP
{\em site} modified in this manner will still run a standard operating
system (OS) such as an SMP version of Unix.  We have chosen to run an
OS image per site as opposed to a single image on the whole system for
better fault tolerance.  \start/ will provide an inexpensive,
low-risk, and flexible experimental vehicle for exploring coherence
protocols for various memory models including
I-structures\cite{arvind90}, distributed operating system issues, and
application development in a hybrid message passing/coherent shared
memory environment.


This paper discusses some specific problems we encountered in
implementing cache-coherent distributed shared memory (\ccdsm/) on
\start/.  The problems we will discuss have origins in three
different sources: the processor and its snoopy bus
protocol\cite{Goodman83}, buffering within the system and the non-FIFO
character of the network.  Although the problems are discussed in the
context of \start/, and the PowerPC architecture, some of these
problems are likely to be present in any parallel coherent shared
memory system based with stock microprocessors or SMPs.  As we will
show, there are software solutions around most of these problems.
However, with a slightly different processor or bus design, some of
these problems can either be completely eliminated or their solutions
made much simpler.  We hope that these findings may influence the
design of future processors and snoopy bus protocols.


In Section~\ref{sec:background}, we will give the background
information necessary to understand the challenges we faced.  It will
describe those aspects of processors, memory buses, buffers and the
network that are relevant to implementing \ccdsm/.
Section~\ref{sec:start-design} gives a brief description of \start/ and
estimates of its performance.  In Section~\ref{sec:ccdsm-issues}, we
discuss the technical problems that we encountered while implementing
\ccdsm/.  It also proposes solutions.  The final section is a summary
of our recommendations.

