next up previous
Next: Run-time Communication Library Up: The HPJava Language Previous: HPspmd Programming Model


Features

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 features 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 labeled 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 parameterize 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 multiarray. There are two kinds of multiarray in HPJava: distributed arrays and sequential multidimensional arrays3. A distributed array is a collective array, 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. A sequential multi-dimensional array is similar to an ordinary Fortran array. Like in Fortran (but unlike ordinary Java arrays) one can form a regular section of a multiarray.

With a process group and a suitable set of ranges, we can declare distributed arrays. The type signature of a distributed array is clearly distinguished by double brackets. In the type signature of a distributed array each slot holding a hyphen, -, stands for a distributed dimension, while an asterisk, *, stands for a sequential dimension. The array c is distributed in both its dimensions. 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 with the forall construct of HPF. The symbol i scoped by the overall construct is called a distributed index. Its value is a location--an abstract element of a distributed range. In general 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 does not have any run-time communications because of the special choice of alignment relation between arrays. All arguments for the innermost 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 in relation to the output array. Figure 2 shows the method. It 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. Adlib [9], described in section 3.3, is a communication library available for use with HPJava.

This simplified example 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.

We will give another old favorite program, red-black relaxation. It remains interesting since it is a kernel in some practical solvers (for example we have an HPJava version of a multigrid solver in which relaxation is a dominantly time-consuming part). Also it conveniently exemplifies a family of similar, local, grid-based algorithms and simulations.

Figure 3: Red-black iteration.
                     Procs2 p = new Procs2(2, 3) ;
                     on(p) {
                       Range x = new ExtBlockRange(N, p.dim(0)) ;
                       Range y = new ExtBlockRange(N, p.dim(1)) ;

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

                       ... initialization for `a'

                       for(int iter=0; iter<count; iter++){
                         Adlib.writeHalo(a, wlo, whi);
                         overall(i=x for 1 : N - 2) 
                           overall(j=y for 1+(i`+iter)%2 : N-2 : 2) {
                             a[i,j] = 0.25F * (a [i-1,j] + a [i+1,j] +
                                               a [i,j-1] + a [i,j+1]);
                           }
                       }
                     }

We can see an HPJava version of red-black relaxation of the two dimensional Laplace equation in Figure 3. Here we use a different class of distributed range. The class ExtBlockRange adds ghost-regions [12] to distributed arrays that use them. A library function called Adlib.writeHalo() updates the cached values in the ghost regions with proper element values from neighboring processes.

There are a few additional pieces of syntax here. The range of iteration of the overall construct can be restricted by adding a general triplet after the for keyword. The i` is read ``i-primed'', and yields the integer global index value for the distributed loop (i itself does not have a numeric value--it is a symbolic subscript). Finally, if the array ranges have ghost regions, the general policy that an array subscript must be a simple distributed index is relaxed slightly--a subscript can be a shifted index, as here.

Figure 4: HPJava Architecture.
\includegraphics[width=3.5in]{Figures/hpjava-hierarchy}


next up previous
Next: Run-time Communication Library Up: The HPJava Language Previous: HPspmd Programming Model
Bryan Carpenter 2004-04-24