\section{Issues in the language design}
\label{design}

With some of the implementation mechanisms exposed, we can
better discuss the language design itself.

\subsection{Extending the Java language}

The first question to answer is why use Java as a base language?
Actually, the programming model embodied in HPJava is largely language
independent.  It can bound to other languages like C, C++ and Fortran.
But Java is a convenient base language, especially for initial
experiments, because it provides full object-orientation---convenient
for describing complex distributed data---implemented in a relatively
simple setting, conducive to implementation of source-to-source
translators.  It has been noted elsewhere that Java has various
features suggesting it could be an attractive language for science
and engineering \cite{Java98}.

With Java as base language, an obvious question is whether we can
extend the language by simply adding packages, instead of changing the
syntax.  There are two problems with doing this for data-parallel
programming.

Our baseline is HPF, and any package supporting parallel arrays as
general as HPF is likely cumbersome to code with.  The examples given
earlier using the adJava interface illustrate this point.  Our runtime
system needs an (in principle) infinite series of class names
\begin{small}
\begin{verbatim}
   Array1dI, Array1cI, Array2ddI, Array2dcI, ...
\end{verbatim}
\end{small}
to express the HPJava types
\begin{small}
\begin{verbatim}
  int [[]], int [[*]], int [[,]], int [[,*]] ... 
\end{verbatim}
\end{small}
as well as the corresponding series for \texttt{char}, \texttt{float}, and so on.
To access an element of a distributed array in HPJava, one writes
\begin{small}
\begin{verbatim}
  a[i] = 3 ;
\end{verbatim}
\end{small}
In the adJava interface, it must be written as,
\begin{small}
\begin{verbatim}
  a.dat()[a.pos(i)] = 3 ;
\end{verbatim}
\end{small}
This is only for {\em simple} subscripting.  For passing array section
it will become even more complex using the raw class library
interface.

The second problems is that a Java program using a package like adJava
in a direct, naive way will have very poor performance, because all
the local address of the global array are expressed by functions such
as \texttt{pos}.  An optimization pass is needed to transform offset
computation to a more intelligent style.  So if a preprocessor must do
these optimizations anyway, it makes most sense to design a set of
syntax to express the concepts of the programming model more
naturally.

\subsection{Why not HPF?}

The design of the HPJava language is strongly influenced by HPF.
The language emerged partly out of practices adopted in our efforts to
implement an HPF compilation system \cite{Zha97}.  For example:

\begin{small}
\begin{verbatim}
  !HPF$ POCESSOR    P(4)
  !HPF$ TEMPLET     T(100)
  !HPF$ DISTRIBUTE  T(BLOCK) ONTO P
        REAL        A(100,100), B(100)
  !HPF$ ALIGN       A(:,*) WITH T(:)
  !HPF$ ALIGN       B WITH T
\end{verbatim}
\end{small}

have their conterparts in HPJava:

\begin{small}
\begin{verbatim}
  Procs1 p = new Procs1(4);
  Range x = new BlockRange (100, p.dim(0));
  float [[,*]] a = new float [[x,100]] on p;
  float [[ ]] b = new float [[x]] on p;
\end{verbatim}
\end{small}

Both languages provide a globally addressed name space for data parallel
applications.  Both of them can specify how data are mapped on to a
processor grid.  The difference between the two lies in their
communication aspects.  In HPF, a simple assignment statement may cause data
movement.  For example, given the above distribution, the assignment
\begin{small}
\begin{verbatim}
  A(10,10) = B(30)
\end{verbatim}
\end{small}
will cause communication between processor 1 and 2.  In HPJava, similar
communication must be done through explicit function calls\footnote{By default
Fortran array subscripts starts from 1, while HPJava global subscripts always
start from 0.}:
\begin{small}
\begin{verbatim}
  Adlib.remap(a[[9,9]], b[[29]]);
\end{verbatim}
\end{small}
Experience from compiling the HPF language suggests that, while there
are various kinds of algorithms to detect communication automatically,
it is often difficult to give the generated node program acceptable
performance.  In HPF, the need to decide on which processor the
computation should be executed further complicates the situation.  One
may apply ``owner computes'' or ``majority computes'' rules to
partition computation, but these heuristics are difficult to apply in
many situations.

In HPJava, the SPMD programming model is emphasized.  The distributed
arrays just help the programmer organize data, and simplify
global-to-local address translation.  The tasks of computation
partition and communication are still under control of the programmer.
This is certainly an extra onus, and the language is more difficult to
program than HPF\footnote{The program must meet SPMD constraints, eg,
only the owner of an element can access that data.  Runtime checking
can be added automatically to ensure such conditions are met.}; but
it helps programmer to understand the performance of the program much
better than in HPF, so algorithms exploiting locality and parallelism
are encouraged.  It also dramatically simplifies the work of the
compiler.

Because the communication sector is considered an ``add-on'' to the
basic language, HPJava should interoperate more smoothly than HPF with
other successful SPMD libraries, including MPI \cite{MPIStandard},
CHAOS \cite{Das94}, Global Arrays \cite{Nie96},
%DAGH \cite{HDDA_DAGH}, 
and so on.

\subsection{Datatypes in HPJava}

In a parallel language, it is desirable to have both local variables
(like the ones in MPI programming) and \emph{global} variables (like
the ones in HPF programming).  The former provide flexibility and are
ideal for task parallel programming; the latter are convenient
especially for data parallel programming.

