% Section on abstract model.

\section{{\archname} Instruction Set Architecture}

\label{sec-abstract-model}

Figure \ref{fig-start-node} depicts the logical view of a {\archname}
node with three separate, asynchronous coprocessors, each of which can
be regarded as a conventional (\eg\ RISC) processor with a few
extensions.  In this section, we flesh out this view by describing
these extensions.  Since {\sc RMem} and {\sc sP} are very similar, our
description here will not distinguish them (we postpone to Section
\ref{sec-implementation}
a more detailed discussion of physical implementations that may
separate or multiplex them).

Both {\sc sP} and {\sc dP} execute instruction streams.  For clarity,
we distinguish labels for the two coprocessors by the subscripts $S$
and $D$, respectively (\eg\, {\cf L$_S$,~L$_D$,~M$_S$,~M$_D$,~...}).

We will look at messages in more detail shortly, but for now it is
enough to know that each message has the form:
\begin{quote}\cf
    <{\em  IP},   {\em Address},  {\em Value1\/}, {\em Value2\/}, ...>
\end{quote}
{\cf Address} is a global address that identifies a unique destination
node in the MPA, and is typically a frame pointer {\cf FP} or an
address of a location in the heap.  The message is automatically routed
there.  Of course, messages from a node to itself are short-circuited
back directly.

We assume that a {\em context\/} for a computation is represented
simply by an address in memory.  In the spaghetti stack model, this
may be a stack pointer or a pointer to a frame in the stack.  In an
object oriented model, this may be a pointer to an object.  For
uniformity, we will use the term {\em Frame Pointer\/} {\cf FP} to
refer to a context.

We assume that frames or contexts do not span nodes in the MPA, \ie\
{\em each context resides entirely within one node\/} of the MPA.
Thus, {\cf FP} may be regarded as a pointer to the collection of local
variables of that context.  A frame pointer encodes a node number.
Thus, a continuation is given by {\cf <IP,~FP>} where {\cf IP} is a
pointer to an instruction on the same node encoded by {\cf FP}.  This
model of locality is not restrictive in any way--- parallel procedure
calls and loop iterations may be distributed to different nodes by
giving them separate contexts (see \cite{Nikhil90e} and
\cite{Culler90a,Schauser91} for more on programming and compilation).

