Translating element access in distributed arrays

Figure 6: Translation of distributed array element access.

SOURCE:

$$\begin{eqnarray*} e & \equiv & a \verb$ [$ e_0 \verb$, $ \ldots \verb$, $ e_{R-1} \verb$]$ \end{eqnarray*}$$

TRANSLATION:

$$\begin{eqnarray*} {\bf T}\left[{e}\right] & \equiv & {\bf T}_{\mbox{\small dat}}... ...ight]\verb$ [$\mbox{\it OFFSET}(a, e_0, \ldots, e_{R-1})\verb$]$ \end{eqnarray*}$$

where:

$$\begin{array}{l} \mbox{The expression $a$\ is the subscripte... ...box{the macro {\it OFFSET} is defined in the text.} \end{array}$$

We only need to consider the case where the array reference is a distributed array: the general scheme is illustrated in Figure 6. The macro OFFSET is defined as

$$\begin{minipage}[t]{\linewidth}\begin{tabbing} $\mbox{\it OF... ...-1}\left[{a}\right], e_{R-1}\right)$\end{tabbing}\end{minipage}$$

There are three cases for the macro OFFSET_DIM depending on whether the subscript argument is a distributed index, a shifted index, or an integer subscripts (in a sequential dimension). We will only illustrate the case where $e_r$ is a distributed index $i$. Then

$$\begin{minipage}[t]{\linewidth}\begin{tabbing} $\mbox{\it OF... ..._r$\verb$.stride * $$\mbox{\it sub}$\end{tabbing}\end{minipage}$$

where $\mbox{\it sub}$ is the local subscript variable for this index (see the last section).

Ultimately--as we should expect for regular access patterns--the local subscript computations reduce to expressions linear in the indices of local loops. Such subscripting patterns are readily amenable to optimization by the compiler back-end, or, more likely, they can be further simplified by the HPspmd translator itself.

We have only sketched three of the more important schema, leaving out details. The full translation scheme for HPJava, recorded in [4], involves perhaps a couple of dozen such schema of varying complexity. In practice the translation phase described here is preceded by a ``pre-translation'' phase that simplifies some complex expressions by introducing temporaries, and adds run-time checking code for some of the rules described in section 3.