Collapsed Distributions and Sequential Dimensions

The CollapsedRange subclass in Figure 3.1 stands for a range that is not distributed--all elements of the range are mapped to a single process. The code

$$\begin{minipage}[t]{\linewidth}\small\begin{verbatim}Proc... ...] a = new float [[x, y]] ;... }\end{verbatim}\end{minipage}$$

creates an array in which the second dimension is distributed over processes in q, with the first dimension collapsed. The situation is visualized for the case N = 8 in Figure 3.14. This, by the way, is our first example of a one-dimensional process ``grid''.

Figure 3.14: Two-dimensional array, a, distributed over the one-dimensional grid, q.

Because of the limitations on what kinds of subscripts are allowed in accessing distributed array elements, the language defined so far doesn't provide a good way to exploit the locality implied by a collapsed dimension. So in practice it is doubtful that one would explicitly create a distributed array with a collapsed dimension in the way just shown. Instead HPJava is extended to allow distributed arrays to have sequential dimensions.

Given that we introduced sequential multiarrays in Chapter 1, sequential dimensions shouldn't seem like an unfamiliar idea. The type signature of a distributed array may have asterisks in place of hyphens in some of its dimensions. This indicates that that these dimensions implicitly have a collapsed range. These dimensions can be subscripted with integer expressions just like dimensions of a sequential multiarray. Here is an example:

$$\begin{minipage}[t]{\linewidth}\small\begin{verbatim}Proc... ... = y [1]) a [6, j] = a [1, j] ; }\end{verbatim}\end{minipage}$$

The at construct deals with the distributed dimension, but there is no need for distributed indices in subscripting the sequential dimension. The distributed array creation expression is passed integer extent expressions for sequential dimensions. A CollapsedRange object will be created for the array, but generally the programmer does not need to be aware of its existence.

Figure 3.15: A pipelined matrix multiplication program.

$$\begin{minipage}[t]{\linewidth}\small\begin{verbatim}Proc... ..., 1) ; HPutil.copy(b, tmp) ; } }\end{verbatim}\end{minipage}$$

Figure 3.15 is an example of a parallel matrix multiplication in which the first input array, a, and result array, c, are distributed by rows--each processor is allocated a consecutive set of complete rows. The first dimension of these array is distributed, breaking up the columns, while the second dimension is collapsed, leaving individual rows intact. The second input array, b, is distributed by columns.

The standard library function HPutil.copy() copies elements between two aligned arrays (unlike Adlib.remap(), copy() does not implement communication; if it is passed non-aligned arrays, an exception occurs). The cshift() method of Adlib is similar to the shift() method introduced earlier, except that it implements a cyclic shift--wrapping edge values around.

Distributed array types with sequential dimensions are technically subtypes of corresponding distributed array types without sequential dimensions. All operations generally applicable to distributed arrays are also applicable to arrays with sequential dimensions. The asterisk in the type signature adds the option of subscripting the associated dimension with integer espressions. It does not remove any option allowed for distributed arrays in general.