\section{\label{memory}The Abstract Machine Model}

A shared-memory multiprocessor consists of a collection of processors
and a distributed memory system organized so that each processor may
access any object held in the memory.  We view this general
architecture according to the {\em abstract computer system} model
shown in Figure~\ref{mem-sys-org}. In this model, the processors
interact with the memory system by presenting {\em commands}, and the
memory responds by storing information or returning {\em responses}
containing values of stored data. The Interprocessor Network supports
function application as discussed below.  In this section we describe
an architecture-independent memory model matched to our
dataflow program execution model.

\begin{figure}[tbh]
\begin{center}

\illustrationx{arch-model}{3in}

\end{center}
\caption{\label{mem-sys-org}Abstract computer system
   with memory system model.}
\end{figure}


\subsection{The Processors}

Before discussing characteristics of the memory system, let us
consider the nature of the processors. For simplicity we
assume that any one function activation is performed entirely
on one processor; that is, the instruction
instances corresponding to one instantiation of a
dataflow signal graph are all executed by the same processor.
This choice has been made in most, if not all, of the experimental
multiprocessors based on dataflow principles.

Given this choice, it makes sense to allocate memory for the
data frames of function activations in the processors executing them.
Then all references to variables held
in data frames will be local memory references, and may be performed
independently of the distributed memory system.

Function application is initiated by an {\tt APPLY}
instruction that starts the following sequence of events:

\begin{enumerate}

\item
A processor is chosen for executing the new function activation.

\item
A memory segment is allocated at the chosen processor for the
data frame of the new activation, and each cell of the data
frame is set to {\tt UNDEF}.

\item
A return {\em continuation} consisting of the data frame address
and the list of successors of the {\tt APPLY} instruction is
stored in the data frame of the new activation.

\item
The function argument value is placed in the argument location
of the data frame, and the start node is
enabled for execution.

\item
When a return node of the function is executed, the result
value of the function is delivered according to the successor
list.

\end{enumerate}

If a function has more than one argument or result value,
the argument or result values are made components of a (heterogeneous)
incremental array. This choice provides lenient evaluation semantics.
We assume that function initiation and termination are performed
using messages sent over the Interprocessor Network.


\subsection{The Memory System}


We wish to specify a memory system suitable
for supporting the nested function program execution model
introduced above. We insist that correct operation of the
system as a whole not depend on immediate responses to processors
from the memory system. To enforce this requirement, the 
memory system model in Figure~\ref{mem-sys-org}
includes a buffer (the Command Pool) for commands
that have been presented by processors, but have not yet
been acted on by the memory system.
The memory system acts upon commands chosen arbitrarily
(subject to fairness) from the Command Pool. Thus
any criterion of correct behavior must recognize that
commands may be arbitrarily delayed. (This is essentially
the network delay assumption for scalable multiprocessors.)

The basic memory operations are {\tt READ} and {\tt WRITE}.
For the purpose of supporting execution of
dataflow graphs, it is helpful to view the memory system
as a collection of locations where values may be placed
by one computing entity for use by other entities that
act concurrently. The {\tt WRITE} command is used to
place values in memory locations and the {\tt READ} command
is used to retrieve them.
Now, even if one could guarantee that each {\tt READ} is presented to the
memory system only after presentation of the corresponding {\tt WRITE},
it would be impossible to ensure that the memory system acts
on the {\tt WRITE} before acting on the {\tt READ}. This is because
either command may remain in the Command Pool arbitrarily
long before being selected for action.
For this reason we specify the memory system so that
a pair of {\tt READ} and {\tt WRITE} operations on the same memory
location has the same effect regardless of which operation is
acted upon first. This requires that they be ``synchronizing''
shared-memory operations, which is just what is needed to support
I-structure operations.

Here we give a specification in the Haskell
language of the Action Control module of the memory system.
The command messages sent to the memory
have the following formats:
\begin{verbatim}
  data Request =
     READ Address Node Continuation  |
     WRITE Value Address
