Array Communication Library: Introduction

D.B. Carpenter

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

January 17, 1992

Contents

1 Overview 1 1.1 Distributed Indicies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Distributed Channels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Usage Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2 The Application Library. I: Index Communications 6 2.1 Broadcasts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Prefixes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.5 Multi-index operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3 The Application Library. II: Input and Output 10 3.1 Communicating globals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2 Communicating whole distributions . . . . . . . . . . . . . . . . . . . . . . 11 3.3 Elements of distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.4 Distributions of arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

The Array Communication Library is a library of procedures to facilitate programming “array-parallel” problems on MIMD machines. It is currently implemented on top of the Southampton Virtual Channel Router, and provided as a library of occam procedures.

A general theme of the library is to treat communications as operations on distributed data—although low-level message-passing entry-points are available, the point-to-point communication model is not really encouraged for communication within an array process.

The library is underpinned by a model of array processes and distributed data based on a couple of simple extensions to the occam communication model. This extended model has been described in [1]. It is sketched in section 1. Sections 2 and 3 describe the most important entry points in the library, using the notation introduced in section 1.

At the moment the library consists of communication procedures which operate in some existing process configuration with a specific channel connectivity. It is the responsibility of the user to set up the process and channel network correctly. The intention in future releases is to provide configuration primitives which will spawn the proper networks dynamically.

Listings of the concrete occam interfaces of all procedures, as well as details of configuration and implementation, can be found in [2].

1 Overview

1.1 Distributed Indicies

The library is built on an occam-like communication model, generalised to give communications within process arrays a more central role than they have in conventional, exclusively channel-based, occam

In this model a structure called a “distributed index” (or just an “index”) takes over the role of the occam channel for communication within arrays. Communication between a particular process array and external processes still takes place over occam-like channel structures.

In this section a couple of language conventions will be introduced for describing indices, array processes, and distributed data. This simplifies logical specification of the procedures in the communication library. In our language an index is brought into existence by a declaration:

    [n] INDEX x :
    Scope

where n is an integer expression and Scope is a process. In the implementation we are assuming the effect of an index declaration is to execute n copies the scope process in parallel. These n processes (collectively the “array process”, or process array) can only communicate amongst themselves through the index x. So declaration of an index of size n is similar to a replicated PAR with count n in occam, preceded by declaration of a whole collection of channels for communication amongst the processes. And, of course, in a transcription from our notation to standard occam, this is essentially how index declaration would go. The channels connecting the processes can be embodied in a single (distributed) data structure. This data structure is the concrete representation of the index.

Declaring a single index produces a one-dimensional process array. If a second index is declared inside the scope of the first, its scope is a two-dimensional process array, and so on.

The second modification to occam is the requirement that all data structures (except the index structure, which has special status) have a property called “rank”. Rank is analogous to arithmetic type, but defines how a data structure is distributed over the process array. A rank is a subset of the scoped indices. A “scalar” object has the trivial rank {}. Scalars take values global across the process array. In a typical implementation a copy of the object is held redundantly across all processes, and (in principle) rules are enforced to ensure that all updates of this object maintain its global nature. More generally, if several indices are in scope (x and y, say) an object with rank {x} would take distinct values for each value of the x-coordinate, but be global with respect the the y-direction, whereas an object with rank {x, y} would take distinct values in every process.

We call any ranked object, especially one with non-trivial rank, a “distribution”. A distribution can be thought of as a kind of parallel array, but for a distribution there is no analogue of subscripting. A process just accesses a distribution by name—implicitly the locally held element. A scalar is a distribution, but one with trivial rank—analogously in ordinary occam one could say that a simple variable was “zero-dimensional array”.

Specifiers for distributions will be quite important in describing the procedure interfaces for the communication library, so some examples of declarations of distributions are given here:

     {} INT i :
     INT j :
     {x} [m] INT b :
     {x, y} INT A :

i and j are scalars (the two styles of declaration are equivalent). b is a one-dimensional distribution (over {x}) of ordinary sequential arrays. A is a two-dimensional distribution of integers. In general the specifier consists of a conventional type, preceded by an index set.

