Spawning Process Networks in a Virtual Channel Environment

D.B. Carpenter

Department of Electronics and Computer Science, Southampton University, Southampton, S09 5NH

November 14, 1991

1 Introduction

This article discusses efficient spawning of process networks on a parallel computer. It starts from the premise that communication between remote processes will go through “virtual channels”. A virtual channel is a CSP-style [1] communication channel implemented on some packet routing network ^{1}. It also assumes that a process running anywhere on the machine can start up another process somewhere else on the machine at any time. The parent process should be able to supply a child with some set of channels for its communication purposes.

These services are provided in our case by the Virtual Channel Router (VCR) developed by Debbage, Hill and Nicole [2] under the Esprit PUMA project. VCR is, in part, an emulation of features which will be supported in hardware by the T9000 generation of Inmos transputer components [5] (though it may be that not all the dynamic features of VCR exploited during this work will be particularly strongly supported by the T9000).

The CSP or occam [6] concurrent programming models rely on the medium of synchronous point-to-point logical channels for communication between processes. One advantage of this mechanism is that channels map straightforwardly onto the physical wires of simple hardware (for example, first generation transputers [4]). This particular motivation has become less compelling as MIMD systems have moved away from providing restricted local communication, towards hardware-supported routing of messages between arbitrary processors. Strong arguments for the channel model remain, however. For one, a channel can be efficiently implemented on top of packet routers with a single buffer per channel; the channel discipline ensures that errant user programs can’t infect the packet delivery system with deadlocks. For another, the clearly defined semantics of channel communication simplify production of reliable code. Further aesthetic and formal arguments in favour of the channel are given, for example, in [1].

The discussion will be mainly in terms of the occam language. Obviously similar things can be done in any language provided with a library of functions for the kinds of service outlined above—VCR entry-points, for example, are available for FORTRAN and C programs, as well as occam. In a number of ways occam as currently implemented is less than ideal for describing dynamic algorithms, and a slightly extended form of occam notation will be introduced in section 3 as a vehicle for presentation of algorithms.

The original implementations of occam only provided static placement of top-level user processes on processors. Although occam allows any process to fork into several processes at any time through the PAR construct, early implementations have forced processes spawned in this way to run on the same processor as their parent. The dynamic procedures of the VCR library can be viewed as a run-time system for an enhanced occam in which this constraint is relaxed ^{2}. These VCR facilities allow a process running on one processor to start a process with which the parent may communicate unrestrictedly on another processor. They are reviewed more fully in section 2.

The remaining sections describe an application of these basic capabilites—namely to run-time spawning of fully connected networks of processes on some available set of processors.

The work presented here was originally motivated by the configuration requirements of a distributed-data communication library developed in the applications workpackage of Esprit project 2701 (PUMA) [7]. Some aspects of those requirements show through in details of section 5, although, by and large, I have tried to make the presentation here self-contained.

1Sometimes distinguished from a “hard channel”, implemented across a direct physical link, or a “soft channel” implemented within a single processor’s memory and connecting two processes running on the same processor.

2At the time of writing not all these features have been fully integrated with the compiler.

2 The Virtual Channel Router

The Southampton VCR [2] provides efficient routing of messages between arbitrary user processes on arbitrary processors, overcoming the hardware limitation of first generation transputers and their compilers, which only provided support for communication between processors with direct physical connections. VCR adheres strictly to the occam model of communication, so the channel retains a central role, and all communications are strictly synchronised. An enhanced occam compiler is available which transparently incorporates calls to VCR procedures wherever user code contains occam communication primitives. Also a configurer recognising a subset of occam is available for placing top-level user processes on processors. The only apparent distinction between this configurer and earlier ones is that there are no hardware-related restrictions on the number or connnectivity of configuration-level channels; these channels are now through-routed “virtual channels”.

For purposes of this article, the most interesting aspect of VCR is not the enhanced compiler or configurer, which together still only directly support static placement of user processes on processors, with static connections, but the facilities in the VCR library for dynamic placement.

Existing implementations of occam include an unnatural restriction which only allows code to be placed on particular processor through directives in the top-level configuration code. One of the goals of VCR has been to provide a run-time library for a dialect of the language in which this restriction was lifted [8]. In configuration-level occam the process

    PROCESSOR expression
      process

which behaves identically to ‘process’, but is specified to run on the processor defined by ‘expression’, may appear. The VCR library [3]effectively allows this placed process to appear anywhere in a user process, not just in a static, top-level, PLACED PAR. In both (early) static configurers and dynamic VCR the restriction is enforced that ‘process’ should be a call to a separately-compilable procedure (rather than general in-line code). For many purposes this is a relatively minor “implementation limit”. The important point is that arbitrary parameters, including channel parameters, can be passed to this procedure invocation.

