%\documentstyle{csart}

%\begin{document}

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

\section{\label{spawn}Spawning General Networks Efficiently}

     This section outlines a simple recursive scheme for spawning
process networks connected by virtual channels.  The discussion is
in terms of "all-to-all" connected networks---every process has a
channel pair connecting it with every other process.  Fairly clearly,
though, similar schemes are applicable to other networks, especially
those with regular recursive decompositions (hypercubes, rings and
grids, etc).  The emphasis is on what primitive operations are needed to
implement the procedure, and how efficient it is.

     First notice that the naive method of spawning such a network,
using only the pure RPC operations described in section \ref{vcr},
is too inefficient to consider seriously.  This approach would involve
declaring (allocating) all connecting channels ($O(N^2)$ of them),
on the parent process, then spawning $N$ processes and moving the
ends of all channels to the appropriate children.  The overall
time would be proportional to $N^2$.  The scheme described here
is much more efficient.

\begin{figure}
\centerline{\psfig{figure=life.ps,height=2.5in}}
%\vspace{45\baselineskip}
\caption{\label{recspawn}Recursive spawning of an 8-site array}
\end{figure}

     Figure \ref{recspawn} illustrates the recursive algorithm pictorially. 
In the figure a single process ``gives birth to'' a network of
8 processes with full channel connectivity.  The arcs in the diagram
are labelled with the basic operations involved in the corresponding
stage of the algorithm.  The first stage is to declare (in {\em occam}
parlance) a new channel pair (a dashed line is a channel pair).
Both ends of the channels are initially
held by the process performing the \verb$NEW$ operation (or channel
declaration).  Next, the parent process forks into two processes,
passing one end of each channel to each child.  In {\em occam} terms a
\verb$PAR$ has been executed.
This gives immediately the first
``all-to-all'' network consisting of just two processes.
(Incidentally, for brevity, protocols on {\em occam} port and channel
specifiers will be omitted in code fragments.)

     The next stage of the algorithm can't be expressed in conventional
{\em occam}.
As well as declaring a new channel pair in each process (as in the
previous paragraph) three new channels are needed between the two processes to
bring the contingent of connecting channels up to 4.  Four (ie, $2 \times 2$)
channels are needed to establish full connectivity when the two existing
processes each fork into two new ones, as illustrated in the next stage
of the diagram.  Implementing this part of the algorithm needs a
``channel duplication'' operation, whereby two processes holding the
ends of an existing channel can cooperate to bring a new independent
channel connecting them into existence.

     Once such an operation is introduced, nothing else novel is needed to
carry on extending the network indefinitely.  At each stage every process
declares one new channel, and uses channel duplication to create three
copies of each previously existing channel.

\subsection{\label{program}Programming Recursive Spawning}

     The first two stages of figure \ref{recspawn} can be represented
in conventional {\em occam} just by
\begin{linear}
\begin{verbatim}

    CHAN a.to.b, b.to.a :
    PAR
      A
      B

\end{verbatim}
\end{linear}
where processes {\em A} and {\em B} will be expanded below.  {\em A}
would take the output end of {\em a.to.b} and the input end of {\em b.to.a},
and conversely for {\em B}.

     For the next stage we need operations for creating a copy of an
existing channel.  These are easy
to express in the extended version of {\em occam} described in
section \ref{dynamic}.
\begin{linear}
\begin{verbatim}

    PROC CHAN.create.child  (CHAN parent, PORT child)

      PORT remote :
      SEQ
        remote, child NEW (CHAN)
        POINTER.OUT (parent, remote)
    :

    PROC CHAN.receive.child (CHAN parent, PORT child)

      POINTER.IN (parent, child)
    :

\end{verbatim}
\end{linear}
\verb$CHAN.create.child$ is called by the process that holds the
outputting end of the parent channel, \verb$CHAN.receive.child$ by
the process with the inputting end.  One ought also to define operations
for destroying a duplicate channel after it is no longer needed.
For brevity, these are omitted here.

     Stages 3 and 4 of figure \ref{recspawn} can now be expressed
along the lines of figure \ref{2to4}.

