HPJava simple example

<h1>A Simple Example - Matrix multiplication</h1>

Like it's namesake, HPF (High Performance Fortran), HPJava provides
some special syntax to describe logical groupings of the processes
executing a program, and for declaring and manipulating
<i>distributed arrays</i>, whose elements are distributed over groups
of processes.

<p>

Here is an example of an HPJava program for multiplying together
two matrices, implemented as distributed arrays:
<font color=Blue>
<pre>
  Procs2 p = new Procs2(P, P) ;
  on(p) {
    Range x = new BlockRange(N, p.dim(0)) ;
    Range y = new BlockRange(N, p.dim(1)) ;

    float [[,]]  c = new float [[x, y]] ;

    float [[,*]] a = new float [[x, N]] ;
    float [[*,]] b = new float [[N, y]] ;

    ... initialize `a', `b'

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

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

        c [i, j] = sum ;
      }
  }
</pre>
</font>
A process group object <tt>p</tt> is created, representing a
2-dimensional, <tt>P</tt> by <tt>P</tt> grid of processes.  Implicitly
these P<sup>2</sup> processes are some subset of the processes in
which the program was started.  The remainder of the program is
executed only by processes in the subset <tt>p</tt>.  This is specified
through the <tt>on(p)</tt> construct.

<p>

Distributed arrays <tt>a</tt>, <tt>b</tt> and <tt>c</tt> are declared
through special syntax, using double brackets.  This distinguishes them
from the sequential arrays of ordinary Java.  HPJava is a superset of
ordinary Java, so ordinary Java arrays are also available in HPJava.
But there are several important differences between standard Java
arrays and the distributed arrays conventionally used in data-parallel
programming.  Rather than try to force two incompatible models of an
array into the same mold, HPJava lives with the distinction.  It keeps
the idea of a distributed array strictly separate from the standard
Java idea of a sequential array.

<p>

Whereas all the elements of an ordinary Java array reside in the memory
of the process that creates the array, the elements of a
distributed array are divided across the memories of the processes
that collectively create the array.
Distributed arrays may be multidimensional.  In general their shape and
distribution is specified in the constructor using a list of
<i>distributed range</i> objects.  These belong to the class
<tt>Range</tt>.  The 2-dimensional array <tt>c</tt> has ranges <tt>x</tt> and
<tt>y</tt>.  Other languages (including Ada) provide special syntax for
describing ranges of integers, to be used in declaring arrays
and parametrizing <tt>for</tt> loops.  HPJava elevates its range
entities to full object status, and endows them with a <i>distribution
format</i>.  The range <tt>x</tt> represents a mapping of the integer
interval <tt>0 ... N - 1</tt> into the first dimension of the process
grid <tt>p</tt> (represented by the expression <tt>p.dim(0)</tt>).  The
range <tt>y</tt> is similar, but the interval is distributed over the
second dimension of <tt>p</tt>.  The choice of subclass
<tt>BlockRange</tt> for these ranges implies that the intervals are
distributed over the process grid dimensions using <i>simple block</i>
distribution format.  More complex distributions formats are supported
through different subclasses of <tt>Range</tt>.  In general a
multidimensional array can have ranges with an arbitrary mix of these
distribution formats.

<p>
<img src="matc.gif">
<p>

The figure shows the distribution of the elements of <tt>c</tt> over
the 4 processors of <tt>p</tt> if <tt>P = 2</tt> and <tt>N = 5</tt>.

<p>

The arrays <tt>a</tt> and <tt>b</tt> are the same <i>shape</i> as
<tt>c</tt> -- they are <tt>N</tt> by <tt>N</tt> matrices -- but there
distribution patterns are different.  The second dimension of
<tt>a</tt> and the first dimension of <tt>b</tt> are <i>sequential</i>,
or <i>collapsed</i>, dimensions.  (Actually a sequential array dimension
is just a dimension parametrized by a particular subclass of
<tt>Range</tt> called <tt>CollapsedRange</tt>, but this is a
sufficiently simple and important case to warrant special treatment by
the compiler.)  The <i>type signature</i> of an array with a sequential
dimension includes an asterisk in the associated slot, and a simple
integer extent is used in the corresponding slot of the constructor.
The layout of the elements of <tt>a</tt> looks like:

<p>
<img src="mata.gif">
<p>

The first dimension of <tt>a</tt> is distributed over the ``vertical''
process dimension.  But because the second dimension of <tt>a</tt> is
sequential every processor contains complete rows of the matrix.
Notice that each column of processes contains a replica of the whole
array.  Because <tt>a</tt> has no dimension distributed over the second
dimension of <tt>p</tt>, the whole array is <i>replicated</i> across
that process dimension.

<p>

The distribution of <tt>b</tt> is complimentary:

<p>
<img src="matb.gif">
<p>

Processes contain whole columns of the matrix, and every row of processes
contains a replica of the complete array.  The code that initializes
<tt>a</tt> and <tt>b</tt> should respect this replication pattern, and
enter identical values in each copy of the elements of the arrays.
In a later section we will illustrate how this requirement may be met.

<p>

Because we have carefully selected the distribution patterns for the
matrices, the parallel implementation of the matrix multiplication is
very straightforward.  All the operands for the computation of
<tt>c[0,0]</tt>, say, are resident on the processor that holds
that element, so no communication is needed to compute that element
(or any other element).

<p>

The <i>overall</i> construct is a loop
parametrized by a range object.  Because a <tt>Range</tt> generally
represents a <i>distributed</i> range of integers, an <tt>overall</tt>
is generally a <i>parallel, distributed loop</i>.  In the specific example
illustrated above the body of the construct
<font color=Blue>
<pre> 
    overall(i = x) {
      ...
    }
</pre> 
</font>
is executed 3 times by processes in the first row of processes and
twice by processes in the second row.  In each iteration the symbol
<tt>i</tt> takes on a value that represents a particular, locally
held ``element'' of the range <tt>x</tt>.
Note the symbol <tt>i</tt> is not an integer.  Instead elements of
ranges are special entities called <i>locations</i>.  Locations can be
used as subscripts to distributed arrays - in fact subscripts in
distributed dimensions of arrays are typically <i>required</i> to be
locations in appropriate ranges.  Subscripting operations on
distributed arrays are restricted by the language in a way that ensures
that all direct array accesses involve locally held elements.

<p>

The implementation of the matrix multiplication should now be
reasonably transparent.  A pair of nested parallel loops iterate over
the elements of <tt>c</tt>.  An inner sequential loop accumulates the
inner product of the relevant row of <tt>a</tt> with the relevant
column of <tt>b</tt>.  Notice that, because the second dimension of
<tt>a</tt> and the first dimension of <tt>b</tt> were explicitly declared
to be sequential, the compiler allows them to be subscripted
unrestrictedly with integer expressions.  The variable <tt>sum</tt> is
simply a local scalar variable.


<p>

<b>Next:</b>
<a href="groups.html">Process groups</a>


