next up previous contents index
Next: A Complete Example Up: Processes and Distributed Arrays Previous: Parallel Programming   Contents   Index


Locations

An HPJava range object can be thought of as a set of abstract locations. In our earlier example,

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{verbatim}Proc...
... BlockRange(N, p.dim(1)) ;...
}\end{verbatim}\end{minipage}\end{displaymath}

the range x, for example, contains N locations. In an overall construct such as

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{verbatim}overall(i = x for 1 : N - 2) {
...
}\end{verbatim}\end{minipage}\end{displaymath}

the symbol i is called a distributed index. The value associated with a distributed index is considered to be a location, not an integer value.

With a few exceptions that will be discussed later, the subscript of a distributed array must be a distributed index, and the location must be an element of the range associated with the array dimension. This is why we introduced the temporary arrays of neighbours in the stencil update example of the previous section. Arbitrary expressions are not usually legal subscripts for a distributed array. If we want to combine elements of arrays that are not precisely aligned, we first have to use a library function such as shift to align them.

Figure 2.7 is an attempt to visualize the mapping of locations from x and y. We will write the locations of x as x[0], x[1], ..., x[N - 1]. Each location is mapped to a particular group of processes. Location x[1] is mapped to the three processes with coordinates $(0,0)$, $(0,1)$ and $(0,2)$. Location y[4] is mapped to the two processes with coordinates $(0,1)$ and $(1,1)$.

Figure 2.7: Mapping of x and y locations to the grid p.
\includegraphics{locations.eps}

There is one other construct in HPJava besides overall that defines a distributed index. This is the relatively simple at construct. Suppose we want to update or access a single element of a distributed array (rather than accessing a whole set of of elements in parallel). it is not allowed to write simply

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{verbatim}floa...
...]] ;
...
a [1, 4] = 73 ; // ERROR\end{verbatim}\end{minipage}\end{displaymath}

because 1 and 4 are not distributed indices, and therefore not legal subscripts. We can write:

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{verbatim}floa...
...1])
at(j = y [4])
a [i, j] = 73 ;\end{verbatim}\end{minipage}\end{displaymath}

The symbols i and j, scoped within the construct bodies, are distributed indices.

The effect of the at construct should be fairly clear. It is similar to the on construct. It restricts control to processes in the set that hold the specified location. Referring back to Figure 2.7, the outer

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{verbatim}at(i = x [1])\end{verbatim}\end{minipage}\end{displaymath}

construct limits execution of its body to processes with coordinates $(0,0)$, $(0,1)$ and $(0,2)$. The inner

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{verbatim}at(j = y [4])\end{verbatim}\end{minipage}\end{displaymath}

then restricts execution down to just process $(0,1)$. This is exactly the process that owns element a[1,4].

So we see that the odd-looking restriction that subscripts must be distributed indices helps ensure that processes only manipulate array elements stored locally. If a process has to access non-local data, some explicit library call is needed to fetch it, like the Adlib.shift() operations used in the previous section.

We can now formally define the meaning of the overall construct in terms of the simpler at construct. If s is greater than zero, the construct

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

is equivalent in behavior to

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{verbatim}for(...
... ; n += s)
at(i = x [n]) {
...
}\end{verbatim}\end{minipage}\end{displaymath}

If s is less than zero, it is equivalent to

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{verbatim}for(...
... ; n += s)
at(i = x [n]) {
...
}\end{verbatim}\end{minipage}\end{displaymath}

The bodies of the at constructs are skipped for values of n that don't correspond to locally held elements. In practice of course the HPJava compiler translates the overall construct more efficiently than this definition suggests.

The at construct completes the contingent of special control constructs in HPJava. We sometimes refer to the three constructs on, at and overall as distributed control constructs.

The backquote symbol, `, can be used as a postfix operator on a distributed index, thus:

\begin{displaymath}
\begin{minipage}[t]{\linewidth}\small\begin{verbatim}i\lq \end{verbatim}\end{minipage}\end{displaymath}

This expression is read ``i-primed'', and evaluates to the integer global index value. In the operational definition of the overall given above, this is the value called n.

We now know enough about HPJava to write some more complete examples.


next up previous contents index
Next: A Complete Example Up: Processes and Distributed Arrays Previous: Parallel Programming   Contents   Index
Bryan Carpenter 2003-04-15