A component process in a process array will often need to know “where it is” in the array. One way of achieving this is to introduce a special construct, called the WHERE loop in [1]. This document is more concerned with a particular library implementation of the model—and a more appropriate mechanism here is to introduce the access function INDEX.coord for the INDEX data type. For example

    [n] INDEX x :
    SEQ
      A
      IF
        INDEX.coord (x) = 3
          P
        TRUE
          SKIP
      B

executes A and B in every process in the array, but P is only executed for the point with coordinate 3 (coordinates go from 0 to n − 1 in this example).

So far we have just said vaguely that the index structure contains some channels for communication amongst processes, without defining what the primitive communication operations are. Actually we aren’t going to say here what these primitive operations are. The philosophy will be that the “user” is presented with a set of “applicationlevel” procedures for doing quite high-level operations (such as data permutation and broadcasts). These operations take some index structures and some data distributions as parameters. But in principle the communication primitives are hidden from the user.

A concrete example of communication, using the application library:

    [n] INDEX x :
    {x} INT a, b :
    SEQ
      ...
      PERM.SHIFT (x, b, a, 2)
      ...

PERM.SHIFT is a procedure which takes as parameters an index, a pair of distributions over that index, and a shift. The output values of b are the input values of a, shifted cyclically up by two places “in the x-direction”.

1.2 Distributed Channels

An array process communicates with external processes through logical channels. The implementation of these channels is different from ordinary occam channels, so channel (ends) accessed from within an array process will usually be distriguished as “distributed channels”. Often one “end” of a channel will be an ordinary occam channel (accessed by a non-array process) while the other end is a distributed channel—this is how ordinary processes and array processes communicate.

For example:

    CHAN c :
    PAR
      A
      [n] INDEX x :
      B

A is an ordinary process, which can communicate with the array process, scope B, across the channel c. From A’s point of view c is an ordinary channel; from B’s point of view it is a distributed channel. For simplicity of presentation we will normally assume that distributed channels are scalar, but there is a natural generalisation to channels with non-trivial rank. Figure 1 illustrates various logical networks that can be achieved by juxtaposing declarations of indices and channels. The net a is produced by the previous example. Nets b-e are given respectively by the programs:

    CHAN c :                             [n] INDEX x :
    PAR                                  {x} CHAN c :
      A                                  PAR
      [n] INDEX x, y :                     A
      B                                    B

Figure 1: Example logical networks 4

    [n] INDEX x :                        [n] INDEX x :
    {x} CHAN c :                         CHAN c :
    PAR                                  PAR
      [n] INDEX y :                        [n] INDEX y :
      A                                    A
      B                                    B

In the illustrations full vertical connections represent x-connections, horizontal ones yconnections, and dashed arcs c-connections. Where a c channel is drawn as ending in the middle of an array process, that channel end is a distributed channel, global with respect to the array.

Cases c and d use distributions of channels. In principle using multiple channels like this can overcome bottlenecks caused by communicating between array processes over single channels, as in e, at least in the case where the processes share some indices.

An example using a distributed channel (on network b):

    CHAN c :
    PAR
      SEQ i = 0 FOR n
        c ! t; expr (i)
      [n] INDEX x, y :
      {y} INT data :
      SEQ
        ...
        INPUT.1D (c, y, data, t)
        ...

INPUT.1D is a library routine for inputting the whole of a one-dimensional distribution (as a sequential tagged data stream, tag t) from a distributed channel. INPUT.1D puts the ith item it reads from the channel in the element of data held by the processes with y-coordinate i. It maintains the global nature of data with respect to the orthogonal index x, implicitly broadcasting all input values across this direction.

Usage of the distributed channel is logically very similar to that of ordinary occam channels, but again (as with indices) no particular primitives are specified here for performing IO operations on these channels; they are hidden in the implementation of the library.

1.3 Usage Rules

Some discipline has to be imposed on assignments and calls to communication routines to ensure that

• the values of global variables stay global

• mismatched calls to input/output routines don’t cause deadlocks.

• mismatched calls to index communication routines don’t cause deadlocks.

Obviously the user of the application libraries can choose to follow or disregard the following rules at his or her discretion; they are only intended as general guidelines within which reasonable guarantees of correct behaviour can be given.

The rules can be expressed neatly in terms of WHERE loops (by prohibiting assignment to global variables inside the loop; by prohibiting communication on global channels inside the loop; and by descoping indices inside the loop). However we aren’t going to describe these loops here, so more informal guidelines have to be given.

