Higher-level ranges and locations

The class BlockRange is a subclass of Range which describes a simple block-distributed range of subscripts. Like BLOCK distribution format in HPF, it maps blocks of contiguous subscripts to each element of its target process dimension⁶. The constructor of BlockRange usually takes two arguments: the extent of the range and a Dimension object defining the process dimension over which the new range is distributed.

  Procs2 p = new Procs2(3, 2) ;
  
  Range x = new BlockRange(100, p.dim(0)) ;
  Range y = new BlockRange(200, p.dim(1)) ;

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

a is created as a 100 $\times$ 200 array, block-distributed over the 6 processes in p. The fragment is essentially equivalent to the HPF declarations

  !HPF$ PROCESSORS p(3, 2)
  
  REAL a(100, 200)

  !HPF$ DISTRIBUTE a(BLOCK, BLOCK) ONTO p

Subscripting distributed arrays with non-primitive ranges introduces some new problems. An array access such as

  a [17, 23] = 13 ;

is perfectly legal if the local process holds the element in question. But deterimining whether an element is local is no longer so easy. When arrays had only primitive distributed ranges, it was straightforward to check that accesses were local--the subscript simply had to be equal to the local coordinate. With higher-level ranges, that simple condition no longer holds.

In practise it is unusual to use integer values directly as local subscripts in distributed array dimensions. Instead the idea of a location is introduced. A location can be viewed as an abstract element, or ``slot'', of a distributed range. Conversely, a range can be thought of as a set of locations. This model of a range is visualized in figure 1. An individual location is described by an object of the class Location. Each Location element is mapped to a particular slice of a process grid. In general two locations are identical only if they come from the same position in the same range. A subscripting syntax is used to represent location n in range x:

  Location i = x [n]

Figure 1: A range regarded as a set of locations, or slots.

This is an important idea in HPJava. By working in terms of abstract locations--elements of distributed ranges--one can usually respect locality of reference without resorting explicitly to low-level local subscripts and process ids. In fact the location can be viewed as an abstract data type incorporating these lower-level offsets.

Publically accessible fields of Location include dim and crd. The first is the process dimension of the parent range. The second is coordinate in that dimension to which the element is mapped. So the access to element a [17, 23] could now be guarded by conditionals as follows:

  Location i = x [17], j = y [23] ;

  if(i.crd == i.dim.crd())
    if(j.crd == j.dim.crd())
      a [17, 23] = 13 ;

This is still quite verbose and error-prone. The language provides a second distributed control construct (analogous to on) to deal with this common situation. The new construct is called at, and takes a location as its argument. The fragment above can be replaced with

  Location i = x [17], j = y [23] ;

  at(i)
    at(j)
      a [17, 23] = 13 ;

This is more concise, but still involves some redundancy because the subscripts 17 and 23 appear twice. A natural extension is to allow locations to be used directly as array subscripts:

  Location i = x [17], j = y [23] ;

  at(i)
    at(j)
      a [i, j] = 13 ;

Locations used as array subscripts must be elements of the corresponding ranges of the array.

The range class has a member function

  int Range.idx(Location i)

which can be used to recover the integer subscript, given a location in the range.

There is a restriction that an at(i) construct should only appear at a point of execution where i.dim is a dimension of the active process group. In the examples of this section this means that an at(i) construct, say, should normally be nested directly or indirectly inside an on(p) construct.