\section{Programming examples}
\label{examples}

In this section we only give out example programs to show the new
language features.

The first example is Choleski decomposition,

\begin{small}
\begin{verbatim}
Procs1 p = new Procs1(4);
on(p) {
  Range x = new CyclicRange(n, p.dim(0));
  float a[[*,]] = new float [[n, x]];
  ... some code to initialise `a' ...
  float b[[*]] = new float [[n]]; // buffer

  for(int k = 0 ; k < N - 1 ; k++) {
    at(l = x[k]) {
      float d =  Math.sqrt(a[k,l]) ;
      a[k,l] = d ;
      for(int s = k + 1 ; s < N ; s++)
        a[s,l] /= d ;
    }
    Adlib.remap(b[[k+1:]], a[[k+1:,  k]]);

    overall(m = x [k + 1 :] )
      for(int i = x.idx(m) ; i < N ; i++)
        a[i,m] -= b[i] * b[x.idx(m)] ;
  }
  at(l = x [N - 1])
    a[N - 1,l] = Math.sqrt(a[N-1,l]) ;
}
\end{verbatim}
\end{small}

Here, \texttt{remap} is used to broadcast one updated column to each
process. \texttt{idx} is a function to get the global index of
\texttt{m} inside \texttt{x}.

The second example is Jacobi iteration,
\begin{small}
\begin{verbatim}
Procs2 p = new Procs2(2, 4);
Range
    x = new BlockRange(100, p.dim(0), 1),
    y = new BlockRange(200, p.dim(1), 1); 
on(p) {
  float [[,]] a = new int [[x,y]] ;
  ... some code to initialize `a'
  float [[,]] b = new int [[x,y]];

  Adlib.writeHalo(a);

  overall(i=x)
    overall(j=y)
      b[i,j] = 0.25 * (a[i-1,j] + a[i+1,j] + a[i,j-1] + a[i,j+1]);
  overall(i=x)
    overall(j=y)
      a[i,j] = b[i,j];
}
\end{verbatim}
\end{small}
In the above code, there is only one iteration, it is used to demonstrate
how to define range reference with \emph{halo} area, and how to use
the \texttt{writeHalo} function. 

\section{Java packages for HPspmd programming}
\label{sec:package}

The implementation of the HPJava compiler is based on runtime system.
It is actually a source-to-source translator converting an HPJava
program to a Java node program, with function calls to the runtime
system, called \emph{adJava}.

The runtime interface consists of several Java packages. The most
important one is the HPspmd runtime proper. It includes the classes
needed to translate language constructs. Other packages provide
communication and some simple I/O functions.

The important classes in the packages include an environment class,
distributed array ``container classes'', and related classes
describing process groups and index ranges.

The environment class {\tt SpmdEnv} provides functions to initialize and
finalize the underlying communication library (currently MPI).
Constructors call native functions to prepare the lower
level communication package.  An important field, {\tt apg},
defines the group of processes that is cooperating in ``loose
synchrony'' at the current point of execution.

The other classes correspond directly to HPJava built-in classes.  The
first hierarchy is based on \texttt{Group}.  A {\em group}, or {\em
  process group}, defines some subset of the processes executing the
SPMD program.  They can be used either to describe how program
variables such as arrays are distributed or replicated across the
process pool, or to specify which subset of processes execute a
particular code fragment.  Important members of adJava {\tt Group}
class include the pair {\tt on()}, {\tt no()} used to translate the
{\em on} construct.

%\begin{figure}[htb]
%  \begin{center}
%    \leavevmode
%    \psfig{figure=procs.eps,width=2.2in} 
%    \caption{The HPJava {\tt Group} hierarchy}
%    \label{fig:procs}
%  \end{center}
%\end{figure}

The most common way to create a group object is through the
constructor for one of the subclasses representing a {\em process
  grid}.  The subclass \texttt{Procs} represents a grid of processes
and carries information on process dimensions: in particular an
inquiry function {\tt dim(r)} returns a range object describing the
$r$-th process dimension.  {\tt Procs} is further subclassed by
\texttt{Procs0}, \texttt{Procs1}, \texttt{Procs2}, \ldots which
provide simpler constructors for fixed dimensionality process grids.

%The class hierarchy of groups and process grids is shown in figure
%\ref{fig:procs}.

The second hierarchy in the package is based on \texttt{Range}.
A {\em range} is a map from the integer interval $0,\ldots,n-1$ into
some process dimension (ie, some dimension of a process grid).
Ranges are used to parametrize distributed arrays and the
{\em overall} distributed loop.

%\begin{figure}[htb]
%  \begin{center}
%    \leavevmode
%    \psfig{figure=ranges.eps,height=1.9in} 
%    \caption{The HPJava {\tt Range} hierarchy}
%    \label{fig:ranges}
%  \end{center}
%\end{figure}

