Array Sections

HPJava has a mechanism for representing subarrays. This mechanism is modelled on the regular array sections of Fortran 90. The syntax of array sections looks superficially similar to the syntax of array element references, but uses double brackets. Also section subscripts allow several options not available in element subscripts. The most obvious new option is that a subscript can be an index triplet.

We already saw examples of index triplets used in the header of the overall construct. The most general form is:

  
lower : upper : stride

This involves three numbers, hence of course the name "triplet". There is a lower bound, an upper bound, and a stride. The triplet denotes a sequence of integer values starting at lower, and incremented by stride. The value of stride may be positive or negative. If stride is positive (and upper is greater than or equal to lower) the sequence continues as long as its values are less than or equal to upper (the sequence is empty if upper is less than lower). Likewise, if stride is negative and upper is less than or equal to lower, the sequence continues downwards as long as its values are greater than or equal to upper. In the negative stride case the sequence is empty if upper is greater than lower.

The abbreviated form of triplet:

  
lower : upper

is equivalent to the general form with stride equal to 1. Finally there is a degenerate form of triplet:

i.e. a single colon. This is equivalent to additionally setting lower to zero, and upper to N - 1, where N is the size of the controlling range object - in other words the triplet covers all values of the range. (Fortran has a few additional options for abbreviating triplets. For now those extra options are not available in HPJava - it is limited to exactly the three formats described above.)

A section is an array in its own right - its type is that of a suitable multi-dimensional array. But it contains a subset of the elements in its parent array, rather than introducing its own set of element variables. If a is an 8 by 8 array distributed blockwise over a 2 by 3 process grid, the section:

    a [[3:6, 1:4]]

contains the elements of in the red area below:

A section is an array, so its elements are variables (they can appear on the left-hand-side of assignments). The section expression itself, on the other hand, is not a variable, and cannot appear on the left-hand-side of an assignment. We cannot write, for example

    a [[3:6, 1:4]] = b ;  // Illegal!

where b is some 4 by 4 array. This is different to Fortran and some similar languages. To achieve the effect probably intended by the above assignment we would have to write:

    Adlib.remap(a [[3:6, 1:4]], b) ;

This copies elements of the arrays, allowing for the fact that the arrays may have different distribution formats, in which case the element-by-element assignment requires communication. If we know in advance that the arrays have identical distribution format, we can use the HPutils.copy() method, which copies elements of aligned arrays:

    HPutils.copy(a [[3:6, 1:4]], b) ;

Notice that (conversely) it is perfectly legal for an array section to appear on the right-hand-side of an assignment, as in:

    float [[-,-]] c ;
    ...
    c = a [[3:6, 1:4]] ;  // Legal

An array section expression evaluates to a distributed array reference, which can be copied to the variable c. The array c now looks like:

c[0,0] is now an alternate name for the variable a[3,1], and so on. Because elements are literally shared with the parent array, modifying an element of the section modifies the corresponding element of the parent. This may seem strange, but bear in mind that Java already allows similar aliasing of its array elements, by copying references to ordinary Java arrays.

The distribution format of c looks a little strange. In general a distributed array section has a new kind of distribution format that cannot be described very naturally by the range classes described so far. In fact a new family of ranges called a subranges is used to describe the distribution of sections. Just as an array section shares elements with its parent array, a subrange is considered to share locations with its parent array.

Some (or indeed all) of the subscripts in an array section can be scalar subscripts. These are either simple integer expressions or distributed index symbols. In contrast to element references, there is no requirement that section subscripts in distributed dimensions of arrays be distributed indexes (however, if a section subscript is a distributed index, it must still be bound to a location in the associated range of the parent array).

The section a[[2, :]] describes the red area below:

Each scalar subscript reduces the rank of the result array by 1. So we may copy the section reference to a rank-1 distributed array as follows:

    float [[-]] d ;
    ...
    d = a [[2, :]] ;

The array d now looks like:

Again there is something strange about the distribution format of d - this time it is a subtle issue relating to the process group. The one-dimensional array d still has a range distributed over the horizontal dimension of the process grid, but it no longer has range distributed over the vertical dimension. According a rule stated early on, if d is considered to be distributed over the whole process grid, we would expect its elements to be replicated across the vertical dimension. Clearly they are not. The natural solution is to consider array d to be distributed over the restricted group consisting of the top row of the grid.

HPJava only allows its special distributed arrays to be sectioned - not ordinary Java arrays.

Syntax for Subranges and Restricted Groups

Subranges and restricted groups normally exist "behind the scenes" in HPJava programs: one rarely needs to create them explicitly. But, for closure, the language provides some syntax for doing that.

A subrange can be created explicitly by subscripting a range object with a proper triplet. Double brackets are used, as in

  Range x ;

  ... x [[l : u : s]] ...
  ... x [[l : u]] ...

The division operation / is overloaded to explicitly create restricted groups. The second operand of the restriction operator is a formal location. The expression:

  
group / location

refers to the subgroup of group to which location is mapped. In this context location can either be a distributed index symbol, or it can be a special syntactic term of the form

  
range [expr]

where expression range refers to a range object and expression expr has type int.

Next: Another Example - Choleski Decomposition

Bryan Carpenter, (dbc@ecs.soton.ac.uk). Last updated May 2007.