\begin{figure}
\begin{verbatim}

    CHAN a.to.b, b.to.a :
    PAR
      PORT p.a.to.d, p.d.to.a, p.c.to.b, p.c.to.b, p.c.to.d, p.d.to.c :
      SEQ
        CHAN.create.child  (a.to.b, p.a.to.d)
        CHAN.create.child  (a.to.b, p.c.to.b)
        CHAN.create.child  (a.to.b, p.c.to.d)
        CHAN.receive.child (b.to.a, p.d.to.a)
        CHAN.receive.child (b.to.a, p.b.to.c)
        CHAN.receive.child (b.to.a, p.d.to.c)

        CHAN a.to.d IS FOLLOW p.a.to.d :
        CHAN c.to.b IS FOLLOW p.c.to.b :
        CHAN c.to.d IS FOLLOW p.c.to.d :
        CHAN d.to.a IS FOLLOW p.d.to.a :
        CHAN b.to.c IS FOLLOW p.b.to.c :
        CHAN d.to.c IS FOLLOW p.d.to.c :

        CHAN a.to.c, c.to.a :
        PAR
          A'
          C

      PORT p.a.to.d, p.d.to.a, p.c.to.b, p.c.to.b, p.c.to.d, p.d.to.c :
      SEQ
        CHAN.receive.child (a.to.b, p.a.to.d)
        CHAN.receive.child (a.to.b, p.c.to.b)
        CHAN.receive.child (a.to.b, p.c.to.d)
        CHAN.create.child  (b.to.a, p.d.to.a)
        CHAN.create.child  (b.to.a, p.b.to.c)
        CHAN.create.child  (b.to.a, p.d.to.c)

        CHAN a.to.d IS FOLLOW p.a.to.d :
        CHAN c.to.b IS FOLLOW p.c.to.b :
        CHAN c.to.d IS FOLLOW p.c.to.d :
        CHAN d.to.a IS FOLLOW p.d.to.a :
        CHAN b.to.c IS FOLLOW p.b.to.c :
        CHAN d.to.c IS FOLLOW p.d.to.c :

        CHAN b.to.d, d.to.b :
        PAR
          B'
          D

\end{verbatim}
\caption{\label{2to4}Stages 1-4 of a spawning schedule}
\end{figure}

     This fragment is presented for illustration because it follows in the
style of the
pure occam representation of stages 1 and 2 above, and because it
faithfully represents
the pictorial outline of figure \ref{recspawn}.  It would be possible, but
evidently not very sensible, to carry on the algorithm with this
particular organisation of the code.

     The changes we now make are
\begin{enumerate}
\item
{\em All} channels are taken to be dynamic.  So far channels which
{\em could} be declared in the normal static manner ({\em a.to.b}, {\em b.to.a},
{\em a.to.c},\dots ) were so declared.  Changing this adds uniformity.
\item
We abandon the optimisation of only creating 3 duplicate channels of
each existing channel.  Instead 4 are created, and the original isn't
used any more.  Again, this makes things more uniform.
\item
Throughout the algorithm we work with \verb$PORT$s, rather than dereferencing
them in abbreviations to get \verb$CHAN$s at the earliest opportunity.
(The abbreviations would get particularly clumsy in the light of the next
modification).
\item
We work with arrays of ports rather than individual ones.  This is
obviously necessary to go to a general number of processes.
Each process has an array of input ports and an array of output ports.
Suppose the index of a particular process is {\em id}, and its input
ports and output ports are respectively {\em ins} and {\em outs}.
Then \verb$ins [d]$ connects the local process with process $d$,
and \verb$outs [s]$ connects it with process $s$.  Here
$s$ and $d$ range from $0$ to $N-1$,
where $N$ is the total number of processes.
\end{enumerate}
Notice that we now have an extra port pair, \verb$ins [id]$ and
\verb$outs [id]$,
which connect a process to itself.  These are quite useful.
The formerly static channels alluded to in item 1 above will be brought
into existence by copying this channel, making things yet more
uniform.

     After these rationalisations the code becomes surprisingly simple.
In one fell swoop, it's now straightforward to generalise the recursive
step to the case where the ``arity'' of each existing process
(the number of children it gives rise to)
is arbitrary---it doesn't even have to be the same for every process.

\begin{figure}
\begin{verbatim}

    PROC ports.extend ([] [] PORT new.ins, new.outs,
                          [] PORT ins, outs,
                          VAL INT N, id, new.size)

      VAL loc.arity IS arity (N, new.size, id) :
      PAR
        SEQ shft = 0 FOR N
          VAL dst       IS (id + shft) MOD N :
          VAL dst.arity IS arity (N, new.size, dst) :
          SEQ i = 0 FOR loc.arity 
            SEQ j = 0 FOR dst.arity
              VAL dst.new IS child.id (N, new.size, dst, j) :
              CHAN.create.child (FOLLOW (outs [dst]), new.outs [i] [dst.new])

        SEQ shft = 0 FOR N
          VAL src       IS (id + shft) MOD N :
          VAL src.arity IS arity (N, new.size, src) :
          SEQ j = 0 FOR src.arity
            SEQ i = 0 FOR loc.arity 
              VAL src.new IS child.id (N, new.size, src, j) :
              CHAN.receive.child (FOLLOW (ins  [src]), new.ins  [i] [src.new])
    :

    PROC net.extend ([] PORT ins, outs, VAL INT N, id, target.size)

      IF
        N = target.size 
          worker (ins, outs, N, id)
        TRUE
          VAL new.size  IS MIN (target.size, STRETCH.FACTOR * N) :
          VAL loc.arity IS arity (N, new.size, id) :
          [loc.arity] [new.size] PORT new.ins, new.outs :
          SEQ
            ports.extend (new.ins, new.outs, ins, outs, N, id, new.size)
            PAR i = 0 FOR loc.arity
              VAL id.new IS child.id (N, new.size, id, i) :
              net.extend (new.ins [i], new.outs [i], new.size, id.new, target.size)
    :

    PROC spawn.net (VAL INT target.size)

      [1] PORT ins, outs :
      SEQ
        ins [0], outs [0] NEW (CHAN)
        net.extend (ins, outs, 1, 0, target.size)
    :

