next up previous
Next: Miscellaneous language issues Up: Translation Schemes for the Previous: Introduction


HPJava--an HPspmd language

HPJava extends its base language, Java, by adding some predefined classes and some additional syntax for dealing with distributed arrays. We aim to provide a flexible hybrid of the data parallel and low-level SPMD paradigms. To this end HPF-like distributed arrays appear as language primitives. The distribution strategies allowed for these arrays closely follow the strategies supported in HPF--any dimension of an array can independently be given blockwise, cyclic, or other distribution format2, array dimensions can have strided alignments to dimensions other arrays, arrays as a whole can be replicated over axes of processor arrangements, and so on.

A design decision is made that all access to non-local array elements should go through explicit calls to library functions. These library calls must be placed in the source HPJava program by the programmer. This requirement may be surprising to people expecting to program in high-level parallel languages like HPF, but it should not seem particularly unnatural to programmers presently accustomed to writing parallel programs using MPI or other SPMD libraries. The exact nature of the communication library used is not part of the HPJava language design, per se. An appropriate communication library might perform collective operations on whole distributed arrays (as illustrated in the following examples), or it might provide some kind of get and put functions for access to remote blocks of a distributed array, similar to the functions provided in the Global Array Toolkit [13], for example.

A subscripting syntax can be used to directly access local elements of distributed arrays. A well-defined set of rules--automatically checked by the translator--ensures that references to these elements can only be made on processors that hold copies of the elements concerned. Alternatively one can access local elements of a distributed array indirectly, by first extracting the locally held block of elements, then subscripting this block as a local sequential array.

To facilitate the general scheme, the language adds three distributed control constructs to the base language. These play a role something like the ON HOME directives of HPF 2.0 and earlier data parallel languages [8]. One of the special control constructs--a distributed parallel loop--facilitates traversal of locally held elements of distributed arrays.

Mapping of distributed arrays in HPJava is described in terms of a two special classes: Group and Range. Process group objects generalize the processor arrangements of HPF, and distributed range objects are used in place HPF templates. A distributed range is comparable with a single dimension of an HPF template. The changes relative to HPF (with its processor arrangements and multi-dimensional templates) are best be regarded as a modest change of parametrization only: the set of mappings that can be represented is unchanged.

Figure 1: A parallel matrix addition.
\begin{figure*}\small\begin{verbatim}Procs2 p = new Procs2(P, P) ;
on(p) {
...
...or :)
c [i, j] = a [i, j] + b [i, j] ;
}\end{verbatim}\normalsize\end{figure*}

Figure 1 is a simple example of an HPJava program. It illustrates creation of distributed arrays, and access to their elements. The class Procs2 is a standard library class derived from the special base class Group, and representing a two-dimensional grid of processes. The distributed range class BlockRange is a library class derived from the special class Range; it denotes a range of subscripts distributed with BLOCK distribution format. Process dimensions associated with a grid are returned by the dim() inquiry. The on(p) construct is a new control construct specifying that the enclosed actions are performed only by processes in group p.

The variables a, b and c are all distributed array objects. The type signature of an $r$-dimensional distributed array involves double brackets surrounding $r$ comma-separated slots. The constructors specify that these all have ranges x and y--they are all M by N arrays, block-distributed over p.

A second new control construct, overall, implements a distributed parallel loop. The symbols i and j scoped by these constructs are called distributed indexes. The indexes iterate over all locations (selected here by the degenerate interval ``:'') of ranges x and y.

In HPJava, with a couple of exceptions noted below, the subscripts in element references must be distributed indexes. The locations associated with these indexes must be in the range associated with the array dimension. This restriction is a principal means of ensuring that referenced array elements are held locally.

Figure 2: Red-black iteration.
\begin{figure}\par\small\begin{verbatim}Procs2 p = new Procs2(P, P) ;
on(p) ...
...+
u [i, j - 1] + u [i, j + 1]) ;
}
}\end{verbatim}\normalsize\par\end{figure}

This general policy is relaxed slightly to simplify coding of stencil updates. A subscript can be a shifted index. Usually this is only legal if the subscripted array is declared with suitable ghost regions [7]. Figure 2 illustrates the use of the standard library class ExtBlockRange to create arrays with ghost extensions (in this case, extensions of width 1 on either side of the locally held ``physical'' segment). A function, writeHalo, from the communication library Adlib updates the ghost region. If i is a distribute index, the expression i` (read ``i-primed'') yields the integer global loop index.

Distributed arrays can be defined with some sequential dimensions. The sequential attribute of an array dimension is flagged by an asterisk in the type signature. As illustrated in Figure 3, element reference subscripts in sequential dimensions can be ordinary integer expressions.

Figure 3: A pipelined matrix multiplication program.
\begin{figure}\small\begin{verbatim}Procs1 p = new Procs1(P) ;
on(p) {
Rang...
...tmp, b, 1, 1) ;
Adlib.copy(b, tmp) ;
}
}\end{verbatim}\normalsize\end{figure}

The last major component of the basic HPJava syntax is support for Fortran-like array sections. An array section expression has a similar syntax to a distributed array element reference, but uses double brackets. It yields a new array contains a subset of the elements of the parent array. Those elements can subsequently be accessed either through the parent array or through the array section--HPJava sections behave something like array pointers in Fortran, which can reference an arbitrary regular sections of a target array. As in Fortran, subscripts in section expressions can be index triplets. The language also has built-in ideas of subranges and restricted groups. These can be used in array constructors on the same footing as the ranges and grids introduced earlier, and they enable HPJava arrays to reproduce any mapping allowed by the ALIGN directive of HPF.

The examples here have covered the basic syntax of HPJava. The language itself is relatively simple. Complexities associated with varied and irregular patterns of communication would be dealt with in libraries, which can implement many richer operations than the writeHalo and cshift functions of the examples.

The examples given so far look very much like HPF data-parallel examples, written in a different syntax. We will give one final example to emphasize the point that the HPspmd model is not the HPF model. If we execute the following HPJava program

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{verbatim}Proc...
...) +
'', '' + e.crd() + '')'') ;
}\end{verbatim}\end{minipage}\end{displaymath}

we could see output like:

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{verbatim}My c...
...e (1, 1)
My coordinates are (0, 1)\end{verbatim}\end{minipage}\end{displaymath}

There are 6 messages. Because the 6 processes are running concurrently in 6 JVMs, the order in which the messages appear is unpredictable. An HPJava program is a MIMD program, and any appearance of collective behavior in previous examples was the result of a particular programming style and a good library of collective communication primitives. In general an HPJava program can freely exploit the weakly coupled nature of the process cluster, often allowing more efficient algorithms to be coded.


next up previous
Next: Miscellaneous language issues Up: Translation Schemes for the Previous: Introduction
Bryan Carpenter 2002-07-12