1 A Practical Organisation

The implemented version of the scheme described in section ?? 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 ?? are bundled into a single data structure which will be referred to as an “index” structure. So 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 ??) 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 to 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 ??, 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 “meta-occam”). Suppose one wants to execute the procedure ^{1}

    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:

    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 ??. 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. Specifying these has been deliberately overlooked here, anyway.

1Note: 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 kind 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.

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 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 to the 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). Next, 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 ??, 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 ??a). CONF.index.declare first creates the process tree(s) illustrated in figure ??b. (There are 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 ??c.

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 ??d. 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.