Java-D: proposals for comment

Bryan Carpenter

Aug.14, 1997

1 Motivations

This note proposes a set of extensions to the Java language to support SPMD data parallel programming. This work will embed the ad++ [1] model of data parallel programming in Java. There are two or three motivations for this work:

1. The Java language has been mooted as a modern language for scientific programming (somewhat independently of its current role as the programming language of the Internet) [2]. Early experiments on data parallel programming in Java [3] suggest that the current language needs some extension to conveniently support something like the ad++ model (ad++ is the user-level C++ interface to the NPAC PCRC library). Java, unlike C++, does not provide templates, operator overloading, reference parameters, or macros. Without these features it is difficult to provide an attractive interface to a distributed array library.

2. Even in C++, where the ad++ interface is reasonably convenient, it is not particularly efficient—the underlying Adlib library is efficient, but the macro-based implementation of the distributed loop in the ad++ interface is not. A Java preprocessor would be a proving ground for the source-to-source transformations needed to optimize the distributed loop. This would be a natural step towards an optimizing source-to-source preprocessor for the more complex C++ language.

3. Assuming the arguments above justify syntax extensions to Java, we have an added benefit: because the new syntax is not limited by the constraints of C++ templates (for example), and because the translator can automatically add declarations of various auxilliary variables, etc, the extended Java should be significantly easier to read and understand than original ad++.

2 Distributed Arrays

Java-D provides multi-dimensional distributed arrays. These are additional to— orthogonal to—the ordinary sequential arrays of Java.