\end{verbatim}
\caption{\label{spawnocc}General Implementation}
\end{figure}

     In figure \ref{spawnocc}, \verb$arity$ and \verb$child.id$ are auxilliary
functions which define how the nodes of the new network are
parented by the nodes of the old network at each stage.
They depend on the number of old
nodes ($N$), the number of new nodes ($N'$), and the id of the old
(parent) node.  The last argument of \verb$child.id$ indexes the children
of a given node.  They should satisfy
\begin{displaymath}
  \sum_{i=0}^{N-1} arity (N, N', i) = N'
\end{displaymath}
\begin{displaymath}
  \bigcup_{i=0}^{N-1} \bigcup_{j=0}^{arity(N, N', i)-1} \{child.id(N, N', i, j)\}
                               = \langle N' \rangle
\end{displaymath}
where $\langle N' \rangle$ is the set $0\dots N'-1$.  These just say that
the children of the old sites partition the new sites.  For example,
if $N' = 2N$ a possible choice is
\begin{displaymath}
  arity (N, N', i) = 2
\end{displaymath}
\begin{displaymath}
  child.id (N, N', i, j) = 2j + i.
\end{displaymath}

     The procedure \verb$ports.extend$ creates a number of vectors
of {\em new.size} ($N'$) new input and output ports from vectors of $N$ old
ports.  The number of new vectors (the first dimension of {\em new.ins}
and {\em new.outs}) is the number of children of this node (called
{\em loc.arity} in the body of the procedure).

     Channel copying is a synchronising operation on the parent channel,
so some thought has to be given to the scheduling of these operations.
The scheduling chosen in \verb$ports.extend$ is to perform all copying
of channels connecting processes whose {\em id}s differ by 0 first
(these are the former static channels alluded to above), then
all channels connecting processes whose {\em id}s differ by 1,
and so on.  The \verb$CHAN.create.child$ and \verb$CHAN.receive.child$
operations on each process are executed in parallel, to avoid cyclic
dependencies leading to deadlock.

     The procedure \verb$net.extend$ extends an existing all-to-all
network with $N$ nodes to {\em target.size}.  Its other parameters
correspond to those of \verb$ports.extend$.  It operates recursively.  At each
invocation it increases the network size to at most \verb$STRETCH.FACTOR * N$.
Typically \verb$STRETCH.FACTOR$ would be $2$.

     A few liberties are taken with strict occam in \verb$net.extend$,
as written here.  The sizes of the $new.ins$ and $new.outs$ arrays
aren't constant, so actually they would have to be ``declared'' through
pointers and \verb$NEW$ statements.  The range of the \verb$PAR$ replicator
also isn't constant.  However, assuming a sensibly uniform choice of
definition for \verb$arity$, {\em loc.arity} will be bounded
by the constant \verb$STRETCH.FACTOR$;
so the \verb$PAR$ replicator can actually
range over this constant, any unwanted processes being sacrificial.
Finally, existing {\em occam} implementations don't allow recursion.
However, in practise, the recursive calls to \verb$net.extend$ in the
body of the \verb$PAR$ will be remote procedure calls, and VCR
remote procedure calls (being separately compiled modules whose workspace 
is not allocated on
the parent stack) are allowed to be recursive.

     Finally, \verb$spawn.net$ simply invokes \verb$net.extend$ from
an initial state which is formally an all-to-all network of size $1$.

\subsection{Efficiency}

     For dynamically spawning networks with all-to-all channel connectivity
the scheme just described is ``optimal'', assuming our set of primitives. 
The grounds for this claim are
that each process ends up with a number of channels proportional to the
final network size ($N$, say).  Creating $N$ channels, or even just assembling
them in one place (on one processor) inevitably takes time proportional
to at least $N$ with the primitives assumed.
On the other hand, assuming all primitives take some constant time
(ignoring factors like the diameter of an underlying physical processor
network, which may effect timings for message passing)
it's easy to see that the parallel time take to extend a network from
size $n$ to size $2n$ is $O(n)$.  So the parallel time for the full
recursive schedule is 
\begin{displaymath}
  O(1 + 2 + 4 + \ldots + N/2) = O(N),
\end{displaymath}
saturating the above bound, up to some unspecified constant factor.

%\end{document}

