next up previous
Next: Translation Up: Case Study 1: Matrix Previous: Case Study 1: Matrix

HPJava Language Featues

Figure 1: Matrix Multiplication in HPJava.
Procs2 p = new Procs2(P, P) ;
on(p) {
  Range x = new BlockRange(N, p.dim(0)) ;
  Range y = new BlockRange(N, p.dim(1)) ;

  double [[-,-]] c = new double [[x, y]] on p ; 

  double [[-,*]] a = new double [[x, N]] on p ; 
  double [[*,-]] b = new double [[N, y]] on p ; 

  ... initialize `a', `b'

  overall(i = x for :)
    overall(j = y for :) {

      double sum = 0 ;
      for(int k = 0 ; k < N ; k++)
        sum += a [i, k] * b [k, j] ;

      c [i, j] = sum ;
    }
}

Figure 1 is a basic HPJava program for a matrix multiplication. It includes much of the HPJava special syntax, so we will take the opportunity to briefly review the featues of the HPJava language. The program starts by creating an instance p of the class Procs2. This is a subclass of the special base class Group, and describes 2-dimensional grids of processes. When the instance of Procs2 is created, $\mbox{\tt P} \times \mbox{\tt P}$ processes are selected from the set of processes in which the SPMD program is executing, and labelled as a grid.

The Group class, representing an arbitrary HPJava process group, and closely analogous to an MPI group, has a special status in the HPJava language. For example the group object p can parametrize an on(p) construct. The on construct limits control to processes in its parameter group. The code in the on construct is only executed by processes that belong to p. The on construct fixes p as the active process group within its body.

The Range class describes a distributed index range. There are subclasses describing index ranges with different properties. In this example, we use the BlockRange class, describing block-distributed indexes. The first argument of the constructor is the global size of the range; the second argument is a process dimension--the dimension over which the range is distributed. Thus, ranges x and y are distributed over the first dimension (i.e. p.dim(0)) and second dimension (i.e. p.dim(1)) of p, and both have N elements.

The most important feature HPJava adds to Java is the distributed array. A distributed array is a collective object shared by a number of processes. Like an ordinary array, a distributed array has some index space and stores a collection of elements of fixed type. Unlike an ordinary array, the index space and associated elements are scattered across the processes that share the array. There are some similarities and differences between HPJava distributed arrays and the ordinary Java arrays. Aside from the way that elements of a distributed array are distributed, the distributed array of HPJava is a true multi-dimensional array like that of Fortran. Like in Fortran, one can form a regular section of an array. These features of Fortran arrays have adapted and evolved to support scientific and parallel algorithms.

With a process group and a suitable set of ranges, we can declare distributed arrays. The type signature of a distributed array is clearly told by double brackets. In the type signature of a distributed array, each slot holding a hypen, -, stands for a distributed dimension, and a astrisk, *, a sequential dimension. The array c is distributed in both its dimensions. Besides, Arrays a and b are also distributed arrays, but now each of them has one distributed dimension and one sequential dimension.

The overall construct is another control construct of HPJava. It represents a distributed parallel loop, sharing some characteristics of the forall construct of HPF. The symbol i scoped by the overall construct is called a distributed index. Its value is a location, rather an abstract element of a distributed range than an integer value. The indexes iterate over all locations. It is important to note that (with a few special exceptions) the subscript of a distributed array must be a distributed index, and the location should be an element of the range associated with the array dimension. This unusual restriction is an important feature of the model, ensuring that referenced array elements are locally held.

Figure 2: General matrix multiplication.
void matmul(double [[-,-]] c, 
            double [[-,-]] a, double [[-,-]] b) {

  Group p = c.grp() ;

  Range x = c.rng(0) ;
  Range y = c.rng(1) ;

  int N = a.rng(1).size() ;

  double [[-,*]] ta = new double [[x, N]] on p ;
  double [[*,-]] tb = new double [[N, y]] on p ;

  Adlib.remap(ta, a) ;
  Adlib.remap(tb, b) ;

  on(p)
    overall(i = x for :)
      overall(j = y for :) {

        double sum = 0 ;
        for(int k = 0 ; k < N ; k++)
          sum += ta [i, k] * tb [k, j] ;

        c [i, j] = sum ;
      }
}

Figure 1 doesn't have any run-time communications because of the special choice of alignment relation between arrays. All arguments for the inner most scalar product are already in place for the computation. We can make a completely general matrix multiplication method by taking arguments with arbitrary distribution, and remapping the input arrays to have the correct alignment relation with the output array. Figure 2 shows the method. The method has two temporary arrays ta, tb with the desired distribution format. This is determined from c by using DAD inquiry functions grp() and rng() to fetch the distribution group and index ranges of a distributed array. Adlib.remap() does the actual communication to remap.

This implementation has some performance issues associated with its memory usage. These issues can be patched up--see [3] for more details. Meanwhile the simple version given here encapsulates some interesting principles of library construction with HPJava--in particular how arrays can be created and manipulated, even though the distribution formats are only determined at run-time.


next up previous
Next: Translation Up: Case Study 1: Matrix Previous: Case Study 1: Matrix
Bryan Carpenter 2004-04-24