\section{Introduction}
\label{intro}

One approach to designing shared-memory computer systems is to
specify a {\em memory model} upon which a variety of program
execution models may be implemented. This approach has been
used in the design of most shared-memory multiprocessors, which
are usually based on a memory consistency model derived from Lamport's concept of
{\em sequential consistency} \cite{Lamport79}. This requires
the execution of a parallel
program to appear as some interleaving of the memory operations
on a sequential machine. It has been argued that sequential
consistency is ``the property of the memory system preferred by
programmers''.

Alternatively, one may choose a desired program execution model (PXM)
and specify a memory model suited to the PXM. We argue that this
second approach is to be preferred because it avoids the trap of
specifying features of the memory model (consistency, for example)
that may not needed to implement a desired program execution model.

If the PXM is a dataflow model (one based on or equivalent to
recursive dataflow program graphs), then no cache consistency problem
arises if the memory model supports synchronizing memory operations. A
multiprocessor that implements such a program execution model can
support all determinate computation, including, for example, all
scientific computations expressible in the Sisal programming
language \cite{McGrawEtAl85,Cann92}.
As we have shown elsewhere \cite{DennisGao95}, a general class of
nondeterminate computations can be supported by adding a single
special memory operation on non-cached locations, without introducing
any additional consistency requirement to the memory model.

These circumstances raise the question: Why use a memory consistency model
as a basis for designing shared-memory multiprocessors? The consistent
memory approach is not the natural way to realize an efficient
machine that implements a sound and
effective program execution model. One argument is that a general
memory model can support a variety of PXMs. However, many good PXMs,
object-oiented programming, for example, may be built on top of a
basic program model that does not require memory consistency---our
dataflow model is an example.
Perhaps the principal justification for the consistent memory approach
is the desire to build massively parallel processors using conventional
RISC and superscalar processors---processors that do not offer
efficient support for synchronizing memory operations.
On the contrary, we believe that memory systems supporting synchronizing
memory operations will be cheaper to implement than memory consistency
protocols and will support a preferred class of program execution models.
This paper is written in support of this view.

We show how a general computing
capability can be specified and implemented without the memory
system satisfying any global coherence requirement.
We begin by presenting a dataflow program execution model that
uses {\em dataflow signal graphs} to represent function bodies, and
uses {\em incremental arrays}, arrays with I-structure
semantics, to represent data structures.
Next, an abstract multiprocessor architecture
is considered, and the interface of its memory system
and the role of a memory model are
discussed. A formal memory model is
presented that supports the dataflow signal graph program
execution model. Then we show how the abstract architecture may
be implemented with cache memory to achieve good performance
while satisfying the requirements of the model, and note that
``coherence'' of distributed memory is not an issue.

The closest realization of multiprocessor computer architecture
to the implementation scheme for dataflow graphs suggested here
is the Monsoon multiprocessor~\cite{PapadopoulosCul90}, but the principles may
be applied to other multithreaded architectures derived
from dataflow models.
