Regular collective communications

There are three main families of collective operation in Adlib: regular communications, reduction operations, and irregular communications.

The regular communications are exemplified the operations shift, cshift, writeHalo and remap, introduced in earlier sections. The last of these, remap, is a very characteristic example. The remap function takes two distributed array arguments--a source array and a destination. These two arrays must have the same size and shape ^6.1but they can have any, unrelated, distribution formats. The effect of the operation is to copy the values of the elements in the source array to the corresponding elements in the destination array, performing any communications required to do that. If the destination array has replicated mapping, the remap operation will broadcast source values to all copies of the destination array elements.

The remap function is a static member of the Adlib class. Like most of the functions in Adlib, the remap function is overloaded to apply to various ranks and types of array:

    void remap(int    [[]] destination, int    [[]] source) ;
    void remap(float  [[]] destination, float  [[]] source) ;
    void remap(double [[]] destination, double [[]] source) ;
    ...
    void remap(int    [[,]] destination, int    [[,]] source) ;
    void remap(float  [[,]] destination, float  [[,]] source) ;
    void remap(double [[,]] destination, double [[,]] source) ;
    ...
    void remap(int    [[,,]] destination, int    [[,,]] source) ;
    void remap(float  [[,,]] destination, float  [[,,]] source) ;
    void remap(double [[,,]] destination, double [[,,]] source) ;
    ...

and scalars:

    void remap(int    # destination, int    # source) ;
    void remap(float  # destination, float  # source) ;
    void remap(double # destination, double # source) ;
    ...

Currently the element-type overloading includes all Java primitive types. Later Adlib will be extended to support Object types.

There are four preconditions for a call to remap:

1. All processes in the active process group must make the call, and they must pass coherent arguments--in other words, for each argument, all processes pass local references to logically the same distributed array.
2. As mentioned above, the source and destination arrays should have the same shape and element types.
3. The arrays source and destination must not overlap--no element of source must be an alias for an element of destination. This is only an issue if both arguments are sections of the same array.
4. Both arguments must be fully contained.

By definition, an array is ``fully contained'' if its distribution group is contained in the active process group. So the requirement is that every copy of every element of the array is held on one of the processors engaging in the collective operation.

Most of the functions in Adlib have a similar set of preconditions--all operations are called collectively with coherent arguments, input and output arrays should never overlap, and array arguments must always be fully contained in the active group. The last requirement is probably the easiest to overlook. Consider the example of section 3.3, Figure 3.15. An easy mistake would be to put the calls to remap inside the following on construct. This is an error, because there is no guarantee that distribution groups of a and b are contained in the distribution group, p, of c. The function matmul is supposed to work for arguments with any, unrelated, distribution format. The Adlib library includes runtime checks for containment of arrays. If an argument is not fully contained, an exception occurs.

So long as the rule on containment is observed, Adlib calls can be made freely inside distributed control constructs, including the parallel loop, overall. If, for example, we want to ``skew'' an array--shift rows in the y direction by an amount that depends on the x index--we can do something like

  on(p) {
    int [[,]] a = new int [[x, y]], b = new int [[x, y]] ;

    overall(i = x for :)
      Adlib.shift(b [[i, :]], a [[i, :]], i`) ;
  }

The section arguments of shift have distribution group p / i, which is identical to the active process group at this point, so the arguments are fully contained. A slightly more complicated example involving dotProduct was given earlier in section 4.5, Figure 4.6.

A prototype of the shift function was given in section 2.3. In general we have

    void shift($T$ [[]] destination, $T$ [[]] source, 

               int shiftAmount) ; 

    void shift($T$ [[,]] destination, $T$ [[,]] source, 

               int shiftAmount, int dimension) ; 

    void shift($T$ [[,,]] destination, $T$ [[,,]] source, 

               int shiftAmount, int dimension) ; 

    ...

where $T$ stands for any primitive type of Java. The dimension argument is in the range $0, \ldots, R - 1$ where $R$ is the rank of the arrays. It selects the array dimension in which the shift occurs. The shiftAmount argument, which may be negative, specifies the amount and direction of the shift. Again the source and destination arrays must have the same shape, but now there is an extra precondition--they must also be identically aligned. That is, their distribution groups must be identical and all their ranges must be identical or satisfy the isAligned test. By design, shift implements a simpler pattern of communication than general remap. The alignment relation allows a more efficient implementation. The library includes runtime checks on alignment relations between arguments, where these are required.

The shift operation discards values from source that are moved past the edge of destination. At the other end of the range, elements of destination that are not targetted by elements from source are unchanged from their input value. The operation cshift is essentially identical to shift except that it implements a circular shift.

The function writeHalo is applied to distributed arrays that have ghost regions. It updates those regions. The simplest versions have prototypes

    void writeHalo($T$ [[]] a) ; 

    void writeHalo($T$ [[,]] a) ; 

    void writeHalo($T$ [[,,]] a) ; 

    ...

We can distinguish between the locally held physical segment of an array and the surrounding ghost region, which is used to cache local copies of remote elements. The effect of writeHalo is to overwrite the ghost region with values from processes holding the corresponding elements in their physical segments.

A more general form of writeHalo allows to specify that only a subset of the available ghost area is to be updated, and to select circular wraparound for updating ghost cells at the extreme ends of the array, if desired.

    void writeHalo($T$ [[]] a, int wlo [], int whi [], int [] mode) ; 

    void writeHalo($T$ [[,]] a, int wlo [], int whi [], int [] mode) ; 

    void writeHalo($T$ [[,,]] a, int wlo [], int whi [], int [] mode) ; 

    ...

The three integer vectors are all of length $R$, the rank of a. The first two specify the widths at upper and lower ends of the bands to be updated (these values must be less than or equal to the widths of the actual ghost areas on the array). The elements of mode define for each dimension whether to update in the normal way, leaving ghost edges at extreme edges of the arrays unwritten (value should be WriteHalo.EDGE), whether to update using circular wraparound ( WriteHallo.CYCL), or whether to not update any ghost regions in this dimension at all ( WriteHallo.NONE, equivalent to setting the corresponding elements of wlo, whi to zero).

Operation of writeHalo is visualized in figure 6.1.

Figure 6.1: Illustration of the effect of executing the writeHalo function.

[Need to do something about Adlib.copy. Probably this should be moved into a standard HPJava library.]