If it weren’t for the insistence that channel parameters can be passed to the procedure invocation, this placement mechanism would be a fairly mundane remote procedure call (RPC). The fact that the calling (parent) process can pass channel parameters to the remote process makes this mechanism much more expressive. As the simplest example, some parent process could execute

    CHAN OF PROT from.slave, to.slave :  PAR
      ... client process
      PROCESSOR remote
server (to.slave, from.slave)

where the (implicitly local) “client process” interacts with the remote invocation of server through the channels to.slave and from.slave. (Not completely dissimilar mechanisms are available in some distributed system programming languages, for example [9]).

This is a small step, logically, from earlier occam implementations. The implementation details of the new regime are significantly more complicated, though. Spawning a process remotely presumes the existence of a fairly elaborate kernel running on the target processor, whereas earlier occam implementations allowed naked user code to run on all processors. Since it can’t be predicted at compile time where the user process will place processes, the kernel needs to be equipped with dynamic memory management capabilities to find workspace for the spawned processes. Moreover, some technology is needed to set up channels such as from.slave and to.slave above.

The physical incarnation of a virtual channel end is a data structure (called the Virtual channel Control Block, or VCB, in VCR) which contains information concerning the whereabouts of the local and remote processes connected by the channel, and buffer space. In the fragment above both ends of a channel have data structures allocated locally (because in general it isn’t known at allocation time which would be the “proper” processor on which to allocate the remote end; in fact the definition of occam allows several RPCs on different processors to be passed the same channel end at different times). Then, when the remote procedure call (RPC) occurs, one end of the channel must be “moved” to the remote processor for the duration of the RPC. This involves an exchange of control messages between the local and remote kernels causing space for the channel to be allocated remotely, and possible transfer of the contents of the old channel VCB from the local processor.

The pure remote procedure call mechanism illustrated above thus requires dynamic operations including channel-moving for its implementation. These aren’t explicit in the code above, but the technology has to be available in the VCR run-time system. The motivation of the current work was the desire to spawn much more general networks than such simplified client-servers efficiently at run time. For this it seems that the underlying technology of VCR suffices, but that the bits have to be put together in more general paradigms than pure occam remote procedure calls.

3 An Extended occam-like Notation

Pure occam isn’t a suitable notation for expressing very dynamic algorithms. Some sort of pointers seem necessary, at least. To simplify presentation of algorithms in this article we use an “algorithmic language” which is essentially occam with a couple of extensions for handling dynamic objects. (No implementation exists for this language. On the other hand it isn’t much more than a sugaring of capabilities inherent in the VCR run-time library). For our purposes a restricted form of pointer which doesn’t lead to undesirable aliasing is sufficient. (One reason why aliasing is bad in occam is that concurrently executing processes aren’t supposed to share access to variables or channel ends. If there are several different names for the same object, such a regime becomes difficult to enforce.) Non-aliasing pointers for occam have been discussed, for example, in [10]. Usage here differs in detail.

To prevent simply copying the reference in one pointer variable to another (leading to an alias) pointers can’t appear in assignment statements (except in dereferenced form). Instead the primitive procedure

    PROC POINTER.COPY (POINTER T a, b)

copies the value of the pointer b to a, and makes the pointer b null. A precondition is that a should be null before invoking the procedure. (The symbol T is used here as a type variable; POINTER.COPY is overloaded for application to pointers to arbitrary compatible types).

So long as pointers are copied by this operation alone, one never ends up with two pointers referencing the same object. Pointer communication can be defined along similar lines

    PROC POINTER.OUT (CHAN OF POINTER T chan, POINTER T b)
    PROC POINTER.IN  (CHAN OF POINTER T chan, POINTER T a)

If both ends of chan live on the same processor the implementation of these (synchronising) operations is by straightforward pointer copying. If they live on different processors, POINTER.IN allocates space locally for the incoming data, returning the address in a, the data is transfered, and POINTER.OUT deallocates the memory pointed to by b (and makes the pointer null). This implementation is applicable if T is a simple data type. If T is actually a record that contains other pointers, complications ensue which won’t be discussed here. If it’s a channel, other complications ensue which will be mentioned below. In an implementation one should presumably strive to maintain the law

    CHAN c :
    PAR
      POINTER.OUT (c, b)      =      POINTER.COPY (a, b)
      POINTER.IN  (c, a)

For pointers to simple data the story is completed by adding a Pascal-like mechanism to the language for allocating and freeing memory (and a notation for dereferencing a pointer). So, for example,

    POINTER [] INT a :
    SEQ
      a NEW ([n] INT)
      ...
      (FOLLOW a) [i] := ...
      ...
      FREE a

