Parallel Programming

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

Figure 2.5: A parallel matrix addition.

$$\begin{minipage}[t]{\linewidth}\small\begin{verbatim}Proc... ...c [i, j] = a [i, j] + b [i, j] ; }\end{verbatim}\end{minipage}$$

The overall construct is the second special control construct of HPJava. It implements a distributed, parallel loop. So the statement

$$\begin{minipage}[t]{\linewidth}\small\begin{verbatim}overall(i = x for :) ...\end{verbatim}\end{minipage}$$

can be read as ``for all elements, $i$, of the distributed range $x$, do ...''.

The colon in the overall headers of the example is shorthand for an index triplet (see section 1.2.4) so the forms

$$\begin{minipage}[t]{\linewidth}\small\begin{verbatim}overall(i = x for l : u : s) ...\end{verbatim}\end{minipage}$$

and

$$\begin{minipage}[t]{\linewidth}\small\begin{verbatim}overall(i = x for l : u) ...\end{verbatim}\end{minipage}$$

are also allowed. In the original form the lower bound defaults to 0 and the upper bound defaults to $N - 1$, where $N$ is the extent of the range before the for keyword. In other words it is equivalent to

$$\begin{minipage}[t]{\linewidth}\small\begin{verbatim}overall(i = x for 0 : x.size() - 1 : 1)\end{verbatim}\end{minipage}$$

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

Figure 2.6: A parallel stencil update program.

$$\begin{minipage}[t]{\linewidth}\small\begin{verbatim}Proc... ... [i, j] + e [i, j] + w [i, j]) ; }\end{verbatim}\end{minipage}$$

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 become clearer in the next section. Meanwhile we give another example of a parallel program. Figure 2.6 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 in Figure 2.6 is not a new feature of the HPJava language. Instead it is a member of a particular library called Adlib. Adlib 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 version applicable to two dimensional distributed arrays with float elements:

$$\begin{minipage}[t]{\linewidth}\small\begin{verbatim}void... ... int shiftAmount, int dimension) ;\end{verbatim}\end{minipage}$$

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. See section 6.1 for more information on the Adlib shift() method. To use the methods of the hpjava.adlib.Adlib class in the manner illustrated here there should be a suitable import declaration at the start of the program.

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:

$$\begin{minipage}[t]{\linewidth}\small\begin{verbatim}over... ...] + a [i, j - 1] + a [i, j + 1]) ;\end{verbatim}\end{minipage}$$

The answer to this question relates to the nature of the symbols i and j. No declaration was given for these names, but it would be reasonable to guess that they stand for integer values. In fact they don't.