%\documentstyle{csart}

%\begin{document}

%\newenvironment{linear}{\\ \begin{minipage}[t]{\textwidth}}{\end{minipage}}

\section{\label{implement}A Practical Organisation}

     The implemented version of the scheme described in section
\ref{spawn} supports a wider spectrum of channel connectivity than
just fully connected,  all-to-all networks.  Specifically, networks which are
``cartesian products'' of all-to-all graphs are also allowed.  For example,
a cartesian product of $d$ graphs, each of which is a two-element
``all-to-all'' graph (ie, a pair of connected nodes) would be
a possibility---this is just a $d$-dimensional
binary hypercube.  As another example, a product of two all-to-all graphs is
a generalised grid, with connectivity intermediate between a
nearest neighbour 2$d$ mesh and a fully connected network (any pair
of sites with the same $x$ coordinate or the same $y$ coordinate is directly
connected).

     Additionally, external IO channels connecting a given process
array of this
general type with external processes have to be considered.  This aspect
will be skirted in the discussion below, because the implemented mechanism
is fairly complicated.

     To simplify bookkeeping (and also to improve abstraction)
the parameters passed to the user process \verb$worker$ in figure
\ref{spawnocc} are bundled into a single data structure which will
be referred to as an ``index'' structure.
The primary fields in an index structure
(in its current incarnation) are a vector of out ports and
a vector of in ports, the number, $N$, of
sites connected by the structure, and the coordinate, $id$, of the
local site.  $N$ is the also the size of the port vectors.

     One can also think of the
sum of the individual index data structures held in each process
as a single {\em distributed} data structure.  Adopting this viewpoint,
it seems natural to make the logical leap of regarding
the whole procedure of spawning a process network connected by such
a distributed structure as the operation of {\em declaring} the
distributed index.  The operation
\begin{linear}
\begin{verbatim}

    spawn.net (N) 

\end{verbatim}
\end{linear}
(see figure \ref{spawnocc})
is regarded as an implementation of something like (in yet another,
higher level, meta-language) 
\begin{linear}
\begin{verbatim}

    [N] INDEX x :
    worker (x)

\end{verbatim}
\end{linear}
This notation won't be elaborated very far here.  The idea is that
the above fragment invokes $N$ parallel copies of {\em worker},
which can communicate amongst themselves through the distributed
index $x$ brought into scope by the ``declaration''.
This notation also gives a natural expression
of the more general class of networks described above.
For example the generalised grid mentioned there can be represented by
\begin{linear}
\begin{verbatim}

    [N] INDEX x :
    [M] INDEX y :
    worker (x, y)

\end{verbatim}
\end{linear}
Here the scope of the index $x$ is a process which in turn
``declares an index'' $y$.

     In practical terms this means that it should be possible
for the operation fulfilling the role to \verb$spawn.net$
to be invoked recursively.
Moreover, there has to be a mechanism for the 
existing index $x$ to be passed through the \verb$spawn.net$ analogue
to the user
processes \verb$worker$ (unlike the simplified implementation
of figure \ref{spawnocc}, which only passes the components of the
{\em new} ``index structure'' to the user code).

     To make these issues much more concrete we'll now introduce
some fragments of actual occam code (by contrast, most of the previous
fragments were written in various sorts of ``pseudo-occam'').
Suppose one wants to execute the procedure
\footnote{Note: The existing implementation is written in {\em occam}.  It
freely exploits the dingier machine-oriented fringes
of the language, especially
for simulating structures and pointers to them.  My convention
is to use an \verb$INT32$ variable to hold a pointer.
Although these kinds of
things are very clumsy in standard {\em occam}, the language has some
advantages over, say, {\em C} for the very communication-rich
procedures described in this section.}
\begin{linear}
\begin{verbatim}

    PROC worker (INT32 x, y)

      ...
    :

