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

This paper describes the challenges we have faced in designing a
parallel machine based on commercial SMPs.  We, like most other
researchers, believe that to support a general programming model, a
machine must provide both a global address space and efficient message
passing for short messages.  From an implementation perspective, there
is some 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 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 a
shared address space 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
provide some processing power to execute directory-based coherence
protocols.  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).  

Our project, called \start/, is an attempt to build an efficient
message passing machine using commercial SMPs based on PowerPC 620's.
Each processor directly connects to an MPP-class network via a network
interface unit.  The memory bus in each SMP is augmented 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.

In addition to supporting all kinds of message-passing applications,
we would like to run parallel applications written for SMPs on
\start/.  This requires that we implement cache coherent global memory
across sites.  We think that \start/ will provide an inexpensive,
low-risk, and flexible experimental vehicle for exploring coherence
protocols for various memory models including I-structures\cite{},
distributed operating system issues, and application development in a
hybrid message passing/coherent shared memory environment.

The main contribution of this paper is the identification of some
specific problems in implementing cache-coherent distributed shared
memory (\ccdsm/) on commercial SMPs.  The problems we will discuss
have origins in three different sources: the processor and its snoopy
bus protocol, buffering within the system and the non-FIFO character
of the network.  Though the problems are discussed in the context of
PowerPC, we think some of these problems are likely to be present in
any parallel coherent shared memory system based on stock
microprocessors.  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 the next section, we will give the background information necessary
to understand the challenges we faced.  It will describe particular
aspects of processors, memory buses, buffering and the network without
getting into the problems they may cause.  Section~\ref{sec:start}
describes the \start/ implementation and how we plan to implement
\ccdsm/ with a small piece of custom hardware and a dedicated
processor.  Estimates for the performance of \start/'s \ccdsm/ are
included in that section.  In Section~\ref{sec:ccdsm-issues}, we
discuss the challenges that we encountered while implementing \ccdsm/.
The final section gives some conclusions.