allocates a as a pointer to an array of n integers. (Assume that a pointer is set to null when it is declared. Then one can also demand, and in principle check, that the value of any pointer should be null when its scope terminates, enforcing that the user always explicitly deallocates allocated objects. This is only possible because pointers are “nonaliasing”. It represents an interesting antithesis to automatic garbage collection! The language probably ought to have a NULL operator applicable to a pointer to test whether it is null, but no explicit null value needs to be expressible).

Of course these non-aliasing pointers are fairly restrictive. Assuming pointers are allowed to appear in records, one can still only build up simple tree and list structures, and even with those structures there are awkward complications about traversal with the primitives given (especially if the language doesn’t support recursive procedures). Simple stacks work quite well, but any recursive structure more complicated than that gets painful. Nevertheless, non-recursive, bounded depth, trees still represent a significantly richer spectrum of data structures than those available in implemented, pointerless, versions of occam.

Pointers to data were introduced first, but pointers to channel ends are more important in this article. Any channel has two ends (inputting and outputting). A pointer to a channel end will be called a PORT. A port deferenced by the FOLLOW operator can be used wherever a CHAN expression can appear in normal occam (for example, on the left hand side of an input or output operation). Also a port can be passed as a parameter to the generic operations on pointers—POINTER.COPY, POINTER.IN and POINTER.OUT. A dynamic channel is allocated and freed by

    PORT OF ANY c, d :
    SEQ
      c, d NEW (CHAN OF ANY)
      ...
      FREE c, d

The first of the pair of ports appearing in the NEW and FREE statements will be a pointer to the input end of the channel, and the second a pointer to the output end (say). Through the pointer IO operations a port can be passed from one process to another. We’ve specified that a connected pair of ports should be deallocated together (because this seems more symmetric; it may also simplify implementation slightly). This means there has to be some mechanism for getting connected ports back together again for disposal.

    PROC SELF.OUT  (PORT OF T port)

is a primitive procedure which outputs a channel end on itself, making port null. The channel end emerges out of its own input port, (through a normal POINTER.IN operation at that end) and the two can then be deallocated (together, but not necessarily in the same process they started in).

The run-time system needed to implement NEW, FREE, POINTER.IN, POINTER.OUT and SELF.OUT is easily built on top of the VCR run-time library. The first four calls formally apply to, but have very different implementations for, both data and channels (for data, only memory management and simple IO is needed; for channels the full paraphernalia of channel-moving is needed). Facilities for implementing both are available in VCR.

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

Figure 1 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 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 NEW operation (or channel declaration). 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 Figure 1: Recursive spawning of an 8-site array

6 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 contingent 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.

4.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 3.

    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)
    :

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. For brevity, these are omitted here.

Stages 3 and 4 of figure 1 can now be expressed along the lines of figure 2.

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 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. Changing this

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: Stages 1-4 of a spawning schedule

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 CHANs 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, and its input ports and output ports are respectively ins and outs. Then ins [d] connects the local 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 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.

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} arity(N, N′, i) = N′

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

where ⟨N′⟩ is the set 0 … 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

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 (N′) 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

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)
:

Figure 3: General Implementation 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 few liberties are taken with strict occam in 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 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 practise, the recursive calls to net.extend in the body of the 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, spawn.net simply invokes net.extend from an initial state which is formally an all-to-all network of size 1.

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

5 A Practical Organisation

The implemented version of the scheme described in section 4 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 2d 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 worker in figure 3 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 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 declaring the distributed index. The operation

    spawn.net (N)

(see figure 3) is regarded as an implementation of something like (in yet another, higher level, meta-language)

    [N] INDEX x :
    worker (x)

This notation won’t be elaborated very far here. The idea is that the above fragment invokes N parallel copies of 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

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

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 spawn.net to be invoked recursively. Moreover, there has to be a mechanism for the existing index x to be passed through the spawn.net analogue to the user processes worker (unlike the simplified implementation of figure 3, which only passes the components of the 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 ^{3}

    PROC worker (INT32 x, y)
      ...
    :

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 parent, say. For parent to initiate the desired two-dimensional array it makes the following calls:

3Note: The existing implementation is written in 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 INT32 variable to hold a pointer. Although these kinds of things are very clumsy in standard occam, the language has some advantages over, say, C for the very communication-rich procedures described in this section.

    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)
    :

The first two steps load the two parameters for the worker call into an array params (the detailed representation of this array needn’t be known—a series of library procedures similar to PARAM.index are provided, one to load each possible type of parameter). Loading the first parameter, x, into the 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 CONF.index.declare, together with the name of the file containing the code for worker, and the size M of the new array dimension. The other two parameters of CONF.index.declare, proc.base and proc.stride, define processor placement of the processes dynamically created by this utility.