It may be desirable to allow contexts to migrate across MPA nodes for
load balancing and locality reasons.  However, that capability is
orthogonal to our discussion here and, for simplicity, we assume that
frames, once allocated, do not migrate (a virtual-to-physical FP
mapping, plus forwarding, may be added in the manner of the
MDP~\cite{Dally87a} or Empire.\footnote{Empire was the machine being
built at IBM Research based on Iannucci's Dataflow/von Neumann
Hybrid Architecture~\cite{Iannucci88a}.}

\subsection{The Data Processor}

The Data Processor {\sc dP} is a superset of a conventional RISC
processor, with a conventional repertoire of register-to-register
instructions and ability to manipulate local memory using conventional
load and store instructions.  Its program counter is called {\cf dIP}
(``Data processor Instruction Pointer'').  One of its registers,
called {\cf dFP}, is assumed, by convention, to contain the current
Frame Pointer for the thread being executed by the {\sc dP}.  Being a
conventional RISC processor, the Data Processor is optimized to run
sequential threads efficiently.  It obtains the starting points of
these threads from the continuation queue using a {\cf next}
instruction.  Each such thread is run to completion, {\ie} there is no
concept of a thread ``suspending'' in the Data Processor.  On
completion of a thread, if there is no new thread available from the
continuation queue, the Data Processor simply waits until one is
available.

In addition to conventional RISC instructions, the Data Processor can
execute a few additional instructions which are summarized in Figure
\ref{fig-dp-table}.
\begin{figure}
\hdivider
\begin{center}
\begin{tabular}[t]{|l|l|}
\hline
{\sc dP} instruction & Semantics \\
\hline
\hline
{\cf start rIP, rFP, rV}  &  Send message: {\cf <L$_S$, FP, V>} \\
\hline
{\cf next}                &  Load ({\cf L$_D$},{\cf FP'}) \\
                          &  from continuation in \\
                          &  continuation queue \\
                          &  into registers {\cf (dIP,dFP)} \\
                          &  (so, execution continues at {\cf L$_D$}) \\
\hline
{\cf rload rIP, rA}       &  Send message: \\
                          &  {\cf <rload\_handler$_S$, A, L$_S$, FP>} \\
\hline
{\cf rstore rA, rV, rIP}  &  Send message: \\
                          &  {\cf <rstore\_handler$_S$, A, V, L$_S$, FP>} \\
\hline
\end{tabular} \\
{\cf L$_S$} = {\cf Register[rIP]}, {\cf FP} = {\cf Register[rFP]}, \\
{\cf V}     = {\cf Register[rV]},  {\cf A}  = {\cf Register[rA]}
\end{center}
\caption{%
    \label{fig-dp-table}
    {\sc dP} extensions to conventional instruction set.
        }
\hdivider
\end{figure}
(The notation {\cf Register[$j$]} refers to the $j$'th {\sc dP}
register.)  Most of them send messages into the network.  These are
non-blocking, {\ie} the Data Processor continues executing after
sending a message (so, they are implicit forks).  The message can
cause threads to be scheduled on the other nodes or on the same node,
and a later response may deposit values in the sender's frame.

The {\cf start} instruction starts a new thread in a different
context.  For example, suppose function $F$ calls another function
$G$.  The frames for these functions may be on different nodes (hence,
different contexts). Thus, {\cf start} instructions are used by $F$ to
send arguments and initiate threads in $G$, and {\cf start}
instructions are used by $G$ to to send results and resume threads in
$F$.  Since {\cf start} instructions are non-blocking, it is possible
to perform parallel function calls and coroutines.  Note that
instruction pointer {\cf L$_S$} on the start message is a label for
the target node's {\sc sP}, not {\sc dP}.\footnote{A {\cf start}
message corresponds exactly to a dynamic dataflow
token~\cite{Arvind90a}--- {\cf FP} is the context or color, {\cf
L$_S$} is the instruction pointer or statement number and, of course,
{\cf V} is the value on the token.}

The {\cf next} instruction terminates the present {\sc dP} thread by
loading a new continuation, after which the {\sc dP} is executing a
new thread.  Note that there is no implicit saving or restoring of
registers.  In general, at the beginning of a new thread, no
assumptions can be made about the contents of any {\sc dP} registers
except {\cf dFP}.  We also say that registers are ``volatile'' or
``ephemeral'' across threads.  This instruction is similar in effect
to Monsoon's {\sc stop} instruction~\cite{Papadopoulos88a} and the
MDP's {\sc suspend}~\cite{Dally87a}.

We will discuss the {\cf rload} and {\cf rstore} instructions shortly,
after describing the Synchronization Coprocessor.

\subsection{The Synchronization Coprocessor}

{\sc sP}, the Synchronization Coprocessor, also looks very much like a
conventional RISC microprocessor--- it has a program counter {\cf
sIP}, general purpose registers, and it can load and store to local
memory.  Unlike a conventional RISC, it is tuned for very rapid
disposition of incoming messages instead of the computation of
arithmetic expressions.  In particular, some of its registers ({\cf
sIP}, {\cf sFP}, {\cf sV1}, {\cf sV2}, ...) are loaded directly from
messages, there is datapath support for {\cf join} operations, and it
can post {\cf <FP,L$_D$>} pairs into the continuation queue.  In the
following, we do not disinguish it from {\sc RMem}, which is very
similar.

Like a dataflow processor, {\sc sP} is triggered by the arrival of a
network message (it simply waits, if there is none available).  When
it picks up a message, its registers {\cf sIP}, {\cf sFP}, {\cf sV1},
{\cf sV2}, \etc\ are loaded with the corresponding values from the
message, after which it begins executing instructions from the address
in {\cf sIP}.  The unconventional instructions of {\cf sP} are
summarized in Figure \ref{fig-sp-table}.
\begin{figure}
\hdivider
\begin{center}
\begin{tabular}[t]{|l|l|}
\hline
{\sc sP} instruction & Semantics \\
\hline
\hline
{\cf start rIP', rFP, rV}   & Send message: {\cf <L$_S$, FP', V>} \\
\hline
{\cf next}                  & Load ({\cf L$_S$},{\cf A},{\cf V1},{\cf V2}, ...) \\
                            & from message in \\
                            & message queue into registers \\
                            & {\cf sIP,sFP,sV1,sV2,...} \\
                            & (so, execution continues at {\cf L$_S$}) \\
\hline
{\cf post rIP, rFP}         & Post {\cf <FP', L$_D$>} \\
                            & into continuation queue \\
\hline
{\cf join $ctr$, $tc$, rIP} & {\cf Memory[FP + $ctr$] := } \\
                            & \hspace{1em} {\cf Memory[FP + $ctr$] + 1} \\
                            & If {\cf Memory[FP + $ctr$]} $\geq tc$ then \\
                            & \hspace{1em} Post {\cf <FP, L$_D$>} \\
                            & \hspace{1em} into continuation queue \\
                            & \hspace{1em} {\cf Memory[FP + $ctr$] := 0} \\
\hline
\end{tabular} \\
{\cf L$_S$} = {\cf Register[rIP']}, {\cf L$_D$} = {\cf Register[rIP]}, \\
{\cf FP'}   = {\cf Register[rFP]},  {\cf FP}    = {\cf Register[sFP]} \\
{\cf V}     = {\cf Register[rV]},   {\cf A}     = {\cf Register[rA]}
\end{center}
\caption{%
    \label{fig-sp-table}
    {\sc sP} extensions to conventional instruction set.
        }
\hdivider
\end{figure}
(The notation {\cf Register[$j$]} refers to the $j$'th {\sc sP}
register.)

The {\cf start} instruction is identical to the Data Processor's {\cf
start} instruction--- it starts a new thread in a different context.
This allows it to respond to incoming messages directly. For example,
in an {\cf rload} request message, the {\em IP\/} field points to {\cf
rload\_handler$_S$}, the {\em address\/} field contains the address to
be read, and the {\em V1\/} and {\em V2\/} fields contain the return
continuation (return IP, return FP).  The handler code looks like
this:
\beginid
rload\_handler$_S$:
  load   rX, sFP[0]   -- sFP {\em has addr to read (A)}
  start  sV1, sV2, rX -- {\em create response message \/}
  next                -- {\em done; handle next message\/}
\endid
Similarly, here is the handler for remote stores (the message's {\em
V1}, {\em V2\/} and {\em V3\/} fields contain the value to be stored
and the return continuation, respectively):
\beginid
rstore\_handler$_S$:
  store  sFP[0], sV1  -- sFP {\em has addr to write (A)}
  start  sV2, sV3, 0  -- {\em create acknowledgment message \/}
  next                -- {\em done; handle next message\/}
\endid
The acknowledgement may be used to ensure serial consistency--- the
destination thread executes under a guarantee that the store has
completed--- or to return miscellaneous status information.  Omitting
the return continuation from the message and the {\cf start}
instruction from the handler implements unacknowledged stores.
Similar handlers may also be coded on the MDP~\cite{Dally87a}.

The {\cf next} instruction ends the present {\sc sP} thread by
reloading its registers from the next message, after which it is
executing that message's handler.

The {\cf post} instruction allows {\sc sP} to post a thread to {\sc
dP} by inserting a continuation into the continuation queue.  Recall,
this thread will be executed by the {\sc dP} when it is popped off the
continuation queue by the {\sc dP} issuing a {\cf next} instruction.
Here is a typical {\sc sP} code sequence that executes for an incoming
message that loads label {\cf L$_S$} into {\cf sIP} (for example, this
message may be the response to a remote load):
\beginid
L$_S$:
  store  sFP[T], sV1 -- {\em store incoming val at frame offset\/} T
  post   L$_D$, sFP     -- {\em enable thread\/} L$_D$ {\em with}
                     --     {\em this frame in DP}
  next               -- {\em done; handle next message}
\endid
The {\sc dP} thread at {\cf L$_D$} is assured that the remote load has
completed.

The {\cf join} instruction allows fast join synchronization using
synchronization counters in the frames. Because this is a very
frequent operation for the {\sc sP}, we provide special hardware
support to accelerate join operations.  The {\cf join} instruction
implements an atomic test-and-increment semaphore on a location in the
current activation frame called a {\em join counter.} The {\cf join}
instruction {\em conditionally posts\/} a thread to the continuation
queue only if incrementing the join counter causes it to reach the
terminal count (given by $tc$).  It is assumed that a newly allocated
activation frame will have all of its join counter locations
initialized to zero.  Observe, the {\cf join} instruction implements a
self-cleaning protocol by returning the counter to zero after the
terminal count has been reached (this is similar to the wait-match
operation in dataflow architectures~\cite{Arvind86a}).

{\sc sP} message handlers correspond almost exactly to {\em inlets\/}
in the TAM model~\cite{Culler90a}. This style of message handling is
also easy to code for the MDP~\cite{Dally87a}, although there is no
dedicated logic for fast n-ary join synchronization.  The salient
difference is that in {\archname} the message handlers (inlets) and
the computation threads are processed by two logically distinct and
asynchronous processors.

Turning back to {\sc dP}, it can initiate remote loads and stores
using {\cf rload} and {\cf rstore} instructions, each of which sends a
message.  The destination node is implicit in the global address {\cf
A}, which is used to route the message there.  We have already shown
the remote {\cf rload} handler code.  Observe, the response contains
{\cf FP} in its {\em address\/} field, so it is routed back to the
node that issued the {\cf rload}.  Since {\cf rload} and {\cf rstore}
are also forks, we can initiate many remote accesses before receiving
any response.  The responses may return in any order.

Note that the typical {\cf rload} sequence copies a remote value into
a local {\em frame\/} location, and not a register.  Although this
means that another (local) load instruction is necessary to move it
from the frame to a register, the choice is deliberate: it allows the
thread that issued the {\cf rload} to easily relinquish {\sc dP}
before the result comes back.  Our choice recognizes the fact that
storing the value in the frame would be necessary anyway if {\cf
rload} returned to a failing join or if it was a synchronizing load.

% We note that an implementation might want to hardcode the {\cf rload}
% and {\cf rstore} message handlers in the synchronization coprocessor
% {\sc sP} with specialized hardware in order to improve their
% performance and offload the {\sc sP}. However, a nice aspect of their
% implementation as {\sc sP} message handlers is that they are readily
% extended to perform a variety of synchronization operations such as
% synchronizing loads and stores ({\cf iload} and {\cf istore}),
% M-structures and Fetch-and-$\phi$.

{\em Address Hashing\/}: It is useful to have different kinds of
address maps for different kinds of objects.  For example, we may wish
to interleave large data structures such as vectors and matrices
across the MPA nodes.  On the other hand, we may wish code segments,
stack frames and small objects to be addressed linearly within a
node's local memory.  Of course, these variations in address hashing
could be performed in software, but with large overhead.  In
{\archname} we intend to provide hardware support for address
randomization in a manner similar to the IBM RP3 \cite{Pfister85a} or
the Tera \cite{Alverson90a}.  A logical place for this mapping is in
the Message Formatter.