\end{verbatim}
In these formats the data type {\tt Address} is the set of
(global) memory locations, {\tt Value} is the set of
possible contents of memory locations, {\tt Node} is
the set of processor identifiers, and an entity of type {\tt Continuation}
contains information that identifies a specific activity to be continued
by the requesting processor upon completion of the command. For
our program model a continuation would consist of the address
of a data frame and the offset of the instruction to be activated
within the program segment of the function. (The address of the
program segment could be included in the continuation, but it is
usually preferable to retrieve it from the data frame.)

Messages sent by the memory system to processors in response
to {\tt READ} commands have the format:

\begin{verbatim}
  data Message =
     (MESSAGE Node Response)
  data Response =
     REPLY Value Continuation
\end{verbatim}

The state of the memory system consists of a pool of Request messages that
have been presented by processors to the memory system, but have not
been acted upon, and a mapping from addresses to memory items:
\begin{verbatim}
   data MemoryState :: ([Request], MemoryMap)
   data MemoryMap :: Int -> MemoryItem
\end{verbatim}
Items are of the following kinds:
\begin{verbatim}
   data MemoryItem =
      (UNDEF)          |
      (DEFINED Value)  |
      (QUEUE [Entry])

   data Entry =
      (ENTRY Node Continuation Entry) |
      (EMPTY)
\end{verbatim}

The memory system acts on request messages according to the
rules given in Figure \ref{rule-figure}. A {\tt READ} request
contains the address of the location to be read, the
processor identifier, and a continuation that specifies the
instruction instance that should receive the value read.
If the state of the location is {\tt DEFINED}, the value is
sent in a response to the processor.
If the state is undefined ({\tt UNDEF}),
the {\tt READ} request has to be the first read access to the location.
In this case it creates a queue with the {\tt node} and
{\tt continuation} in its first entry.
If the state of the location contains a queue, it just adds
a new entry to the queue.
A {\tt WRITE} request contains a value and the address
of the location where the value is to be written.
If the state of the location is undefined ({\tt UNDEF}),
it writes the value into the location and changes the
state to defined ({\tt DEFINED}).
If the state is a queue, it writes the value into the location and
sends a response message for each entry in the queue.
If the state is found to be defined ({\tt DEFINED}), it signals an error.

\begin{figure}[tbh]\small
\begin{verbatim}
  MemoryAction :: Request -> MemoryMap ->
                          ([Message], MemoryMap)
  MemoryAction (READ address node continuation) map =
    let item = map address
    in case item of
        (UNDEF)  -> let
            q = (ENTRY node continuation (EMPTY))
            map' = MapUpdate map address (QUEUE q)
          in ([], map')
        (QUEUE q) -> let
            q' = AddToQueue node continuation q
            map' = MapUpdate map address (QUEUE q')
          in ([], map')
        (DEFINED value) ->
             (SendReply value node continuation map)
  MemoryAction (WRITE value address) map =
    let item = map address
    in case item of
        (UNDEF) -> let
            map' =
                MapUpdate map address (DEFINED value)
          in ([], map')
        (QUEUE queue) ->let
            msgs = MakeResponses queue node value
            map' =
                MapUpdate map address (DEFINED value)
          in (msgs, map')
        (DEFINED value) -> ERROR

  SendReply value node continuation map = let
      content = (REPLY value continuation)
      msg = (MESSAGE node content)
    in ([msg], map)
  MakeResponses queue node value =
    case queue of
      [] -> []
      [(ENTRY node continuation):queue'] -> let
          content = (REPLY value continuation)
          msg = (MESSAGE node content)
        in [msg:(MakeResponses queue' node value)
\end{verbatim}
\caption{\label{rule-figure}The memory transition rules
   for the abstract computer system. In Haskell
  the prime character (') is valid in identifiers and primed
  identifiers are often used to denote the modified value of
  an object. Note that {\tt map} denotes a function that maps locations into
  items, so {\tt map location} evaluates to the memory item
  of interest. The function {\tt MapUpdate} yields a new mapping in
  which the specified location contains the specified item. Code
  for the auxiliary functions {\tt SendReply} and {\tt MakeResponses} is included.
  }
\end{figure}
