Regular collective communications

There are three main families of collective operation in Adlib: regular communications, reduction operations, and irregular communications. It also provides a few I/O operations.

The regular communications are exemplified by the operations remap(), writeHalo(), shift(), and cshift(), introduced in earlier sections. The first of these, remap(), is a very characteristic example. The remap() method takes two distributed array arguments--a source array and a destination. These two arrays must have the same size and shape^6.2but 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 necessary 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() method is a static member of the Adlib class. Like most of the methods in Adlib, the remap() method is overloaded to apply to various ranks and types of array:

$$\begin{minipage}[t]{\linewidth}\small\begin{verbatim}void... ...tion, double [[-,-,-]] source) ...\end{verbatim}\end{minipage}$$

and to scalars:

$$\begin{minipage}[t]{\linewidth}\small\begin{verbatim}void... ...stination, double [[]] source) ...\end{verbatim}\end{minipage}$$

For this family of operations the element-type overloading includes all Java primitive types, and the type Object. Object elements are communicated using the standard Java serialization mechanism, and the detailed interpretation of what it means to remap an array of objects (e.g. the extent to which referential integrity between the objects is preserved) follows from the semantics of those standard Java mechanisms^6.3.

The overloading with respect to rank is slightly more problematic, because there are infinitely many possible ranks, and for now the HPJava language has no way to express that an argument can have arbitrary rank. As currently implemented, we can summarize the available remap() signatures in the notation:

$$\begin{minipage}[t]{\linewidth}\small\begin{tabbing} \verb$ ... ... destination, $$T$\verb$ ...$$

where the variable $T$ runs over all primitive types and Object, and the notation $T$ # means a multiarray of arbitrary rank, with elements of type $T$.

This notation is quite terse, and perhaps cryptic at first sight, but you will need to get used to it to follow the rest of this chapter. Bear in mind that one should mentally expand this kind of prototype into a series of signatures similar to the ones given above.

You may notice that this shorthand signature contains slightly less information than the series given above, because it doesn't impose as a compile-time constraint that source and destination arrays have the same rank. But as a matter of fact it is a more accurate reflection of the current implementation--although it is not possible to define multiarray parameters of unspecified rank within the HPJava language (i.e. there is no such type as $T$ # in HPJava), the translator provides a special hook that allows methods of ``externally defined'' libraries--typically libraries written in standard Java--to behave as if they had such parameters.

There are four preconditions to a call to remap():

1. All processes in the active process group must make the call, and they must pass coherent arguments--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 (or, if the element types are Object, all objects referenced by elements of the source array must be assignable to elements of the destination array).
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'' in the active process group.

By definition, an array is fully contained in the APG if the array's distribution group is contained in the active process group. In other words, the requirement is that every copy of every element of both arrays is held on a processor involved in the collective operation.

If the second condition above is not satisfied an hpjava.adlib.schedule.RankMismatchException or an hpjava.adlib.schedule.ShapeMismatchException will be thrown. If the last condition is not satisfied an hpjava.adlib.schedule.InaccessibleException will be thrown.

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.4, Figure 3.18. 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 in the APG, an exception occurs as described above.

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

$$\begin{minipage}[t]{\linewidth}\small\begin{verbatim}on(p... ...ft(b [[i, :]], a [[i, :]], i\lq ) ; }\end{verbatim}\end{minipage}$$

The section arguments of shift have distribution group $\mbox{\tt p} / \mbox{\tt 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.8, Figure 4.6.

A prototype of the shift() function was given in section 2.4. In general we have the signatures:

$$\begin{minipage}[t]{\linewidth}\small\begin{tabbing} \verb$ ... ...urce,$ \\ \verb$ int shiftAmount)$ \end{tabbing}\end{minipage}$$

and

$$\begin{minipage}[t]{\linewidth}\small\begin{tabbing} \verb$ ... ...b$ int shiftAmount, int dimension)$ \end{tabbing}\end{minipage}$$

with $T$ defined as above. The first form applies only for one dimensional multiarrays. The second form applies to multiarrays of any rank. The shiftAmount argument, which may be negative, specifies the amount and direction of the shift. In the second form 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. 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 their corresponding ranges $x$, $y$ must be identical or at least satisfy the test $x$.isAligned($y$). By design, shift() implements a simpler pattern of communication than general remap(). The alignment relation allows for a more efficient implementation. The library incorporates runtime checks on alignment relations between arguments, where these are required. If the arguments of shift() are not correctly aligned an hpjava.adlib.schedule.GroupMismatchException or an hpjava.adlib.schedule.MisalignmentException will be thrown.

The shift() operation does not copy values from source that would go past the edge of destination, and at the other extreme of the range elements of destination that are not targetted by elements from source are unchanged from their input value. The related operation cshift() is essentially identical to shift() except that it implements a circular shift, rather than an ``edge-off'' shift.

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

$$\begin{minipage}[t]{\linewidth}\small\begin{tabbing} \verb$ void writeHalo($$T$\verb$ ...$$

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.

More general forms of writeHalo allow to specify that only a subset of the available ghost area is to be updated, or to select circular wraparound for updating ghost cells at the extreme ends of the array:

$$\begin{minipage}[t]{\linewidth}\small\begin{tabbing} \verb$ ... ...verb$ ...$$

and

$$\begin{minipage}[t]{\linewidth}\small\begin{tabbing} \verb$ ... ...t wlo [], int whi [], int [] mode)$ \end{tabbing}\end{minipage}$$

The integer vectors are all of length $R$, the rank of the argument a. The values wlo and whi 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 mode values define, dimension by dimension, whether to update in the normal way, leaving ghost edges at extreme edges of the arrays unwritten (value should be Adlib.EDGE), whether to update using circular wraparound (Adlib.CYCL), or whether to not update any ghost regions in this dimension at all (Adlib.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.

Finally we mention the function broacast(), which is actually a simplified form of remap(). There are two signatures:

$$\begin{minipage}[t]{\linewidth}\small\begin{tabbing} \verb$ ... ... broadcast($$T$\verb$ [[]] source)$ \end{tabbing}\end{minipage}$$

and

$$\begin{minipage}[t]{\linewidth}\small\begin{tabbing} \verb$ ... ...ast($$T$\verb$ source, Group root)$ \end{tabbing}\end{minipage}$$

The first form takes a scalar (rank-0 distributed array) as argument and broadcasts the element value to all processes of the active process group. Typically it is used in conjunction with a scalar section to broadcast an element of a general array to all members of the active process group, as in this fragment:

$$\begin{minipage}[t]{\linewidth}\small\begin{verbatim}int ... ...3 + Adlib.broadcast(a [[10, 10]]) ;\end{verbatim}\end{minipage}$$

The second form of broadcast() just takes an ordinary Java value as the source. This value should be defined on the process or group of processes identified by root. It is broadcast to all members of the active process group. Technically this version is only useful if the source expression is incoherent--see section 5.4--but it is quite handy in practical codes.