Subranges

A subrange is a section of a range, parametrized by a subscript triplet. Logically a subrange can be viewed as a subset of the locations of the original range. Subranges are members of the class Range. Because locations in a subrange are locations of the parent range, subranges retain an alignment relation to their parent range. Note that the integer subscripts for a subrange are in the range $0, \ldots, N - 1$ where $N$ is the extent of the subrange. See figure 6.

A triplet-subscripting syntax is used for creation of subranges: if x is a range, then x [0 : 49] is a contiguous subrange and x [1 : 98 : 2] is a strided subrange.

Figure 6: Locations of a subrange (shaded slots).

As a first application of subranges, we can uses strided subranges to transform the Jacobi update of the previous section to a more efficient red-black form. The result is shown in figure 7. The iteration is split into two phases, the first with parity $= 0$ and the second with parity $= 1$. The range of the inner over construct is either y [0 : : 2] or y [1 : : 2], according to whether the global x index of the outer loop has the same or different parity (odd/even) as the current phase. This version eliminates all temporary arrays¹¹

Figure 7: Red-black iteration.

As a second application involving subranges, figure 8 is a parallel version of Cholesky decomposition. In pseudocode the algorithm is

$$\begin{array}{l} l_{11}=a_{11}^{1/2} \\ For\; k=1\; to\; n-... ...} \\ \;\;\;\; l_{k+1, k+1}= a_{k+1, k+1}^{1/2} \\ \end{array}$$

The array is distributed by columns, using cyclic distribution to improve load balancing. The collective communication function remap is used to broadcast updated columns. The remap function is one of the more powerful functions in the communication library. Like copy, its effect is to copy data from one distributed array to another of the same shape and type. But copy (like shift) has a restriction that its array arguments must be aligned--copy never introduces communication. With remap there is no such restriction--the mapping of the two arrays can be unrelated. One common application of remap is to broadcast data. If the target array has no ranges distributed over a dimension of the process group on which it lives, remap assumes that the result is to be stored in a replicated fashion. It therefore implements a broadcast. In the current example remap actually implements something more sophisticated than a simple broadcast. In MPI terms it executes a gather-to-all operation.

Figure 8: Choleksy decomposition.

Some final comments on subranges. Creating a triplet subscripted section of a distributed array implicitly creates subranges of the ranges in the parent array. Also, arrays can be created directly with subranges, as in

  Range xs = x [0 : 50] ;
  Range ys = y [1 : 198 : 2] ;

  int [[#,#]] e = new int [[xs, ys]] ;

In HPF terms, e has a non-trivial linear alignment to the template spanned by x and y. By allowing subranges (and subgroups, see section 9) to appear in array constructors we reproduce the two-level alignment model of HPF in full generality, at little cost in terms of syntax extensions.