\documentstyle[psfig]{article}

\begin{document}

\sloppy

\pagestyle{plain}

\title{Note on HPJava Programming for Unstructured Problems}

\author{Bryan Carpenter}

\maketitle

Example from the CHAOS manual:
\small
\begin{verbatim}
C  Outer loop L1
L1 do i = 1, n_step
     ...
C    Sweep over edges: Inner Loop L2
L2   do i = 1, nedge
       n1 = edge1(i)
       n2 = edge2(i)
       y(n1) = y(n1) + f(x(n1), x(n2))
       y(n2) = y(n2) + g(x(n1), x(n2))
     end do
     ...
   end do
\end{verbatim}
\normalsize
This {\em could} be expressed in HPJava using HPF-like gather/scatter
operations (available in, for example, Adlib).  That would already
allow some optimization and reuse of communication schedules, but would
involve copying whole arrays of temporaries during the executor loop.
It would not directly allow for irregular repartition of the original
data array to reduce the absolute volume of traffic.

Chaos provides for various kinds of preprocessing before executing a
main loop like L1 above:
\begin{enumerate}
\item
Repartitioning of the main data arrays to improve locality
\item
Repartitioning of the indirection vectors to minimize the number of
off-processor references, following the redistributed data
\item
Translation of values in the indirection vectors to local subscripts,
and generation of the communication schedule (together these form the
``inspector'' phase).
\end{enumerate}
The first two steps are optional.  If adopted they normally yield new
distributed arrays, holding the same values as the original data and
indirection arrays, rearranged by some irregular permutations.

One possibility is to add to HPJava a new kind of distribution format
that includes a translation table {\em [confusing translation tables
with maps?]} in its descriptor.  Various high-level data-parallel
languages have taken this route, but we argue that it doesn't fit
particularly well with the design philosophy of HPJava.

Even if we adopt the policy that a repartitioned array should be a new
kind of distributed array, adding a translation table to descriptor is
not enough in itself to enable a CHAOS-like ``executor'' loop.  We also
need to extend the data segment of the repartitioned array with ghost
regions.  In general the number of ghost cells is unknown until after
the inspector phase.

\end{document}