\end{verbatim}
\end{linear}
at all sites in a two dimensional array of processes.  The arguments
$x$ and $y$ are (pointers to) the appropriate local index structures
necessary for communication in the array.  Assume that a one-dimensional
process array ``indexed by'' an index $y$ already exists.  The procedure
executing in this array is called \verb$parent$, say.  For \verb$parent$
to initiate the desired two-dimensional array it makes the following
calls:
\begin{linear}
\begin{verbatim}

    PROC parent (INT32 x)

      [2] [PARAM.size] INT params :
      SEQ
        PARAM.index (params [0], x)
        PARAM.index (params [1], INT32 NULL.PTR)

        CONF.index.declare (M, proc.base, proc.stride,
                            "worker.cah", params)
    :

\end{verbatim}
\end{linear}
The first two steps load the two parameters for the \verb$worker$
call into an array {\em params} (the detailed representation of this
array needn't
be known---a series of library procedures similar to \verb$PARAM.index$
are provided, one to load each possible type of parameter).
Loading the first parameter, $x$, into the {\em params} array is
fairly self-explanatory.  The second parameter, $y$, however, is
precisely the object that doesn't yet exist.  The convention is to 
place a null pointer in the parameter array wherever the new index
structure is to appear in the actual parameter list.
Once the parameter array has been assembled it is passed to the
\verb$CONF.index.declare$, together with the name of the file containing the
code for \verb$worker$, and the size {\em M} of the new array
dimension.  The other two parameters of \verb$CONF.index.declare$,
{\em proc.base} and {\em proc.stride},
define processor placement of the processes dynamically created by
this utility.

     \verb$CONF.index.declare$ is a generalisation of the \verb$spawn.net$
procedure of section \ref{spawn}.  The initial array of \verb$parent$
processes will itself presumably have been initiated by a previous call
to the same routine.  In fact
\begin{linear}
\begin{verbatim}

    [1] [PARAM.size] INT params :
    SEQ
      PARAM.index (params [0], INT32 NULL.PTR)

      CONF.index.declare (N, proc.base, proc.stride,
                          "parent.cah", params)

\end{verbatim}
\end{linear}
is then a direct translation of the nested index declaration fragment
above, apart from the matter of specifying the processor placement
arguments to \verb$CONF.index.declare$.  Specification of these has been
deliberately overlooked here, anyway.

     The need to pass arbitrary parameters to the ``scope'' procedure
\verb$CONF.index.declare$ suggests a more elaborate organisation
for this routine than that of \verb$spawn.net$.  For one thing,
there's no absolute compunction for the newly declared index to
be passed to the scope procedure at all.  Something like
\begin{linear}
\begin{verbatim}

    [0] [PARAM.size] INT params :
    SEQ
      CONF.index.declare (N, proc.base, proc.stride,
                          "worker.cah", params)

\end{verbatim}
\end{linear}
ought to be legal.  This invokes $N$ identical instances of a parameterless
procedure \verb$worker$ in parallel.  It is pointless, because,
without an index structure containing the local process id, there's no
way for these processes to behave differently on the basis of their
location---in other words they are condemned perform exactly the same task,
redundantly (in this case, with no parameters at all, they can't
communicate their identical results to the outside world, anyway).
It may be pointless, but it still ought to {\em work}.

     This suggests that the operation of spawning the processes ought
to be logically separated from the operation of providing them with
a set of communication structures.  Rather than extending the communication
structure as the recursion goes along, passing the new channels to the
child processes directly through their parameter lists, it seems a
bit simpler to first recursively spawn a set of processes connected
in a tree-like
manner, rooted on the parent.  The leaves of the tree are
the new ``worker'' processes.  The intermediate nodes are auxilliary
processes used only to support the spawning procedure.  Likewise,
the channels of the tree are service channels used only in getting
parameters from the parent to the workers (and back again, as
necessary).  Communication structures demanded by the parameter
list of the worker process are sent out from the root along
the service channels, extended
as required in each layer of auxilliary nodes by operations like
\verb$ports.extend$, and eventually reach the worker processes in
their fully fleshed-out form, where they are assembled into
the proper data structures before being passed to the ``user process''.

     Where \verb$spawn.net$ restricted use of dynamic channels to