First, define the rank of an expression as the union of the ranks of all its component terms. Then

RULE 1: Stylise any control structure as

     CONTROL expression
       process-list

where expression contains all parameters of the control structure (the condition of a WHILE loop, the guards of an IF, the range parameters of a replicated construct, etc) and the process-list contains all the processes combined by the constructor CONTROL. None of these processes should

a) Assign to a variable whose rank is not a superset of that of expression.

b) Perform input or output on a channel whose rank is not a superset of that of expression.

c) Communicate on an index contained in the rank of expression.

Since we mainly assume channels are scalar, b) amounts to saying that IO is only allowed in any of the combined processes if the control expression is scalar.

RULE 2: In any assignment

     a := expression

the assignment is only correct if the rank of a is a superset of that of expression. (There is a natural generalisation to channel IO. However we assume that IO on distributed channels goes through library routines, so the generalisation isn’t very relevant here).

2 The Application Library. I: Index Communications

This section and the next describe the “application library”: the top-level communication library. These sections present a non-exhaustive list of procedure interfaces in the library, with informal descriptions of their behaviour.

A note on presentation of interfaces: here we use the language described in section 1 to describe the distribution of parameters passed to procedures. A couple of conventions are adopted

1. “Type Polymorphism”: The symbol T is used as a “type-variable” in the interfaces. Many communication routines don’t depend on the arithmetic type of their parameters. Where several formal parameters in a procedure header have type T it is assumed that the arithmetic types of the corresponding actuals are the same, but any type is acceptable.

2. “Rank Polymorphism”: Wherever a number of distributions are included in the formal parameter list, the corresponding set of actual parameters may have ranks larger than the formals, provided the index set obtained by subtracting the rank of the formal from that of the corresponding actual is the same for all such parameters.

Throughout this section the symbol N means SIZE x. The notation ⟨n⟩ is used to mean the set 0 … n − 1, so in particular ⟨N⟩ is the set of coordinate values for x.

2.1 Broadcasts

A series of broadcast operations are provided

    PROC BROADCAST     ([] INDEX x, [] T result, VAL {x} T data)
    PROC BROADCAST.EL  ([] INDEX x,    T result, VAL {x} T data,
                                                   VAL INT src)
    PROC BROADCAST.ARR ([] INDEX x, [] T result,
                           VAL {x} INT seg.size, VAL {x} [] T data)

These all take distributed data as inputs and return global data. Let d_{i} be the value of data held at the site with coordinate i. BROADCAST broadcasts the values of the whole distribution to all processes. On exit the value of result[i] is d_{i}. BROADCAST.EL broadcasts a single element of the distribution; on exit the value of result is d_{σ}, where σ is the (global) value of src. BROADCAST.ARR is similar to BROADCAST, but data is a variable length array; if s_{i} is the value of seg.size at site i, then on exit the value, r, of result is given by

[ r FROM ∑_{j=0}^{i−1} s_{j} FOR s_{i} ] = d_{i}

In other words, the output is the result of collecting the segments of data held locally into one large global array.

2.2 Permutations

The basic permutation operations are

    PROC PERM.D  ([] INDEX x, {x} T result, VAL {x} T data,
                                  {x} INT src, VAL {x} INT dst)
    PROC PERM.DS ([] INDEX x, {x} T result, VAL {x} T data,
                                          VAL {x} INT src, dst)

PERM.D permutes the elements of the distribution data to produce result—the destination coordinate for the local value of data is defined in dst. The source coordinate for the locally received value of result is returned in src. Let σ_{i}, δ_{i} be respectively the values of src and dst held at the site with coordinate i. For succesful termination PERM.D needs the precondition

\begin{matrix}∀ \\ i′ ∈ ⟨N⟩ \end{matrix} \begin{matrix}∃ \\ i ∈ ⟨N⟩ \end{matrix} δ_{i} = i′

(In other words dst defines a permutation) ^{1}. PERM.DS is similar, but requires the source for each incoming datum to be specified, in src, as an input. It needs the extra precondition

\begin{matrix}∀ \\ i ∈ ⟨N⟩ \end{matrix} σ_{δ_{i}} = i

