Parallel Programming

The previous section gave a simple example of how to create a distributed array. How do we use this kind of array? Figure 2.4 gives an example--parallel addition of two matrices.

Figure 2.4: A parallel matrix addition.

The overall construct is the second special control construct of HPJava. It implements a parallel loop, sharing a heritage with the forall construct of HPF. The colon in the overall headers of the example is shorthand for an index triplet^2.4. In general a triplet can include a lower bound, an upper bound, and a step, as follows:

    overall(i = x for l : u : s)

In general $l$, $u$ and $s$ can be any integer expressions. The third member of the triplet (the step) is optional. The default step is 1, and most often we see something like

    overall(i = x for l : u)

Finally, either or both of the expressions $l$ and $u$ can be omitted. The lower bound defaults to 0 and the upper bound defaults to $N - 1$, where $N$ is the extent of the range appearing before the for keyword. So in the original example the line

    overall(i = x for :)

means ``repeat for all elements, $i$, of the range $x$'', and is equivalent to

    overall(i = x for 0 : x.size() - 1 : 1)

The size member of Range returns the extent of the range.

Figure 2.5: A parallel stencil update program.

For readers familiar with the forall construct of HPF (or Fortran 95) the only unexpected part of the overall syntax is the reference to a range object in front of the triplet. The significance of this will be discussed at length in the next section. Meanwhile we give another example of a parallel program. Figure 2.5 is a simple example of a ``stencil update''. Each interior element of array a is supposed to be replaced by the average of the values of its neighbours:

$$a [i, j] \,\, \leftarrow \,\, (a [i - 1, j] + a [i + 1, j] + a [i, j - 1] + a [i, j + 1]) / 4$$

The shift operation is not a new feature of the HPJava language, as such. Instead it is a member of a particular library called Adlib. This is a library of collective operations on distributed arrays ^2.5. The function shift is overloaded to apply to various kinds of array. In this example we are using the instance applicable to two dimensional arrays with float elements:

    void shift(float [[,]] destination, float [[,]] source,
               int shiftAmount, int dimension) ;

The array arguments should have the same shape and distribution format. The values in the source array are copied to the destination array, shifted by shiftAmount in the dimension'th array dimension. Edge values from source that have no target in destination are discarded; edge elements of destination that are not overwritten by elements from source are unchanged from their input value.

In the example program, arrays of North, South, East and West neighbours are created using shift, then they are averaged in overall loops. An obvious question is: why go to the trouble of setting up these arrays? Surely it would be easier to write directly:

    overall(i = x for 1 : N - 2)
      overall(j = y for 1 : N - 2)
        a [i, j] = 0.25 * (a [i - 1, j] + a [i + 1, j] +
                           a [i, j - 1] + a [i, j + 1]) ;

The answer relates to the nature of the symbols i and j. No declaration was given for these names, but it would be reasonable to assume that they stand for integer values.

They don't.