Following the Adlib model, the mapping of a distributed array is described through two special classes: Group and Range. A Group object describes the process group over which array elements are distributed. A Range describes the mapping of an array dimension to a process dimension. These basic class have various subclasses some of which are illustrated below.

  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 [[p # x, y]] ;
  int   b [[#]]  = new int   [[p # x]] ;

Procs2 is a subclass of Group describing a two-dimensional process grid. Declaration of p creates a new partition of six of the active processes into a three by two grid. BlockRange is a subclass of Range describing an index space distributed block-wise over a process dimension. In the example x is a range of extent 100 distributed over the first dimension of p; y is a range of extent 200 distributed over the second dimension of p. Global subscripts associated with a range of extent N are always in the range 0, …, N − 1.

Finally, a and b are distributed arrays. Distributed arrays are characterized by double brackets. a is a 200 by 100, two-dimensional array with elements of type float, distributed blockwise over p. Its dimension ranges are x and y. b is a 100-element, one-dimensional array. Its dimension range is x. Implicitly, it is replicated over the second dimension of p, because it has no range distributed over this dimension.

The ranges of an array must be distributed over orthogonal dimensions of the process group over which the array is distributed (or they must be collapsed—see section 11).

In general the brackets in a distributed array constructor contain a process group and a list of ranges (the process group can be omitted, in which case it defaults to the active process group). The brackets in a distributed array type specifier contain a hash and zero or more commas separating empty slots—their number defines the rank of the array. The type of a distributed array element is a Java primitive type (for now).

Java-D provides array sections directly analogous to Fortran 90 array sections. The section subscripting operator uses double brackets:

  a [[50, 0 : 98 : 2]]
  b [[25]]

The first section has a scalar subscript and a triplet subscript. The expression represents a one-dimensional distributed array providing an alias for a subset of elements of a. The second section contains just element 25 of b, but the result is a rank-zero arrray, not a simple variable. Section subscripting always yields an array—never an array element.

Rank-0 arrays can be declared directly as follows

  int c [[]]  = new int [[p]] ;

This creates a new array with a single element replicated over p. The type specifier of a rank-0 distributed array is distinguished from a rank-1 distributed array by omission of the hash.

3 Access to elements of distributed arrays

Local subscripting uses single brackets (to distinguish it from section subscripting). The items in the brackets are local subscripts.

  a [i, j]
  b [i]

A local subscript is a new primitive type in Java-D. It is not an arithmetic type. It can only be created and used in a few restricted ways. The result of a local subscripting operation is a single array element which may appear in an expression or on the left hand side of an assigment.

A local subscript is associated with a particular parent range. A subscripts used in a local subscripting operation must be associated with the corresponding range of the distributed array (or a subrange of that range).

The two most common ways to define local subscripts are through the at construct or the where construct. These constructs are parametrized by range objects.

  at(x | 75)
    b [x] = 23 ;
  where(x)
    where(y)
      a [x, y] = 2 * b [x] + y ;

The at construct in the example specifies that the assignment in the body of the construct is executed only on processes that hold element 75 of x. The important point to note is that the range object can be used as a local subscript inside an at construct. We say that there is a type conversion from a range to a local subscript. The result of this conversion is only well-defined inside an at (or where) construct parametrised by the range in question. The net effect of the construct is to assign the vaule 23 to element 75 of b.

The where construct is a distributed loop. (It is unrelated to the WHERE statement of Fortran, which involves masking. The Java-D where is more analogous to a Fortran FORALL construct, but with an explicit localization of the loop iterations.) Its body is executed, logically in parallel, for every element of the range parametrizing the construct. The example illustrates a pair of nested where constructs. Array subscripting again exploits the conversion from a range to a local subscript (corresponding to the current iteration).

A second conversion is illustrated by the use of y on the right hand side: a range can be converted to a numeric value representing the current value of the global subscript. Again, the result of this conversion is only well defined inside a suitable at or where construct.

Invariably, if a range is used to parametrize an at or where, the only meaningful use of that range inside the body of the construct is through one of these conversions to a local or global subscript.

4 The active process group

The active process group is the set of processes sharing the current thread of control. In the simplest case this is a process array. The active process group can be set explicitly through the on construct, for example

  on(p)
    c [] = 34 ;

In the body of the construct the active process group is changed to the group p (recall that c was declared earlier as a rank-0 array distributed over p).

The where and at constructs defined in the previous section can only appear at a point of execution where range object parametrizing them is distributed over a dimension of the active process group. In fact the active process group is also modified inside the body of these constructs. It is reduced to a slice of the process array, restricted to a fixed coordinate value in the process dimension associated with the parametric range. We will return to this point in a section 7.

Constructs on, where and at are distributed constrol constructs.

5 Collective communication

Collective communications are movements of distributed arrays. They are static members of the Adlib class. The following fragment illustrates the use of one such member: shift.

  Procs2 p(2, 2) ;
  on(p) {
    Range x = new BlockRange(100, p.dim(0)) ;

    Range y = new BlockRange(200, p.dim(1)) ;
    int u [[#,]] = new int [[# x, y ]] ;
    // ... some code to initialise `u'
    int [[#,]] unx = new int [[# x, y ]], upx = new int [[# x, y ]],
               uny = new int [[# x, y ]], upy = new int [[# x, y ]] ;
    Adlib.shift(unx, u,  1, 0, CYCL) ;
    Adlib.shift(upx, u, -1, 0, CYCL) ;
    Adlib.shift(uny, u,  1, 1, CYCL) ;
    Adlib.shift(upy, u, -1, 1, CYCL) ;
    where(x)
      where(y)
        u [x, y] = 0.25 * (unx [x, y] + upx [x, y] +
                           uny [x, y] + upy [x, y]) ;
  }

The array arguments of shift must have the same type and have the same ranges (they must be aligned). The third argument is the shift amount, the fourth is a dimension selector, and the fifth is the mode of the shift—in this case cyclic shift is selected.

A more efficient version of this code, using ghost regions, will be given later. The Adlib class will provide an interface to all the collective communication

functions of the NPAC PCRC library.

6 Process dimensions

A rank-R process array has R associated process dimensions. A process dimension is a Range—a primitive range over which other ranges can be distributed. The global subscripts are in the range 0, …, P − 1 where P is the extent of the process dimension.

Because process dimensions are ranges, they can appear directly in array declarations and distributed control constructs.

  Procs1 p(4) ;
  on(p) {
    Range d = p.dim(0) ;
    int v [[#]] = new int [[# d]] ;
    where(d)
      v [d] = d ;
  }

The array v has a single integer element for every process in p. The where construct assigns the global subscript—in this case the local value of the process coordinate—to each element of v.

7 Local subscripts and subgroups

A local subscript logically defines a process dimension, a position within that dimension, and some offset in the local segment of the range. Local subscripts have type subscript. As explained above they are often created implicitly by conversion of ranges. Sometimes it is convenient to have an explicit expression for a local subscript. In fact we have seen this kind of expression in the argument of the at construct:

  subscript i = x | 75

is a local subscript in x with global subscript 75.

A subgroup is some slice of a process array, formed by restricting the process coordinates in one or more dimensions to single values. A subgroup is a Group.

Any subgroup has a parent process array and a dimension set which is some subset of the dimensions of the parent array. The restriction operation on a group takes a slice in a particular dimension. This restriction procedure is conveniently expressed in terms of a local subscript. Suppose i is a local subscript in a range distributed over process dimension d, and p is a group that has d as one of its dimensions. The expression

  p / i

represents a smaller group formed by restricting the process coordinate in d to that implied by i, and removing d from the dimension set. (By the nature of the definition of the / operator we can see that p / i / j is equivalent to p /

j / i.)

For example

  Procs2 p = new Procs2(3, 2) ;
  Range x = new BlockRange(100, p.dim(0)) ;
  Range y = new BlockRange(200, p.dim(1)) ;
  Group q = p / (x | 20) ;
  int d [[#]]  = new int [[q # y]] ;

The global subscript 20 maps to coordinate 0 of p.dim(0), so q is a one dimensional slice of p formed by fixing the first coordinate to 0. In HPF terms, d has an embedded alignment in the template spanned by x and y.

Besides their role in specifying this unusual kind of alignment, subgroups allow us to formally state the effects of the at and where constructs on the active process group. If the current active process group is p and i is some local subscript associated with range distributed over a dimension of p, then in

  at(i)
    S

the statement S executes in the context of an active process group p / i. If the current active process group is p and x is some range distributed over a dimension of p, then in

  where(x)
    S

the statement S executes in the context of an active process group p / x, assuming the usual conversion from a range to a local subscript.

8 Subranges

A subrange is a section of a range parametrized by a global subscript triplet, in the Fortran style. A subrange is a Range. The syntax for creation of subranges is

  x | 0 : 49

or

  x | 1 : 98 : 2

for a strided subrange. As in Fortran, an upper or lower bound may be omitted in which case it defaults to the bound of the parent range.

Subranges retain an alignment relation to their parent range. Local subscripts formed from a a subrange are valid local subscripts in the parent range. Note, however, that the global subscripts for a subrange are in the range 0, …, N − 1 where N is the extent of the subrange.

Arrays can be declared with subranges, for example

  int e [[#,]]  = new int [[p # (x | 0 : 50), (y | 1 : 198 : 2)]] ;

In HPF terms, e has a non-trivial linear alignment to the template spanned by x and y. By allowing subgroups and subranges to appear in array constructors we reproduce the two-level alignment model of HPF in full generality, at very little cost in terms of syntax extensions. The Java-D version is slightly less readable than the HPF version, but after all this is an advanced feature which is unlikely to be needed by the casual programmer.

Subranges can be used to parametrize where constructs

  Range z = x | 1 : 98 : 2 ;
  where(z)
    b [z] = z ;

Because a local subscript formed from a subrange is a valid local subscript in the parent range, z could be used to subscript b in the loop even though b was declared with range x. The alignment relation between x and z determines which element is selected.

Subranges are created implicitly when a section with triplet subscripts is created—the ranges of the section will be subranges of ranges of the parent array. In fact subranges can be used in place of triplet subscripts in array sections. Also, local subscripts can be used in place of integer scalar subscripts. If the ranges of a are x, y, z, … and n, l, u, s are integers, the section

  a [[n, l : u, l : u : s, ...]]

is equivalent to

  a [[(x | n), (y | l : u), (z | l : u : s), ...]]

Below we will refer to this form of section, with all subscripts expressed as local subscripts or ranges, as the canonical form.

9 Nested parallelism

Consider this code, which is supposed to implement a skewed shift of the data in a, putting the result in b:

  float a [[#,]] = new float [[# x, y ]] ;
  float b [[#,]] = new float [[# x, y ]] ;
  where(y)
    Adlib.shift(b [[:, y]], a [[:, y]], y, 0, CYCL) ;

The shift operation is applied in parallel to the rows of a and b, with a shift amount given by the global index of the parallel loop.

A priori, there is an ambiguity in the use of y as a section subscript. Recall that ranges, local subscripts and global subscripts are all valid as section subscripts. Is y to be used directly as a range, converted to a local subscript, or converted to a global subscript? The second option is chosen: if the parametric range of an at or where appears as a section subscript in the body of the construct, it is converted to a local subscript. (This is an isolated case. There are very few situations where this kind of ambiguity can occur.)

10 Usage rules

The usage rules for variables and distributed arrays are required to ensure that

• for ordinary variables, accesses are always local, and • for distributed arrays, all elements of a distributed array are available in

the active process group at the time a collective operation is performed on that array.

This section gives a formal definition of these rules. A programmer with a good intuitive understanding of the SPMD model will probably not need the formal statement given here, but it is provided for completeness.

First we formally define the phrase distributed over for an array or section. If an array constructor specifies a process group p, the constructed array is distributed over p. If an array constructor doesn’t specify a process group the constructed array is distributed over the active process group. For a section, assume the section is expressed in canonical form (see section 8), and the section subscripts include local subscripts i, j, ... (interspersed with some range subscripts, which can be ignored here). If the parent array is distributed over p, the section is distributed over

  p / i / j / ...

Now, for any ordinary variable (as opposed to a distributed array, which is a collection of variables) we define the home group as the group of processes contain a copy of the variable. In general this group contains multiple processes, because the variable may be stored in a replicated manner. For a variable that is not an array element the home group is the group that was active at the time the variable was created or declared. For an array element, suppose a is an array distributed over p, and i, j, ... are appropriate local subscripts, the home group of

  a [i, j, ...]

is

  p / i / j / ...

The usage rules for ordinary variables are now:

• the variable may only be accessed by value when the active process group is contained in the home group of the variable.

• the variable may only be assigned when the active process group is identical to the home group of the variable.

In other words, the variable can be read if the local process contains a copy of the variable. To write to a variable, we also require that the active process group— the group executing the write operation—includes the whole of the group over which the variable is replicated.

The rules for collective operations are slightly more complex. The essential idea is that an array can be updated by a collective operation if all its elements are contained in the active process group, and it can be accessed by value by a collective operation if all elements can be accessed by value.

More formally, an array is accessible if it is distributed over a group contained in the active process group. It is value-accessible if it is accessible or if the group, p, over which the array is distributed has the same parent process array as the active process group, and the dimension set of the intersection of p with the active process group contains all process dimensions over which the ranges of the array are distributed. (This is a complicated way of saying they p may have dimensions outside the active process group, but the array must be replicated over those dimensions.)

For example

  on(p) {
    float a [[#,]] = new float [[# x, y ]] ;
    float b [[#,]] = new float [[# x, z ]] ;
    float c [[#,]] = new float [[# z, y ]] ;
    where(x)
      where(y)
        a [x, y] = Adlib.dotProduct(b [[x, :]], c [[:, y]]) ;
  }

We assume x, y and z are orthogonal and their dimensions are dimensions of p (otherwise the declarations are illegal). At the point of assignment the active group is p / x / y. The section b [[x, :]] is distributed over p / x, which means it is not accessible at this point. However it is value-accessible because the intersection of p / x with the active process group is p / x / y. The dimension set of this intersection contains the set of dimensions over which the section is distributed, namely {z.dim()}.

The rules for accessibility in collective operations apply also to array constructors. An array must be accessible at the time it is created!

In some cases the compiler may be able to detect violation of usage rules automatically. This cannot be guaranteed however—in general, if a programmer writes an invalid program this will lead to a run-time error.

11 Collapsed ranges

A collapsed range is a sequential range, mapped entirely to the local process. A collapsed range is a Range.

The constructor for a collapsed range is illustrated by

  Range z = new Range(50) ;

This creates a collapsed range of extent 50. As a convenience, an integer value can stand for a collapsed range in an array constructor, so one can write simply

  float a [[#,]] = new float [[p # x, 20 ]] ;
  float b [[#,]] = new float [[# 50, 50 ]] ;

a is an array distributed over p with one distributed range and one collapsed range (by definition, a collapsed range is orthogonal to any other range). b is an array replicated over the active process group with two collapsed ranges. For most practical purposes b is equivalent to a two dimensional sequential array.

As a further convenience, to make the analogy with sequential arrays even stronger, it is allowed to use simple integer values as local subscripts for collapsed ranges. We emphasize that this is only allowed for collapsed ranges—it is a compile-time or run-time error to use an integer as a local subscript in a range that is not collapsed. With the declarations above the following examples are now legal

  on(p)
    where(x)
      a [x, 10] = x ;
  b [25, 25] = 13.0 ;

To avoid ambiguity, note that if a range is used in a local subscripting operation, it is always converted to a local subscript, never to an integer global subscript. If we wanted to assign the diagonal of the array a we would need an explicit conversion

  where(x)
    a [x, (int) x] = x ;

12 Ghost regions

Ghost regions require some extension to the framework discussed above. A new constructor for BlockRange allows specification of ghost widths. Shift operators >> and << applicable to ranges return subscripts a specified number of places to the right or left of the current position (the results are only defined inside an at or where construct parametrized by the range involve). A collective operation writeHalo updates the ghost regions of a distribute array, copying values from the physical segments of neighbouring processes.

  Procs2 p(2, 2) ;
  on(p) {
    Range x = new BlockRange(100, p.dim(0), 1) ;  // ghost width 1
    Range y = new BlockRange(200, p.dim(1), 1) ;  // ghost width 1
    int u [[#,]] = new int [[# x, y ]] ;
    // ... some code to initialise `u'
    Adlib.writeHalo(u) ;
    int v [[#,]] = new int [[# x, y ]] ;

    where(x)
      where(y)
        v [x, y] = 0.25 * (u [x << 1, y] + u [x >> 1, y] +
                           u [x, y << 1] + u [x, y >> 1]) ;
    Adlib.copy(u, v) ;
  }

This version only involves a single array temporary and a single array-copy operation (done here using the library function copy). By using suitable strided subranges to parametrize the loops this could be converted to a red-black form requiring no array temporaries, something like

    where(x)
      where(y | (x + parity) % 2 : : 2)
        u [x, y] = 0.25 * (u [x << 1, y] + u [x >> 1, y] +
                           u [x, y << 1] + u [x, y >> 1]) ;

It is a compile-time or run-time error to use >> or << in ways that would imply access to off-processor data.

For the purposes of this example we have assumed that writeHalo implements cyclic boundary conditions.

13 Cyclic ranges

CyclicRange is a subclass of Range that represents a cyclically distributed range. Ghost regions are not supported for cyclic ranges. Block cyclic distributions can be handled by distributing a range blockwise over a cyclic range:

  Range k = CyclicRange(20, p.dim(0)) ;
  Range x = BlockRange(100, k) ;

14 Global arrays

The language features described above support data parallel programming based on a collective communication library. However the model trivally allows a lower level of SPMD programming through the idiom illustrated in section 6.

Eventually we can add GAs style non-local get and put members to the distributed arrays (and a handful of other GAs-style synchronization primitives) to support task parallel programming in this framework. Task parallel phases can be freely alternated with SPMD data parallel phases.

References

[1] Bryan Carpenter, “Adlib Language Reference”, URL: http://www.npac.syr.edu/users/dbc/Adlib [2] Special edition of Concurrency, Practise and Experience,

[3] Bryan Carpenter, Yuh-Jye Chang, Geoffrey Fox, Donald Leskiw, Xiaoming Li, “Experiments with HPJava”