1PERM.D is not implemented in the current release.

(In other words src and dst define inverse permutations).

Having to guarantee these preconditions to avoid deadlocks makes these routines potentially error prone. So several common special cases of permutations are provided which are automatically deadlock free.

    PROC PERM.SHIFT   ([] INDEX x, {x} T result, VAL {x} T data,
                                                   VAL INT shift)
    PROC PERM.XOR     ([] INDEX x, {x} T result, VAL {x} T data,
                                                   VAL INT p)
    PROC PERM.REFLECT ([] INDEX x, {x} T result, VAL {x} T data,
                                                   VAL INT a)
    PROC PERM.SWAP    ([] INDEX x, {x} T result, VAL {x} T data,
                                                   VAL INT i.1, i.2)

The permutations performed are r_{i′} = d_{i} where respectively

i′ = i + shift mod N
i′ = \{ \begin{matrix}i ⊕ p & if i ⊕ p < N \\ i & otherwise \end{matrix}
i′ = a − i mod N
i′ = \{ \begin{matrix}i_{2} & if i = i_{1} \\ i_{1} & if i = i_{2} \\ i & otherwise \end{matrix}

⊕ is bitwise exclusive or.

As a small convenience, all permutations are also supplied as entry points which perform the permutation in situ in the data array, for example

    PROC PERM.DS.IN  ([] INDEX x, {x} T data, VAL {x} INT src, dst).

2.3 Relations

The “relation” provided is a generalisation of the permutation. Instead of a single message being sent to a single destination process, and a single message received from a single source, in a relation an arbitrary number of messages are sent to arbitrary destinations, and an arbitrary number received from arbitrary sources. Example applications are

• permuting data, where more than one data element is held in each process.

• distributing data held on a single process across several processes.

These are complicated operations. The interfaces provided are

    PROC RELATE.D  ([] INDEX x,
                     {x} INT res.size,     {x} [] T result,
                 VAL {x} INT dat.size, VAL {x} [] T data,
                  {x} [] INT src.coord, src.addr,
              VAL {x} [] INT dst.coord, dst.addr)
    PROC RELATE.DS ([] INDEX x,
                 VAL {x} INT res.size,     {x} [] T result,
                 VAL {x} INT dat.size, VAL {x} [] T data,
              VAL {x} [] INT src.coord, src.addr,
                             dst.coord, dst.addr)

RELATE.D sends the dat.size messages in data from each process to the processes with coordinates given in dst.coord. When the messages arrive they are to be placed in the array result at the address specified by dst.addr. (The correspondence between elements of the three arrays data, dst.coord and dst.addr is naturally according to subscript in those arrays). Aside from result, the source coordinate and source address in data of each message received are returned in src.coord and src.addr. Also the total number of messages received locally is returned in res.size. Let σ_{i}^{C}, σ_{i}^{A}, s_{i}^{d}, δ_{i}^{C}, δ_{i}^{A}, s_{i}^{r} be respectively the values of src.coord, src.addr, dat.size, dst.coord, dst.addr and res.size held at the site with coordinate i, and let

A_{i′} = \{l′ | \begin{matrix}∃ \\ i ∈ ⟨N⟩ \end{matrix} \begin{matrix}∃ \\ l ∈ ⟨s_{i}^{d}⟩ \end{matrix} (δ_{i}^{C}[l] = i′) ∧ (δ_{i}^{A}[l] = l′)\}

(A_{i′} is the set of destination addresses of messages incoming to site i′.) Then RELATE.D needs the precondition

( \begin{matrix}∀ \\ i′ ∈ ⟨N⟩ \end{matrix} A_{i′} = ⟨|A_{i′}|⟩) ∧ ( ∑_{i′∈⟨N⟩} |A_{i′}| = ∑_{i∈⟨N⟩} s_{i}^{d})

which says that all the sets A_{i′} are of the form 0 … a − 1, (a = |A_{i′}| will be the returned value s_{i′}^{r} of res.size) and sum of the a’s is the sum of the number of messages sent (so no two messages are sent to the same place) ^{2}. RELATE.DS is similar, but requires the source coordinates and addresses (in the source site data array) for each incoming datum to be specified in src.coord and src.addr, as inputs. It needs the additional precondition

\begin{matrix}∀ \\ i′ ∈ ⟨N⟩ \end{matrix} \{(s_{i′}^{r} = |A_{i′}|) ∧ \begin{matrix}∀ \\ l′ ∈ A_{i′} \end{matrix} ((δ_{σ_{i′}^{C}[l′]}^{C}[σ_{i′}^{A}[l′]] = i′) ∧ (δ_{σ_{i′}^{C}[l′]}^{A}[σ_{i′}^{A}[l′]] = l′))\}

to guarantee agreement of source and destination specifications.

(A third version could be provided in which dst.addr didn’t have to be supplied as an input. This would eliminate the complicated preconditions; the most natural specification would return incoming messages in non-deterministic order in the result array.)

2.4 Prefixes

The library provides a set of “prefix” type operations. Generically, given some distribution d over x, these calculate the distribution r with values

r_{i} = d_{0} ⊗ … ⊗ d_{i}

2RELATE.D is not implemented in the current release.

for some associative operation ⊗, which could be, for example, addition, logical and, maximum or minimum, etc. These routines all have a common interface and naming convention. In this section we will take addition of REAL32 numbers as a particular case. The routines are

    PROC PREFIX.REAL32.SUM ([] INDEX x, {x} REAL32 result,
                      VAL {x} REAL32 data)
    REAL32 FUNCTION GLOB.REAL32.SUM ([] INDEX x, VAL {x} REAL32 data)

PREFIX.REAL32.SUM calculates a distribution of partial sums, as described above. GLOB.REAL32.SUM is a function which returns the sum of all elements of data as a global variable.

2.5 Multi-index operations

Presently the library doesn’t contain any operations (apart from the IO operations on multi-dimensional distributions in the next section) which take more than one index as parameters. Some obvious candidates for such operations would be matrix operations, such as matrix transpose. One might want more general permutations on multidimensional data-sets. Square matrix transpose can be implemented efficiently in terms of operations already given:

    PROC transpose ([] INDEX x, y, {x, y} T data)
      SEQ
        PERM.SHIFT.IN   (x, data,  INDEX.coord (y))
        PERM.REFLECT.IN (y, data,  INDEX.coord (x))
        PERM.SHIFT.IN   (x, data, -INDEX.coord (y))
    :

This assumes SIZE x = SIZE y. It follows a routing i, j → i + j, j → i + j, i → j, i. By replacing the special permutations by the general PERM.DS operation, with suitable src to dst routing, it is also possible to achieve an arbitrary two-dimensional permutation in three “moves” ^{3}. Unfortunately this isn’t generally practical, because the routing calculation is fairly complicated. However it suggests that for common permutations the library’s restriction to operations on single indices probably won’t be too severe.

3 The Application Library. II: Input and Output

Input and output involving array processes are performed on logical channels. Channels accessed from within array processes are called “distributed channels”. Distributed channels carry the same sort of sequential protocols as normal occam channels, and often the “other end” of a distributed channel will be an ordinary channel.

In the current implementation distributed channels can only be accessed through the communication library. Direct occam style IO on a distributed channel won’t work.

When applying the “rank polymorphism” rule of the previous section the channel itself should be regarded as a distribution. If the ranks of the actual data parameters are larger than in the formal parameter list, the call will only be valid if rank of the actual channel parameter is corresponding larger than the formal. In the simplest case all existing distributed channels are scalar, and rank polymorphism can’t be applied

3This was pointed out to me by D.J. Pritchard.

3.1 Communicating globals

The routines for inputting and outputting global values on distributed channels are

    PROC INPUT      (CHAN chan, T   result, VAL INT tag)
    PROC OUTPUT     (CHAN chan, VAL T data, VAL INT tag)
    PROC INPUT.TAG  (CHAN chan,     INT tag)
    PROC OUTPUT.TAG (CHAN chan, VAL INT tag)

INPUT and OUTPUT normally input or output a message. The calls are equivalent, respectively to

    chan ? CASE tag; result
    chan ! tag; data

Following current occam implementations, the actual tag value read or written is a single byte. If the tag parameter passed is the reserved value T.UNTAGGED no tag is read or written. INPUT.TAG and OUTPUT.TAG input or output a single global byte value (they are useful for communicating control information).

3.2 Communicating whole distributions

A series of procedures are provided for performing IO on whole multi-dimensional distributions

    PROC INPUT.1D  (CHAN chan, [] INDEX x,    {x}    T   result,
                 VAL INT tag)
    PROC INPUT.2D  (CHAN chan, [] INDEX x, y, {x, y} T   result,
                 VAL INT tag)
    ...
    PROC OUTPUT.1D (CHAN chan, [] INDEX x,    VAL {x}    T data,
                 VAL INT tag)
    PROC OUTPUT.2D (CHAN chan, [] INDEX x, y, VAL {x, y} T data,
                 VAL INT tag)
    ...

If d_{i} is the value of data held at sites with x-coordinate i, OUTPUT.1D outputs the stream

    chan ! tag; d_{0} ; tag; d_{1} ; ... ; tag; d_{N−1}

where the subscript on data represents the coordinate with respect to x of the datum.

INPUT.1D inputs the same stream, assigning d_{i} to result at site i. The higher dimensional routines behave similarly; in each case the coordinate with respect to the last index appearing in the parameter list is “most-rapidly-varying” in the output stream; if d_{ij} is the value of data held at sites with x-coordinate i and y-coordinate j, OUTPUT.2D outputs the stream

    chan ! tag; d_{00} ; tag; d_{01} ; ... ; tag; d_{0,M−1} ;
             tag; d_{10} ; ...
                                     ... ; tag; d_{N−1,M−1}

(where M = SIZE y).

3.3 Elements of distributions

The routines

    PROC INPUT.1D.EL  (CHAN chan, [] INDEX x,    {x}    T   result,
                    VAL INT dst.x, tag)
    PROC INPUT.2D.EL  (CHAN chan, [] INDEX x, y, {x, y} T   result,
                    VAL INT dst.x, dst.y, tag)
    ...
    PROC OUTPUT.1D.EL (CHAN chan, [] INDEX x,    VAL {x}    T data,
                    VAL INT src.x, tag)
    PROC OUTPUT.2D.EL (CHAN chan, [] INDEX x, y, VAL {x, y} T data,
                    VAL INT src.x, src.y, tag)
    ...

communicate single elements of the distribution from the specified coordinates on chan, with the usual tagged protocol.

3.4 Distributions of arrays

These routines

    PROC INPUT.1D.ARR  (CHAN chan, [] INDEX x,
                 VAL {x} INT seg.size.x,
                    {x} [] T result,
                     VAL INT tag)
    PROC INPUT.2D.ARR  (CHAN chan, [] INDEX x, y,
                 VAL {x} INT seg.size.x, VAL {y} INT seg.size.y,
              {x, y} [] [] T result,
                     VAL INT tag)
    ...
    PROC OUTPUT.1D.ARR (CHAN chan, [] INDEX x,
                 VAL {x} INT seg.size.x,
                VAL {x} [] T data,
                     VAL INT tag)
    PROC OUTPUT.2D.ARR (CHAN chan, [] INDEX x, y,
                 VAL {x} INT seg.size.x, VAL {y} INT seg.size.y,
          VAL {x, y} [] [] T data,
                     VAL INT tag)
    ...

can be used for performing IO on d-dimensional distributions of d-dimensional arrays. The special feature is that the data is input or output in the same order as if the local segments were joined together across the array to form one big d-dimensional array. OUTPUT.1D.ARR outputs the stream

    chan ! tag; d_{0}[0] ; tag; d_{0}[1] ; ... ; tag; d_{0}[s_{0} − 1] ;
             tag; d_{1}[0] ; ...

... ; tag; d_{N−1}[s_{N−1} − 1]

(s_{i} is the value of seg.size.x held at sites with x-coordinate i). whereas OUTPUT.2D.ARR outputs the stream (expressed in occam pseudocode)

    SEQ i = 0 FOR N
      SEQ I = 0 FOR s_{i}
        SEQ j = 0 FOR M
          SEQ J = 0 FOR t_{j}
            chan ! tag; d_{ij}[I][J]

(t_{i} is the value of seg.size.y held at sites with y-coordinate i).

References

[1] D.B. Carpenter. Geometric Parallelism. PUMA workpackage 5.1 interim report.

[2] Array Communication Library: Reference Manual. 14