In HPJava, variable names are divided into two sets.  In general those
declared using ordinary Java syntax represent local variables and
those declared with \texttt{[[ ]]} represent global variables.  The
two sectors are independent.  In the implementation of HPJava the
global variables have special data descriptors associated with them,
defining how their components are divided or replicated across
processes.  The significance of the data descriptor is most obvious
when dealing with procedure calls.

Passing array sections to procedure calls is an important component in
the array processing facilities of Fortran90 \cite{Fortran90}.  The data
descriptor of Fortran90 will include stride information for each array
dimension.  One can assume that HPF needs a much more complex kind of
data descriptor to allow passing distributed arrays across procedure
boundaries.  In either case the descriptor is not visible to the
programmer.  Java has a more explicit data descriptor concept; its
arrays are considered as objects, with, for example, a publicly
accessible \texttt{length} field.  In HPJava, the data descriptors for
global data are similar to those used in HPF, but more explicitly
exposed to programmers.  Inquiry fields such as \texttt{group},
\texttt{range} have a similar role in global data to the field
\texttt{length} in an ordinary Java array.

%In HPJava, an array can be sectioned to yield a ``zero-dimensional
%array'' by specifiying all scalar subscripts in double brackets.  The
%result is a global data entity {\em containing} the associated array element;
%the result is {\em not} the element itself.  The difference between an
%array sectioned to a global scalar and an array elment is that the global
%scalar has a descriptor specifying the process group that holds the element.
%This one reason why \texttt{[[~]]} is used for the
%section operation and \texttt{[~]} is used for array element access.
%The symbol \texttt{\#} is introduced to augment the type
%signature of a global scalar reference (a zero-dimensional array) to
%distinguish it from an ordinary Java scalar.

Keeping two data sectors seems to complicate the language and its
syntax.  But it provides convenience for both task and data parallel
processing.  There is no need for things like the \texttt{LOCAL}
mechanism in HPF to call a local procedure on the node processor.  The
descriptors for ordinary Java variables are unchanged in HPJava.  On
each node processor ordinary Java data will be used as local varables,
like in an MPI program.

\subsection{Programming convenience}

The language provides some special syntax for the programmer's
convenience.  Unlike the syntax for data declaration, which has
fundamental significance in the programming model, these extensions are
purely provide syntactic conveniences.

There are a limited number of Java operators overloaded.  A group
object can be {\em restricted} by a location using the \texttt{/}
operation, and a sub-range or location can be obtained from a range
using the \texttt{[~]} operator enclosing a triplet expression or an
integer, These pieces of syntax can be considered as shorthand for
suitable constructors in the corresponding classes.  This is comparable
to the way Java provides special syntax support for String class
constructor.

Another kind of overloading occurs in \emph{location shift}, which is
used to support \emph{ghost regions}.  A shift operator \texttt{+} is
defined between a location and an integer.  It has be illustrated in
the examples in the previous section.  This is a restricted
operation---it has meaning (and is legal) only in an array subscript
expression.

\section{Project in progress}

Projects related to this work include development of MPI, HPF,
and other parallel languages such as ZPL\cite{ZPL} and Spar\cite{Spar}.
%introduced elsewhere\footnote{For more analysis, please refer to our
%documents at http://www.npac.syr.edu/projects/pcrc/doc}.  
Here we explain the background and future developments of our own
project.

The work originated in our compilation practices for HPF. As described
in \cite{Zha97}, our compiler emphasize runtime support.
\emph{Adlib}\cite{Car98}, a PCRC runtime kernel library, provides a
rich set of collective communication functions.  It was realized that
by raising the runtime interface to the user level, a rather
straightforward (compared to HPF) compiler could be developed to
translate the high level language code to a node program calling the
runtime functions.

Currently, a Java interface has been implemented on top of the Adlib
library.  With classes such as \texttt{Group}, \texttt{Range} and
\texttt{Location} in the Java interface, one can write Java programs
quite similar to HPJava we proposed here. Yet, the program executed in
this way will have large overhead due to function calls (such as
address translation) when accessing data inside loop constructs.

Given the knowledge of data distribution plus inquiry functions inside
runtime library, one can substitute address translation calls with
linear operation on the loop variable, and keep most of the inquiry
function calls outside the loop. 

At present time, we are working on the design and implementation of
the prototype of this translator.  Further research works
will include optimization and safety-checking techniques in the
compiler for HPspmd programming.

Figure \ref{fig:performance} shows a preliminary benchmark for hand
translated versions of our examples. The parallel programs are executed
on 4 sparc-sun-solaris2.5.1 with mpich MPI and Java JIT compiler in
JDK 1.2Beta2. For Jacobi iteration, the timing is for about 90
iterations, the array size is 1024X1024.

\begin{figure}[ht]
  \begin{center}
    \leavevmode
    \putfig{Jacobi4.eps}{0.60}
%    \psfig{figure=Choleski4.eps,height=2.45in,width=3.5in}
%    \psfig{figure=Jacobi4.eps,height=2.45in,width=3.5in}
    \caption{Preliminary performance}
    \label{fig:performance}
  \end{center}
\end{figure}

We also compared the sequential Java, C++ and Fortran version of the
code, all with \texttt{-O} flag when compiling. The dotted lines shown
in the figure only represent times for the one processor case. We can
see that on a single processor, Java program use language own
mechanism for calculating array element address, it is slower than
HPJava, which uses an optimized scheme.

Similar test was made on an 8-node SGI challenge(mips-sgi-irix6.2),
the communication time is much smaller than the one on solaris, due to
MPI device using shared memory.

%The overall performance is not as
%good, because the JIT compiler on IRIX. The whole system are also
%being ported to Windows NT.

