\section{Dataflow Signal Graphs}

We wish to use a program execution model that
has good generality so the concepts and principles discussed
will be credible for a broad range of compter applications.
We also wish to keep the model simple to avoid needless
complexity. For generality, the model must encompass
recursive nesting of function activations, and it must allow data
structures of arbitrary extent to be created, accessed,
and released.

We have chosen a dataflow model because it provides a simple
semantic basis for parallel computing that encompasses the
desired level of generality. The particular dataflow model
is based on the graph/heap model \cite{Dennis74},
but with function bodies specified
using named variables and activation of actors by signals. We call this model
{\em dataflow signal graphs}. This choice provides a straightforward
mapping to the computer system and memory models that are the
subject of this paper.

For writing textual program examples we
will use the Haskell language~\cite{HudakEtAl91}.
We use a functional language, not so much for the ease of 
programming it yields, but because functional programming languages
express parallelism implicitly---without use
of any explicit parallel processing commands. A compiler can readily
translate functional programs into implicitly parallel
dataflow code. Figure~\ref{insert-search} shows Haskell
text representing two recursive
functions that, respectively, insert intergers
into an ordered list, and search for an integer in
the list. Figure~\ref{insert-dfg} shows  the {\tt Insert} function
represented as a {\em dataflow program signal graph}.
Each actor (denoted by a box) specifies an {\em action} that occurs after all
predecessor boxes (or the {\em start} node) have completed their
actions. A directed arc ({\tt u},{\tt v}) between
two actors {\tt u} and {\tt v}
in the graph denotes that when {\tt u} finishes its action,
a signal is to be sent to node {\tt v} to signal its completion.
Therefore we call these {\em signal arcs}.

\begin{figure}[tb]\small
\begin{verbatim}
  data Set =
     EMPTY |
     NONEMPTY int Set

  Insert set n :: Set -> Int -> Set  

  Search set n  :: Set -> Int -> Bool

  Insert set n =                     Search set n =
    case set of                        case set of
      EMPTY -> NONEMPTY n (EMPTY)        EMPTY -> FALSE
      NONEMPTY m rest ->                 NONEMPTY n rest -> TRUE
        if m > n then                    NONEMPTY m rest ->
          NONEMPTY n set                   Search rest n
        else
          NONEMPTY m (Insert n rest)
\end{verbatim}
\caption{\label{insert-search}The {\tt Insert} and {\tt Search}
  functions written in Haskell.}
\end{figure}

An action is an operation that
reads values of input variables, performs computation, and
possibly assigns results to an output variable. Some
boxes, drawn as oblongs, perform tests on input variables
and signal successor boxes depending on
outcomes of the tests. Application of a function
causes: new instances of the function's variables to be created
and initialized with the undefined value; argument
values to be made available to the new activation; and the {\em start}
node of the called function graph to be enabled. When the application
terminates, the result value is	assigned
to a specified variable of the caller. Each variable must be
assigned a unique and unambiguous value (or not be assigned or
referenced) in any instantiation
of the program graph. So that this is true, all data dependences
between variables in a program graph must be represented
by the partial order defined by the signal arcs of the graph. 

Incremental arrays are implemented using I-structure operations
~\cite{ArvindNikPin89}.
The {\tt CREATE~n} operation creates (as a heap node) an array of $n$
elements indexed by integers $0, ... , n-1$ in which each element
has the value {\tt UNDEF}, meaning undefined. The {\tt CREATE} operation
yields a {\em pointer} to the heap node that may be held by a variable, stored
as an array element, and used to store and access elements
of the array. An action {\tt A[i]:v}
defines element {\tt i} of array {\tt A} to have the value {\tt v}.
Any reference {\tt A[i]} to an array element completes (yielding
the element value) only when the element has become defined.

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

\illustrationx{insert-graph}{5in}

\end{center}
\caption{\label{insert-dfg}Dataflow program graph for
   the {\tt Insert} function.}
\end{figure}

Haskell programs and the dataflow signal graphs derived from
them, as we have described them here, are
{\em determinate}---the result of any function evaluation is
independent of the order in which enabled nodes of the graphs
are chosen for execution. The extension of the dataflow model
to include nondeterminate computations is discussed in
\cite{DennisGao95}, where it is shown how typical programs
may be implemented using a single special memory operation, {\tt SWAP},
which operates on non-cached memory locations, so that their
correct execution does not
depend on a memory consistency model.