The most common way to create a range object is to use the constructor
for one of the subclasses representing ranges with specific {\em
distribution formats}.  
%The current class hierarchy is given in figure
%\ref{fig:ranges}.  
Simple block distribution format is implemented by
{\tt BlockRange}, while \texttt{CyclicRange} and \texttt{BlockCyclicRange}
represent other standard distribution formats of HPF.  The subclass
\texttt{CollapsedRange} represents a sequential (undistributed range).
Finally, \texttt{DimRange} represents the range of coordinates of a
process dimension itself---just one element is mapped to each process.

The related adJava class \texttt{Location} represents an individual
location in a particular distributed range.  Important members of the
adJava {\tt Range} class include the function {\tt location(i)} which
returns the $i$th location in a range and its inverse, {\tt idx(l)},
which returns the global subscript associated with a given location.
Important members of the {\tt Location} class include {\tt at()} and
{\tt ta()}, used in the implementation of the HPJava that {\em at}
construct.

Finally, we have the rather complex hierarchy of classes representing
distributed arrays.  HPJava global arrays declared using
\texttt{[[~]]} are represented by Java objects belonging to classes
such as:

\begin{small}
\begin{verbatim}
   Array1dI, Array1cI,
   Array2ddI, Array2dcI, Array2cdI, Array2ccI,
   ...
   Array1dF, Array1cF,
   Array2ddF, Array2dcF, Array2cdF, Array2ccF,
   ...
\end{verbatim}
\end{small}

Generally speaking the class \texttt{Array}\textit{ndc{\ldots}T}
represents $n$-dimensional distributed array with elements of type
{\em T}, currently one of {\tt I}, {\tt F}, \ldots, meaning {\tt int},
{\tt float}, \ldots\footnote{In the inital implementation, the element
  type is restricted to the Java primitive types.}.  The penultimate
part of the class name is a string of $n$ ``c''s and ``d''s specifying
whether each dimension is collapsed or normally distributed.  These
correlate with presence or absence of an asterisk in slots of the
HPJava type signature.  The concrete {\tt Array\ldots} classes
implement a series of abstract interfaces.  These follow a similar
naming convention, but the root of their names is {\tt Section} rather
than {\tt Array} (so {\tt Array2dcI}, for example, implements {\tt
  Section2dcI}).  The hierarchy of {\tt Section} interfaces is
illustrated in figure \ref{fig:arrays}.

\begin{figure}[htb]
  \begin{center}
    \leavevmode
    \psfig{figure=arrays.eps,height=2.4in} 
    \caption{The adJava {\tt Section} hierarchy}
    \label{fig:arrays}
  \end{center}
\end{figure}

The need to introduce the {\tt Section} interfaces should be evident
from the hierarchy diagram.  The type hierarchy of HPJava involves a
kind of multiple inheritance.  The array type {\tt int [[*, *]]}, for
example, is a specialization of {\em both} the types {\tt int [[*, ]]}
and {\tt int [[, *]]}.  Java allows ``multiple inheritance'' only from
interfaces, not classes.

%We will illustrate constructors of the {\tt Array} classes in later
%examples.  Here we mention 
Some important members of the {\tt Section} interfaces includes
inquiry functions {\tt dat()}, which returns an ordinary one
dimensional Java array used to store the locally held elements of the
distributed array.  The member {\tt pos(i, ...)}, which takes $n$
arguments, returns the local offset of the element specified by its
list of arguments.  Each argument is either a location (if the
corresponding dimension is distributed) or an integer (if it is
collapsed). These functions are used to implement elemental value
access of the global data. The inquiry {\tt grp()} returns the group
over which elements of the array are distributed.  The inquiry {\tt
  rng(d)} returns the $d$th range of the array.

Another package in adJava is the communication library.
The adJava communication package includes classes corresponding to the
various collective communication schedules provided in the NPAC PCRC
kernel.  Most of them provide of a constructor to establish a schedule,
and an \texttt{execute} method, which carries out the data movement
specified by the schedule.  The communication schedules provided in
this package are based on the NPAC runtime library.  Different
communication models may eventually be added through further packages.

The collective communication schedules can be used directly by
the programmer or invoked through invoked through certain wrapper functions.
A class named \texttt{Adlib} is defined
with \texttt{static} members that create and execute
communication schedules and perform simple I/O functions. 
This class includes, for example, the following
methods, each implemented by
constructing the appropriate schedule and then executing it.

\begin{small}
\begin{verbatim}
static public void remap(Section dst,Section src)
static public void shift(Section dst,Section src,int shift,int dim,int mode)
static public void copy(Section dst,Section src)
static public void writeHalo(Section src,int[] wlo,int[] whi,int[] mode)
\end{verbatim}
\end{small}

%Use of these functions will be illustrated in later examples.
%Polymorphism is achieved by using arguments of class {\tt Section}.

Given these classes, one can program in the HPspmd style in pure java
program. The idea of the HPJava compiler is just to translate the
HPJava program onto this interface, except it will use rather
optimized address caculation instead of those function calls to do
elementary access. For detailed translation scheme, please refer to 
\cite{Zha98}.