the channel copying operations described in section \ref{spawn},
this new organisation makes general use of the assumed capability
to send channels (or ports) on channels.

\begin{figure}
\centerline{\psfig{figure=tree1.ps,height=3.5in}}
%\vspace{45\baselineskip}
\caption{\label{tree}Spawning a 2-dimensional array from a 1-dimensional one}
\end{figure}

     To illustrate the procedure, consider \verb$parent$
in the earlier code fragment.  This initially executes in a one dimensional
array of processes connected by $x$ (figure \ref{tree}a).
\verb$CONF.index.declare$ first creates the process tree(s) illustrated
in figure \ref{tree}b.  (There is a set of independent trees
here, one for each $x$ coordinate.  Initially there is no connection
between these trees.)  The only initial channel connections are those
between nodes and their children within the tree.  \verb$Extend$
is an auxilliary type of process, used only for purposes of
spawning processes and passing parameters to them.

     The next stage is to send copies of the $x$ structure (the first
parameter) to the \verb$Worker$ nodes.  The method is to copy all
channels in \verb$Parent$s $x$ structure, and send these channels to
the first layer of \verb$Extend$ nodes.  These nodes make two copies
of the incoming channels, and send one to each child \verb$Extend$ node.
They repeat the procedure, sending the new channels to
the worker \verb$Worker$ nodes, where the incoming channels are
assembled into structures for passing to the instance of the
user procedure \verb$worker$.  This leads to figure \ref{tree}c.

     Now the second parameter, a $y$ index structure, has to be
delivered to the \verb$Worker$ nodes.  The procedure for this is
very similar to that of \verb$spawn.net$.  \verb$Parent$s role is
similar to the body of that procedure---it just creates a new channel
locally.  Rather than passing this channel as a parameter to a recursive
procedure, it outputs the channel to the first \verb$Extend$ node of
the tree.  The \verb$Extend$ nodes read incoming channel vectors,
perform the \verb$ports.extend$ operation on these vectors, and
send the {\em new}, extended port vectors to their children.
This leads to the final figure \ref{tree}d.  Once the index structures
have been delivered to the \verb$Worker$ nodes many channels
created in the intermediate nodes can be disposed of.

     Some remarks about this organisation:
\begin{enumerate}
\item Apart from the fact that they have several output channels
the \verb$Extend$ nodes behave pretty much like simple filters; they
read a stream of parameters, process each parameter in turn in some way,
and output the results.
\item Because of this there is an implicit pipelining of the operation
of sending out parameters.  In the above example the first level of
\verb$Extend$ nodes may start processing the $y$ parameter before the
second level has finished processing the $x$ parameter.
\end{enumerate}

     What kind of parameters can be passed through \verb$CONF.index.declare$?
Index structures have already been mentioned.  Vectors of index structures
can also be passed.  Ordinary data arrays can be passed in to the
scope process, and returned, provided their values are global.
Also a second kind of communication structure, used for IO between
an array process and the outside world can be passed; vectors of
{\em these} structures are also allowed.
So the most general type of parameter list is quite a complex structure.
As represented in memory it involves pointers---for example an index
structure contains pointers
to port vectors, and a vector of indices is actually passed as
a vector of pointers to index structures.  However, the structure is
strictly tree-like---partially a consequence of the occam rules against
aliasing through procedure parameter passing.
This leads to useful simplifications of the protocol
used to send parameters from a \verb$Parent$-like process, through
the \verb$Extend$ nodes, to \verb$Worker$-like processes.  Although the
representation in memory of a parameter list structure contains pointers,
the ``external data representation'' embodied in this protocol doesn't
need any explicit representation of these  pointers.  This is because a tree
can be converted to a stream which can be trivially ``parsed'' back
into a tree at its destination.


%\end{document}

