next up previous contents
Next: Recommendations for updating variables Up: Some rules and definitions Previous: Rules for distributed array   Contents

Rules for accessing array elements

First we summarize rules for distributed array element references given in section 2.4. If $a$ is a distributed array, then in the element reference

\begin{displaymath}
a \mbox{\tt [}e_0\mbox{\tt , }\ldots
\mbox{\tt , }e_r\mbox{\tt , }\ldots
\mbox{\tt ]}
\end{displaymath}

the expression $e_r$ may an integer expression (allowed only if the corresponding dimension of $a$ has the sequential attribute), or a bound location. If it is an integer, it must lie in the interval $0, \ldots , a\mbox{\tt .rng(}r\mbox{\tt ).size()} - 1$. If it is a location, it must be an element of the range $a$.rng($r$)5.3.

The rules on subscripts given in the previous paragraph go a long way towards ensuring a crucial requirement of HPJava, namely that a process may only access locally held array elements. Unfortunately there are still odd cases--typically involving array sections--where those rules are insufficient. Consider this pathological example

  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 [[,]] a = new float [[x, y]] ;

    float [[]] b = a [[0, :]] ;

    at(i = x [N - 1])
      overall(j = y for :)
        b [j] = j` ;               // error!
  }
The subscripts on the element reference b [j] are legal--j is certainly a location in b.rng(0) (which is equal to y). But, as illustrated in Figure 5.1, the section b is localized to p / x [0]--the top row of processes in the figure--whereas the at construct specifies that the element assignments are performed in the group p / x [N - 1]--the bottom row of processes.

Figure 5.1: Access error discussed in text. Section b is shaded area at top.
\begin{figure*}\centerline{\psfig{figure=accessError.eps,width=4.5in}}\end{figure*}

This kind of error can be excluded by the following rule. Suppose the distribution group of $a$ is $p$, and the list of subscripts $e_0, \ldots, e_r, \ldots$ in the element reference

\begin{displaymath}
a \mbox{\tt [}e_0\mbox{\tt , }\ldots
\mbox{\tt , }e_r\mbox{\tt , }\ldots
\mbox{\tt ]}
\end{displaymath}

includes locations {i, j, ...}. The home group of the array element is defined to be
    p / i / j / ...
(If the array has a replicated distribution this group may contain several processes; otherwise it contains a single process.) The general rule about accessing array elements can be stated formally as follows
An array element can only be accessed if the active process group is contained in the home group of the element.
Informally this simply says that any process involved (active) at the point the array element is accessed must hold a copy of the array element.

The error above is now exposed, because the home group of b [j] is p / x [0] / j. This does not contain the active process group inside the overall construct, which is p / x [N - 1] / j. This kind of error can be trapped by runtime checks in the generated code. Very often this kind of check can be lifted out of innermost overall loops, leading to minimal overhead. In the current example a check that p / x [0] contains the active process group, placed immediately before entering the overall construct, would suffice.


next up previous contents
Next: Recommendations for updating variables Up: Some rules and definitions Previous: Rules for distributed array   Contents
Bryan Carpenter 2002-07-12