CONF.index.declare is a generalisation of the spawn.net procedure of section 4. The initial array of parent processes will itself presumably have been initiated by a previous call to the same routine. In fact

    [1] [PARAM.size] INT params :
    SEQ
      PARAM.index (params [0], INT32 NULL.PTR)
      CONF.index.declare (N, proc.base, proc.stride,
                          "parent.cah", params)

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

The need to pass arbitrary parameters to the “scope” procedure CONF.index.declare suggests a more elaborate organisation for this routine than that of 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

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

ought to be legal. This invokes N identical instances of a parameterless procedure 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

Figure 4: Spawning a 2-dimensional array from a 1-dimensional one

outside world, anyway). It may be pointless, but it still ought to 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 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 spawn.net restricted use of dynamic channels to the channel copying operations described in section 4, this new organisation makes general use of the assumed capability to send channels (or ports) on channels.

To illustrate the procedure, consider parent in the earlier code fragment. This initially executes in a one dimensional array of processes connected by x (figure 4a). CONF.index.declare first creates the process tree(s) illustrated in figure 4b. (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. 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 Worker nodes. The method is to copy all channels in Parents x structure, and send these channels to the first layer of Extend nodes. These nodes make two copies of the incoming channels, and send one to each child Extend node. They repeat the procedure, sending the new channels to the worker Worker nodes, where the incoming channels are assembled into structures for passing to the instance of the user procedure worker. This leads to figure 4c.

Now the second parameter, a y index structure, has to be delivered to the Worker nodes. The procedure for this is very similar to that of spawn.net. Parents 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 Extend node of the tree. The Extend nodes read incoming channel vectors, perform the ports.extend operation on these vectors, and send the new, extended port vectors to their children. This leads to the final figure 4d. Once the index structures have been delivered to the Worker nodes many channels created in the intermediate nodes can be disposed of.

Some remarks about this organisation:

1. Apart from the fact that they have several output channels the 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.

2. Because of this there is an implicit pipelining of the operation of sending out parameters. In the above example the first level of Extend nodes may start processing the y parameter before the second level has finished processing the x parameter.

What kind of parameters can be passed through 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 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 Parent-like process, through the Extend nodes, to 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.

6 Discussion

The algorithms for spawning networks described here depend on certain extensions to the standard occam model. The most practical algorithms seem to demand passing pointers down channels, and, most especially, passing pointers to channel ends down channels. The basic scheme outlined in section 4 got by with a restricted operation of channel copying. However, it’s difficult to see how even this operation could be very practically expressed in a language which didn’t provide pointers to channels.

The discipline of non-aliasing pointers outlined in section 3 (and borrowing from [10]) might be worth considering as a pragmatic language compromise between the completely undisciplined use of pointers in languages like C, and total abolition of pointers in occam. This approach isn’t without problems… for example, sending a pointer to a tree structure down a channel to a different processor involves a notional compiler generating code to traverse the tree. Also, there are clear formal problems with allowing pointers in occam. The semantics of standard occam can be understood in terms of CSP, but allowing pointers would probably require some sort of extended CSP model in which processes had mutable alphabets. These sorts of problems are discussed briefly, in the context of CCS rather than CSP, in [11] (and, doubtless, elsewhere).

Such problems aside, the notation of section 3 was invaluable in implementing the algorithms described in this article. (The procedures were implemented in the extended notation, then the code was manually transcribed to a very muddy, low-level, style of standard occam).

Finally, the manner in which VCR was exploited in this paper is a clear abuse of the original intentions of the authors of that system. Apologies to them.

References

[1] C.A.R. Hoare, Communicating Sequential Processes, Prentice/Hall International (1985).

[2] M. Debbage, M.B. Hill and D.A. Nicole, Towards a Distributed Implementation of Occam, Proceedings of the 13th Occam Users Group, IOS Press (1990).

[3] M. Debbage, M.B. Hill and D.A. Nicole, VCR 2.0 RPC Support and Run-Time Library, University of Southampton, Concurrent Computation Group (1991).

[4] Inmos Ltd., Transputer Reference Manual, Prentice-Hall (1988).

[5] Inmos Ltd., The T9000 Transputer Products Overview Manual.

[6] Inmos Ltd., occam Programming Manual, Prentice-Hall International (1984).

[7] D.B. Carpenter, Array Communication Library: Introductory Guide, University of Southampton, Concurrent Computation Group (1991).

[8] D. May, Implementing Full Occam Esprit Project 2701 (PUMA) Working Paper 2, Inmos Ltd (1989).

[9] R.E. Strom et al Hermes: A Language for Distributed Computing Prentice Hall, Inc (1991).

[10] P.H. Welch, Securely Managed Pointers, WoTUG Newsletter 15 (1991) pp35.

[11] R. Milner, Communication and Concurrency, Prentice Hall International (1989) pp249.