Subranges and restricted groups

Consider again the example of the array section in figure 4.2. We can capture this object in a named variable as follows

    float [[,]] a = new float [[x, y]] ;

    float [[,]] c = a [[0 : N / 2 - 1, : : 2]] ;

Now, what are the ranges of c--the objects returned by the rng() inquiry?

In fact they are a different sort of range from any considered so far--they are subranges. For completeness the HPJava language provides a special syntax for constructing subranges directly. Ranges equivalent to those of c can be created by

    Range u = x [0 : N / 2 - 1] ;
    Range v = y [: : 2] ;

This syntax should look quite natural. It is similar the subscripting syntax for locations, but the subscript is a triplet.

[Global subscripts in subranges.]

What about the distribution groups of sections? In this case triplet subscripts don't cause problems--the distribution group of c above can be defined to be the same as the distribution group of the parent array a. On the other hand the example of figure 4.1 is now problematic. This was constructed using a scalar subscript, effectively as follows:

    float [[,]] a = new float [[x, y]] on p ;

    float [[]] b = a [[0, :]]

The single range of b is clearly y, but identifying the distribution group of b with that of a doesn't seem to be right. If a one dimensional array is newly constructed with range y and distribution group p, as follows,

    float [[]] bnew = new float [[y]] on p ;

it is replicated over the first dimension of p. The section b clearly isn't replicated in this way. Where does the information that b is localized to the top row of processes go?

Triplet section subscripts motivated us to define subranges as a new kind of range. Likewise, scalar section subscripts will drive us to define a new kind of group. A restricted group is defined as the subset of processes in some parent group to which a particular location is mapped. In the current example, the distribution group of b is defined to be the subset of processes in p to which the location x [0] is mapped. Instead of further extending subscripting notations to describe these subgroups, the division operator is overloaded. The distribution group of b is equivalent to q, defined by

    Group q = p / x [0] ;

The expression in the initializer is called a group restriction operation ^4.2.

In a sense the definition of a restricted group is tacit in the definition of an abstract location. Without formally defining the idea, we used it implicitly in section 2.4. In Figure 2.6 of that section the set of processes with coordinates $(0,0)$, $(0,1)$ and $(0,2)$, to which location x[1] is mapped, can now be written as

    p / x [1]

and the set with coordinates $(0,1)$ and $(1,1)$, to which y[4] is mapped, can be written as

    p / y [4]

The intersection of these two--the group containing the single process with coordinates $(0,1)$--can be written as

    p / x [1] / y [4]

or as

    p / y [4] / x [1]

At first sight the definition of HPJava restricted groups may appear slightly arbitrary. One good way to argue that a language construct is ``natural'' is to demonstrate that it has a simple and efficient implementation. The subgroups introduced here have an attractively simple concrete representation. A restricted group is uniquely specified by its set of effective process dimensions and the identity of the lead process in the group--the process with coordinate zero relative to the dimensions effective in the group. The dimension set can be specified as a subset of the dimensions of the parent grid using a simple bitmask. The identity of the lead process can be specified through a single integer ranking the processes of the parent grid. So a general HPJava group can be parametrized by a reference to the parent Procs object, with the addition of just two int fields. It turns out that this representation is not only compact, but also lends itself to efficient computation of the most commonly used operations on groups.

Now we can give a formal definition of the mapping (distribution group and ranges) of a general array section. As a matter of definition an integer subscript $n$ in dimension $r$ of array $a$ is equivalent to a location-valued subscript $a$ .rng($r$ )[$n$ ]. By definition, a triplet subscript $l$ :$u$ :$s$ in the same dimension is equivalent to range-valued subscript ^4.3$a$ .rng($r$ )[$l$ :$u$ :$s$ ].

Suppose all integer and triplet subscripts are replaced by their equivalent location or range subscripts as just described. If the location subscripts are $i, j, \ldots$ the distribution group of the section is

    p / i / j / ...

where $p$ is the distribution group of the parent array. The $s$th range of the section is equal to the $s$th range-valued subscript.

Note that for a shifted location, as a matter of definition,

    p / (i $\pm$  expression)  =  p / i

This makes sense--a shifted location is supposed to find an array element in the same process as the original location, albeit that the element could be in a ghost region.

It shouldn't come as a surprise that subranges and restricted groups can be used in array constructors, on the same footing as the ranges and groups described in earlier sections. This means, for example, that temporary arrays can be constructed with identical mapping to any given section. This facility is useful when writing generic library functions, such as the matmul of Figure 3.15, which must accept full arrays or array sections indiscriminately ^4.4.

Unusually, this subsection introduced a couple of new pieces of syntax but did not give any full example programs that use them. The reason is that restricted groups and subranges largely exist ``below the surface'' in HPJava. The new notations are mainly needed to add a kind of semantic completeness to the language. It is not especially common to see subgroups or subranges constructed explicitly in HPJava programs.