Figure 1:

1 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, the 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.

Figure 1 illustrates the 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 occam parlance) a new channel pair. Both ends of the channels are initially held by the process performing the NEW operation (as it is denoted in the figure). Next, the parent process forks into two processes, passing one end of each channel to each child. In occam terms a PAR has been executed. This gives immediately the first “all-to-all” network consisting of just two processes. (Incidentally, for brevity, protocols on occam port and channel specifiers will be omitted in code fragments)

The next stage of the algorithm can’t be expressed in conventional 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 contigent of connecting channels up to 4. Four (ie, 2 × 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. (This is if the “arity” of the existing processes, ie the number of children it gives rise to, is constant 2. If instead an existing channel connected a process of arity m to one with arity n, mn copies of that channel would be needed before forking.)

1.1 Programming Recursive Spawning

The first two stages of figure 1 can be represented in conventional occam just by

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

where processes A and B will be expanded below. A would take the output end of a.to.b and the input end of b.to.a, and conversely for 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 occam described in section ??.

    PROC CHAN.create.child  (CHAN parent, PORT child)
      PORT remote :
      SEQ
        remote, port NEW (CHAN)
        POINTER.OUT (parent, remote)
    :
    PROC CHAN.receive.child (CHAN parent, PORT child)
      POINTER.IN (parent, child)
    :

CHAN.create.child is called by the process that holds the outputting end of the parent channel, 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, but this is a nicety.

Stages 3 and 4 of figure 1 can now be expressed along the lines of figure 2. For obvious reasons, full details of B, which are very similar to A, aren’t spelt out.

This fragment is presented for illustration because it follows in the style of the pure occam representation above of stages 1 and 2, and faithfully represents the pictorial outline of figure 1. 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

1. All channels are taken to be dynamic. So far channels which could be declared in the normal static manner (a.to.b, b.to.a, a.to.c,…) were so declared. This change adds uniformity.

2. 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.

3. Throughout the algorithm we work with ports, rather than dereferencing them in abbreviations to get channels at the earliest opportunity. (The abbreviations would get particularly clumsy in the light of the next modification).

4. 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 id,

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

Figure 2: and its input ports and output ports are respectively ins and outs. Then ins [d] connects this process with process d, and 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.

Notice that we now have an extra port pair, ins [id] and 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 even more uniform. The results of these rationalisations are surprisingly simple code. In one fell swoop, it’s now straightforward to generalise the recursive step to the case where the “arity” of each existing process is arbitrary—it doesn’t even have to be the same for every process.

In figure 3, arity and 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 child.id indexes the children of a given node. They should satisfy

⋃_{i=0}^{N−1} ⋃_{j=0}^{arity(N,N′,i)−1}{child.id(N, N′, i, j)} = ⟨N′⟩

∑_{i=0}^{N−1} arity(N, N′, i) = N′

where ⟨N′⟩ is the set 0 … N′ − 1. For example, if N′ = 2N a possible choice is

arity(N, N′, i) = 2
child.id(N, N′, i, j) = 2j + i.

The procedure ports.extend creates a number of vectors of new.size new input and output ports from vectors of N old ports. The number of new vectors (the first dimension of new.ins and new.outs) is the number of children of this node (called 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 ports.extend is to perform all copying of channels connecting processes whose ids differ by 0 first (these are the former static channels alluded to above), then all channels connecting processes

whose ids differ by 1, and so on. The CHAN.create.child and CHAN.receive.child

operations on each process are executed in parallel, to avoid cyclic dependencies leading to deadlock.

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

A couple of liberties are taken with strict occam in net.extend, as written. The sizes of the new.ins and new.outs arrays aren’t constant, so actually they would have to be “declared” through pointers and NEW statements. The range of the PAR replicator also isn’t constant. However, assuming a sensibly uniform choice of definition for arity, loc.arity will be bounded by the constant STRETCH.FACTOR; so the PAR replicator can actually range over this constant, any unwanted processes being sacrificial. Finally, existing occam implementations don’t allow recursion. However, in reality the recursive calls to net.extend in the body of the PAR will be remote procedure calls, and VCR remote

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.create.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, new.outs, 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)
:

Figure 3: procedure calls (being separately compiled modules whose workspace is not allocated on the parent stack) are allowed to be recursive.

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

1.2 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

O(1 + 2 + 4 + … + N/2) = O(N),

saturating the above bound, up to some unspecified constant factor.