\documentclass[10pt, titilepage, twocolumn]{article}
\usepackage{psfig}
%\pagestyle{empty}                         %%%% No page Numbering

\addtolength{\textwidth}{0.6in}
\addtolength{\hoffset}{-0.3in}
\addtolength{\textheight}{1.6in}
\addtolength{\voffset}{-0.9in}

%\setlength{\textheight}{9.0in}
%\setlength{\textwidth}{6.5in}              %%% Preset settings
%\setlength{\columnsep}{0.375in}
%\setlength{\oddsidemargin}{0.0in}
%\setlength{\topmargin}{0.0in}
%\setlength{\headheight}{0.75in}
%\setlength{\headsep}{0.0in}
%\setlength{\footheight}{0.0in}
%\setlength{\parindent}{1pc}

\newenvironment{code}{\small}{\normalsize}

\begin{document}

\title{\textbf{A high level SPMD programming model: \emph{HPspmd} 
    \\ and its Java language binding}}

\author{Guansong Zhang, Bryan Carpenter, Geoffrey Fox\\
  Xinying Li, Yuhong Wen  \\
  \\
  \emph{111 College Place} \\
  \emph{NPAC at Syracuse University} \\
  \emph{Syracuse, NY 13244} \\
  \\
  \emph{\{zgs, dbc, gcf, xli, wen\}@npac.syr.edu} \\
  \emph{Fax: (315)4431973}} 

%\institute{NPAC at Syracuse University, Syracuse, NY 13244}

%\date{Oct. 1, 1997}

\maketitle
%\thispagestyle{empty}

\begin{abstract}
  
  This report introduces a new language, \emph{HPJava}, for parallel
  programming on message passing systems. The language is designed in
  a high level SPMD programming model. From examples and performance
  in its Java binding, the features of the new programming style, and
  its implementation are shown.

\end{abstract}

\paragraph{Keywords} Parallel programming, SPMD, Java

\section{Introduction}

%\footnote{This article is
%  based on \cite{Bry97}, intends to be used as a lecture note or
%  programming reference, especially for programmers new to the
%  language. Until the definition of the programming language become
%  mature, it will be kept as a living document.} 

In this report, we introduce \emph{HPJava} language, a programming
language extended from Java for parallel programming on message
passing systems, such as workstation clusters.

%targeting at multi-processor system with distributed memory.

%\emph{background}

Though its name comes directly from HPF\cite{HPF96}, the design of
HPJava does not inherit HPF completely. The language introduces a high
level SPMD programming style, \emph{HPspmd}, which can be summarized
as following,

%(We will explain more about this
%term in section \ref{SPMD}). It can be summarized as
%following\footnote{Though these are ``buzzwords'' just like Java has,
%  they try to characterize a language independent programming style.},

\begin{itemize}
\item \textbf{Structured SPMD programming} The programming language
  presented here depends on a well organized process group as control
  threads. As in a SPMD program, only the data owners are allowed to
  share the current control thread when the data items are accessed.
  The language offerers special constructs for programs to achieve
  this conveniently. 
  
\item \textbf{Global name space} Besides local variables, the language
  provides variables associated with \emph{data descriptor}, offering
  a global name space, especially, global addressed array with
  different distribute patterns. This helps to relieve programmers of
  error-prone activities like local-to-global, global-to-local
  translations in most data parallel applications.
  
\item \textbf{Collective communication} Accessing data on different
  processors is through a powerful collective communication library
  provided with the language. With this library, data parallel
  applications may have dead-lock free communication. As in SPMD
  style, the language itself does not provide data movement semantics
  implicitly. This encourages the programmer to write algorithms that
  exploit locality and simplifies the task of compiler writers.
  
\item \textbf{Hybrid of data and task parallel programming} The
  language provides constructs facilitating both data parallel and
  task parallel programming. Through language constructs, different
  processors can not only work simultaneously on global addressed
  data, but also execute independently complex procedures on their own
  local data. The conversion between these two phases is a seamless
  one.
  
\item \textbf{Flexible for future extension} The language itself only
  provides basic concepts to organize a group of process grid.
  Different communication patterns are implemented as library
  functions. This gives the possibility that when ever a new
  communication pattern is needed, it is relatively easy to be
  integrated.

\end{itemize}

%\emph{simple example}

The reason we don't follow HPF directly is that during the practice of
compiling HPF\cite{Zha97}, ``run-time'' support is emphasized in our
approach, and we found the level of runtime system can be effectively
raised to a programming model. In fact, the new programming style
introduced here is a language independent one, it also can be binded
with other programming languages such as C/C++ and Fortran.

As Java language is simple, elegant, and more promising, we
implemented our prototype based upon this language, and found the
efforts are quite rewarding.

%In the following, we introduce HPJava language by answering two
%questions: 1) how is HPJava different from Java? 2) what are
%differences between parallel programs in HPJava and MPI or HPF?

\section{Java language Binding} 

String is a class in Java, yet there is language syntax to support it.
In HPJava, we add more this kind of \emph{build-in} classes.

\subsection{Basic concepts}

The key concepts in the new programming style is built around process
groups, which will be used to support program execution control in a
parallel program.

%(syntactically, these special classes have similar status to, say,
%`Exception' in Java);

\paragraph{Process group}
A \emph{Group} is defined to represents a process group, typically
with a grid structure and an associated set of {\em process
  dimensions}. It has its subclasses to represent different grid
shape, such as \texttt{Procs1}, \texttt{Procs2}, etc. For example,

%\small
%\begin{verbatim}
%  Procs2 p = new Procs2(2,4);
%\end{verbatim}
%\normalsize

\begin{code}
\begin{verbatim}
  Procs2 p = new Procs2(2,4);
\end{verbatim}
\end{code}

Naturally, an HPJava program will be executed parallel in each process
of a group grid. 

%The package provides a pre-defined group,
%\texttt{Procs1 Adlib.global}.  It is an one dimension process grid,
%with the size of total number of logical processes the runtime
%environment provided. The program will starts on this group, and new
%process groups may be created as subsets of this group.

%\emph{(Mapping method? when the parent process group is one dim)}

\paragraph{Distributed dimension and index with position}

%In a programming language, array elements can be represented by an
%integer sequence. 

%for example in Java, we have
%
%\small
%\begin{verbatim}
%  int[] a = new int[10];
%\end{verbatim}
%\normalsize
%
%then, when accessing the array, we use an index in the sequence,
%
%\small
%\begin{verbatim}
%  for (int i=0; i<a.length; i++)
%    ...a[i]...
%\end{verbatim}
%\normalsize

For an ordinary array, its elements can be represented by an integer
sequence. By doing so, we have two concepts reflected by \texttt{int}
value here, an index to access each array element and a range where
the index can be chosen from. When describing a distributed array, we
use two new build-in classes in HPJava to represent the above
concepts, a) A {\em range} maps an integer interval into a process
dimension according to certain distribution format. Ranges describe
the extent and mapping of array dimensions. b) A {\em location}, or
slot, is an abstract element of a range. A range can be regarded as a
set of locations, actually it is a one-to-one mapping between the
global index and locations. For example,

\small
\begin{verbatim}
  Range x = new BlockRange(100, p.dim(0)) ;
  Range y = new CyclicRange(200, p.dim(1)) ;
\end{verbatim}
\normalsize

will create two ranges on the different process dimensions of group
\texttt{p}, one is block distributed, the other is cyclic
distributed. 

%We will further explain the function \texttt{dim} and the
%meaning of block and cyclic range in section \ref{SPMD}.
  
We can get 100 different items as \texttt{Location} references mapped
by the range \texttt{x} from integers, for example, the first one
is\footnote{Here ``\texttt{[ ]}'' is used to construct a new location,
  it is also used to construct a subrange in the following code.},

\small
\begin{verbatim}
  Location i = x[0];
\end{verbatim}
\normalsize

%here ``\texttt{[ ]}'' is used to construct a new location.
%an operator defined on \texttt{Rang} and
%\texttt{int}. 

%When mapping a location reference from a range by an integer, its
%\emph{order} or rank in the range is used. We can also get this
%integer value from an inquiry function in \texttt{Range} class.

%\small
%\begin{verbatim}
%  int order = x.idx(i);
%\end{verbatim}
%\normalsize

%will assign variable \texttt{order} to 0.

\paragraph{Subgroup and Subrange}

A {\em subgroup} is some slice of a process array, formed by
restricting the process coordinates in one or more dimensions to
single values. 

% A subgroup is a {\tt Group}.

%Any subgroup has a parent process grid and a dimension set which is
%some subset of the dimensions of the parent grid.  The {\em
%  restriction} operation on a group takes a slice in a particular
%dimension.  This restriction procedure is conveniently expressed in
%terms of a location reference.  

Suppose {\tt i} is a location in a range distributed over a dimension
of group {\tt p}. The expression

\small
\begin{verbatim}
  p / i
\end{verbatim}
\normalsize

represents a smaller group---the slice of {\tt p} to which location
{\tt i} is mapped.  

%(By the nature of the definition of the {\tt /}
%operator we can see that {\tt p / i / j} is equivalent to {\tt p / j /
%  i}.)

Similarly, a {\em subrange} is a section of a range, parameterized by
a global index {\em triplet}. Logically, it represents a subset of the
locations of the original range.

The syntax for a subrange expression is

\small
\begin{verbatim}
  x [ 1 : 49 ]
\end{verbatim}
\normalsize

%or

%\small
%\begin{verbatim}
%  x | 1 : 98 : 2
%\end{verbatim}
%\normalsize

%for a strided subrange.

%In the above examples, both ``\texttt{/}'' and ``\texttt{|}'' are
%overloaded operators in HPJava.

%``\texttt{[ ]}'' is also used to create new range references.

The symbol ``\texttt{:}'' is a special separator. It is used to
compose a \emph{triplet} expression\footnote{Unlike other expressions
  in Java, there is no type information associate with a triplet
  expression.}, with optional \texttt{int} expressions to represent an
integer subset. The default initial and finial value are zero and the
extend of the range respectively. The default stride size is 1.

\paragraph{Structured SPMD programming}
\label{SPMD}

When a process group is defined, a set of \texttt{Range} and
\texttt{Location} reference also have been defined, as in figure
\ref{fig:group}.

\begin{figure}[htbp]
  \begin{center}
    \leavevmode
    \psfig{figure=group.eps}
    \caption{Structured processes group}
    \label{fig:group}
  \end{center}
\end{figure}

The two ranges associated with the group \texttt{p} are,

\small
\begin{verbatim}
  Range u=p.dim(0);  
  Range v=p.dim(1);
\end{verbatim}
\normalsize

\texttt{dim(int)} is a member function return a range reference, which
corresponds to a processor dimension.

%More complicated ranges can be derived from
%it. Currently, the language supports \emph{block range}, \emph{cyclic
%  range}. The distribution format for these two ranges can be show in
%figure \ref{fig:range}. Besides a \emph{collapsed range}, defined as
%duplicated positions on each process in the dimension is also
%provided.

%\begin{figure}[htbp]
%  \begin{center}
%    \leavevmode
%    \psfig{figure=partition.eps}
%    \caption{Range distribution pattern}
%    \label{fig:range}
%  \end{center}
%\end{figure}

%Combining block range and cyclic range will get block-cyclic
%distribution. For example,

%\small
%\begin{verbatim}
%  Range v1=new CyclicRange(20, v);  
%  Range v2=new BlockRange(100, v1);
%\end{verbatim}
%\normalsize

%will create a cyclic(5) distribution on the second dimension of the
%processor.

%We define the range representing processor dimension as \emph{level 0}
%range, and range based on it one \emph{level} higher. So \texttt{u}
%and \texttt{v} are level 0 ranges, \texttt{v1} is a level 1 range and
%\texttt{v2} is a level 2 range\footnote{Currently, the language
%  supports up to level 2 range. We don't see the need to support level
%  3 range yet.}.

Further more, we can get a location in range \texttt{v}, and use it
to create a new group,

\small
\begin{verbatim}
  Location j = v|1;
  Group q = p/j;
\end{verbatim}
\normalsize

%We also can create a subrange of \texttt{u} by writing

%\small
%\begin{verbatim}
%  u|1::2
%\end{verbatim}
%\normalsize

%Note that in \texttt{Group p}, it need two locations to locate the
%processor with a dotted circle. They are \texttt{i} mapped from
%\texttt{Range u}, and a new location \texttt{j} mapped from
%\texttt{Range v}.

As shown in the figure, group \texttt{p} is a highly \emph{structured}
concept, and all the notions introduced around it contribute to
program execution control in the new programming language.

In a traditional SPMD program, execution control is based on
\texttt{if} statements and process id or rank numbers. In the new
programming language, switching execution control is based on the
structured process group. For example, it is not difficult to imagine,
and we will see that the following code,

\small
\begin{verbatim}
  on(p) {
    ...
  }
\end{verbatim}
\normalsize

will switch the execution control inside the bracket to processes in
group \texttt{p}.

The language also provided well defined constructs to switch
execution control among processes according to data items we want to
access. This will be introduced later.

%Therefor, we call the programming model introduced here
%\emph{structured SPMD programming}.

\subsection{Global variables}

As a SPMD programming language, when a program starts on a group of
$n$ processes, there will be $n$ logical control threads, which
mapping to utmost $n$ physical processors.

On each control thread, the program can define variables in the same
way as in a sequential one. The variables created in this way are
\emph{local variables}, they are \emph{replicated} names on each
process, which will be accessed individually.

Besides local variables, HPJava allows a program to define
\emph{global variables}, which are distributed on a process group. The
global variables will be considered a single entity during the
execution on each process which creates it.

The language has special syntax for the definition of global data. And
the global variables are all defined by using the \texttt{new}
operator from free storage. When a global variable is created, a
\emph{data descriptor} is also allocated to describe where the data are
created. 


\paragraph{Data descriptor and global data}

Actually, the concept of data descriptor is not entirely new. It
exists in Java language itself. The field \texttt{length} in Java
array reflects that Java array is accessed through a data descriptor.

On a single processor, an array variable can be labeled by a simple
value like memory addresses and an \texttt{int} value as length. On a
multi-processor, a more complicated structure is needed to label a
distributed array. We also call it \emph{data descriptor}.

The data descriptor portrays where the data is created, and how are
they distributed. A logical structure of a descriptor is shown in
figure \ref{fig:descriptor}.

\begin{figure}[htbp]
  \begin{center}
    \leavevmode
    \psfig{figure=descriptor.eps}
    \caption{Descriptor}
    \label{fig:descriptor}
  \end{center}
\end{figure}

New syntax were added in HPJava to define data with descriptors.

\small
\begin{verbatim}
  on(p)
    int # s = new int #;
\end{verbatim}
\normalsize

creates a global scalar on the current executing process group. In the
statement, \texttt{s} is a data descriptor handle, in HPJava term, a
\emph{global scalar reference}. And the scalar is of an integer value.
Global scalar references can be defined for each primitive type and
class type in Java.

The symbol \texttt{\#} in the right hand side of the assignment
indicates a data descriptor is allocated as the scalar is created.

Also it will be used to access this \texttt{int} value, as in the
following, 

%\footnote{Though the ``\texttt{\#}'' is used as a prefix
%  operator here, \texttt{s} is only a handle, it is not the descriptor
%  itself.}

\small
\begin{verbatim}
  on(p) {
    int # s = new int #;
    # s = 100;
  }
\end{verbatim}
\normalsize

%Figure \ref{fig:mapping} shows a possible memory mapping for this
%scalar on different processes. 

%\begin{figure}[htbp]
%  \begin{center}
%    \leavevmode
%    \psfig{figure=map.eps}    
%    \caption{Memory mapping}
%    \label{fig:mapping}
%  \end{center}
%\end{figure}

Note, the value of \texttt{s} is \emph{duplicated} on each process in
the current executing processes. Duplicated variables are different
from replicated local variables. The descriptors they have can be used
to keep their value identical on each process during the program
execution. 

%Compared with a local variable,

%\small
%\begin{verbatim}
%  on(p)
%    int t = 10;
%\end{verbatim}
%\normalsize

%the memory layout for the two will be quite different. There is no
%data descriptor allocated with \texttt{t}, neither \texttt{t} is a
%handle.

The group inside a descriptor is called \emph{data owner group}, it
defines where the global variable belongs.

%For a local variable, the data owner is the process which holds the
%data, though there is no descriptor to record it. For example, there
%will be an integer \texttt{t} on each process in \texttt{Group p} when
%\texttt{t} is defined as above.

%For a global variable, the data owner group and the group on which the
%data are defined are two different concepts. By default, the data
%owner is the current executing group. We can also specify the data
%owner group explicitly by using an optional \texttt{on} clause after
%\texttt{new} operator.

\small
\begin{verbatim}
  on(p)
    int # s = new int # on q;
\end{verbatim}
\normalsize

will set data owner field in the descriptor as group \texttt{q},
instead of the default \texttt{p}.

%Note, the \texttt{on} clause only change the data owner, it does not
%change the \emph{scope} of the variable. The above code is similar but
%different from the following one.

%\small
%\begin{verbatim}
%  on(q) 
%    int # s = new int #;
%\end{verbatim}
%\normalsize

%In the previous fragment, the owner of \texttt{s} is set as
%\texttt{Group q}, but its descriptor is duplicated on each process in
%\texttt{Group p} where \texttt{s} is defined.

%\subsubsection{Global array}

When defining a global array, it is not necessary to allocate a data
descriptor for each array element, so the syntax to define a global
array is not derived directly from the one for a scalar, and it can be
defined with different kinds of ranges we introduced before.

Suppose we still have

\small
\begin{verbatim}
  Range x = new BlockRange(100, p.dim(0)) ;
\end{verbatim}
\normalsize

and the process group defined in figure \ref{fig:group}, then

\small
\begin{verbatim}
  on(q) 
    float [[ ]] a = new float [[x]];
\end{verbatim}
\normalsize

will create a global array with range \texttt{y} on group \texttt{q}.
Here \texttt{a} is a descriptor handle, which describes an one
dimension \texttt{float} type array. It is block distributed on group
\texttt{q}\footnote{The \texttt{on} clause restrict the data owner
  group of the array to \texttt{q}. If group \texttt{p} is used
  instead, the one dimenstion array will be duplicated in the first
  dimenstion of the group, while block distributed on the second
  dimension.}. In HPJava term, \texttt{a} is also called a
\emph{global or distributed array reference}.

The array range can also be a \emph{collapsed} one. 

\small
\begin{verbatim}
  on(p) 
    float [[*]] a = new float [[100]];
\end{verbatim}
\normalsize

Again, \texttt{b} is a descriptor handle, which describes an one
dimension \texttt{float} type array of size 100.

When defining a global array, \texttt{*} is used to mark a 
non-collapsed dimension.

The accessing pattern of a global array element is not the same as a
global scalar reference, neither exactly same as a local array
element. Since global arrays may have position information in their
dimensions, we may need location references as their indexes when
their dimensions are not collapsed.

\small
\begin{verbatim}
  Location i=x|3;
  at(i)
    a[i]=3;
\end{verbatim}
\normalsize

Here the forth element of array \texttt{a} is assigned to 3. We will
leave \texttt{at} construct and how to access array elements in
section \ref{control}, and look at simpler example here.

When a global array is defined with a collapsed dimension, accessing
its element is as usual,

\small
\begin{verbatim}
  for(int i=0; i<100; i++)
    b[i]=i;
\end{verbatim}
\normalsize

will assign the loop index to each corresponding element in the array.

When defining a multi-dimension global array, one descriptor can
describe a rectangular array of any dimensions,

%\footnote{limitations
%  may come from the size of one dimension array in Java. Since it's
%  used to allocate memory for a multi-dimension array.}.

\small
\begin{verbatim}
  Range x = new BlockRange(100, p.dim(0)) ;  
  Range y = new CyclicRange(100, p.dim(1)) ;
  float [[#,#]] c = new float [[x, y]];
\end{verbatim}
\normalsize

will create a two-dimension global array, with the first dimension
block distributed and the second cyclic distributed. \texttt{c} is a
global array reference, its element can be accessed by putting a
single bracket with two location references inside.

The global array introduced here is Fortran-style multi-dimension
arrays rather than C-like array-of-arrays, hence it can be clearly
shown that which dimensions the descriptor is describing.

The array-of-arrays in Java is still useful. For example, one can
define a distributed array of local arrays.

%For example,

%\small
%\begin{verbatim}
%  int[] size = {100, 200, 400};
%  float [[#,#]] [] d = new float [size.length] [[#,#]];
%  Range x[];
%  Range y[];
%  for (int l = 0; l < size.length; l++) {
%    x[l] = new BlockRange(size[l], p.dim(0)) ;  
%    y[l] = new BlockRange(size[l], p.dim(1)) ;  
%    d[l] = new float [[x[l], y[l]]];
%  }
%\end{verbatim}
%\normalsize

%will create an array show as in figure \ref{fig:layer}.

%\begin{figure}[htbp]
%  \begin{center}
%    \leavevmode
%    \psfig{figure=layer.eps} 
%    \caption{Array of distributed array}
%    \label{fig:layer}
%  \end{center}
%\end{figure}

\paragraph{Array section and type signature}

HPJava provides array section of global arrays. The syntax of section
subscripting a global array is similar to its definition, a double
bracket is used.  The subscripts can be locations or
ranges\footnote{When section is made in a collapsed dimension, an
  integer or triplet expression is used directly.}.

%\small
%\begin{verbatim}
%  Range x = new BlockRange(100, p.dim(0)) ;  
%  Range y = new CyclicRange(100, p.dim(1)) ;
%  float [[#]] b = new float [[x]];
%  float [[#,#]] c = new float [[x, y]];
%\end{verbatim}
%\normalsize

Suppose we still have array \texttt{a} and \texttt{c} defined as
above, then, \texttt{b[[i]]}, \texttt{c}, \texttt{c[[i, y[1::2]]]},
and \texttt{c[[i, z]]} are all array sections. Here {\tt i} is a
location in the first range of {\tt a} and {\tt c}, and {\tt z} is a
subrange of the second range of {\tt c}.

Expression \texttt{c[[i, y[1::2]]]} and \texttt{c[[i, z]]} represent a
one-dimensional distributed array, providing an alias for a subset of
elements of \texttt{c}. Expression \texttt{a[[i]]} contains a single
element of  \texttt{a}, yet the result is a global scalar reference, not a
simple variable. 

%For example, if we
%have,

%\small
%\begin{verbatim}
%  float [[ ]] a = new float [[100]];
%\end{verbatim}
%\normalsize

%then \texttt{a[[:98:2]]} is a strided array section.

Array section expression will be used as arguments in function
calls\footnote{When used in method calls, the collapsed dimension
  array is a \emph{subtype} of the ordinary one. i.e. an argument of
  \texttt{float[[*,*]]}, \texttt{float[[*,]]} and \texttt{float[[,*]]}
  type can all be passed to a dummy of type \texttt{float[[,]]}.  But
  it is not true vise versa.}. Table \ref{tab:section} shows the type
relations of global data with different dimensions.

\begin{table}[htbp]
  \begin{center}
    \leavevmode
    \begin{tabular}[c]{l|ll} 
      \textbf{global var}& \textbf{array section} & \textbf{type} \\ 
      \hline
      2-dimension & \texttt{c} & \\
      & \texttt{c[[x,y]]} & \texttt{float [[,]]} \\ 
      \hline
      1-dimension & \texttt{c[[i,y]]} & \\
      & \texttt{c[[i,y[1::2]]]} & \texttt{float [[ ]]} \\ 
      \hline
      scalar(0-dim) & \texttt{c[[i,j]]} & \texttt{float \#} \\ 
      \hline
    \end{tabular}
    \caption{Section expression and type signature}
    \label{tab:section}
  \end{center}
\end{table}


In the table, both \texttt{i} and \texttt{j} are location
references.

% The dimension without \texttt{\#} indicates
%that there is a restricted range here, a collapsed dimension.

%\subsubsection{Data descriptor}
%\label{descriptor}

%When we introduced global data, we introduced a concept, \emph{data
%  descriptor}. We will explain more about the idea in this section.

%Actually, the concept of data descriptor is not something entirely
%new. It exists in Java language itself.

%In Java, array type is not of any class type, but a special reference
%type. In fact, it is exactly a handle to a data descriptor. We can see
%this point through the following example.

%In C language, a \texttt{main} function may has the following
%prototype,

%\small
%\begin{verbatim}
%  int main(int argc, char* argv[]);
%\end{verbatim}
%\normalsize

%From the function input, one can retrieve the information like how
%many command line arguments are passed, and where they are located.

%But in Java, a \texttt{main} function is written as,

%\small
%\begin{verbatim}
%  int main(String argv[]) {
%    ...
%  };
%\end{verbatim}
%\normalsize

%Why does not Java language need to pass the number of arguments?

%The answer is that you can always get this value from the array
%reference, \texttt{argv.length}. This means \texttt{argv} not only
%store where the array data is, but also record the length of the
%array. It is a simplest data descriptor.

%On a single processor, an array variable can be labeled by a simple
%value like memory addresses and an int value as length.

%On a multi-processor, to label a global variable, a more complicated
%structure is needed. We call it \emph{data descriptor}. It portrays
%where the data is created, and how are they distributed. A logical
%structure of a descriptor is shown in figure \ref{fig:descriptor}.

%\begin{figure}[htbp]
%  \begin{center}
%    \leavevmode
%    \psfig{figure=descriptor.eps}
%    \caption{Descriptor}
%    \label{fig:descriptor}
%  \end{center}
%\end{figure}

%The descriptor locates on each process which defines the global
%variable, whenever necessary, a process can look up those information
%to decide where the data is.

%In HPJava, when global data are defined, such as

%\small
%\begin{verbatim}
%  int # s = new int #;
%  float [[ ]] a = new float [[ ]];
%  float [[#]] b = new float [[x]];
%  float [[#,#]] c = new float [[x, y]];
%\end{verbatim}
%\normalsize

%a descriptor shown in the figure is allocated with them.

%Though they have different syntax looking and different names, such as
%global scalar reference an global array reference, in an
%implementation point of view, \texttt{s}, \texttt{a} \texttt{b} and
%\texttt{c} are all descriptor handles. They are not the descriptor
%themselves.

%Therefor, syntactically , we use the descriptor handle to represent
%the whole data it describes; And we use different operators, such as
%\texttt{\#} (when it describes scalar) or \texttt{[]} (when it
%describes array) to access the data value.

%When a new array section is created, a new descriptor has to be
%created to depict a subset of the same array with some dimension
%restricted by locations or subranges. In this case, a double bracket
%is used.

%\subsubsection{Inquiry fields and functions}

%The length of an array reference in Java can be get from its
%\texttt{length} field. Similarly, in HPJava, information like data
%owner group and distributed dimensions can be accessed from the
%following fields,

%\small
%\begin{verbatim}
%  Group group;   //data owner group
%  Range range[]; //dimension array
%\end{verbatim}
%\normalsize

%And further inquiry functions may be used to get values such as
%dimension extent and distribution format.

%For an array with collapsed dimensions, collapsed ranges will be
%created for the corresponding dimensions.

%%\subsubsection{Initialize global data}

\subsection{Program execution control}
\label{control}

HPJava has all the Java statements for program execution control
within a single process. It also introduces three new control
constructs, \texttt{on}, \texttt{at} and \texttt{over} for execution
control among processes.

%\subsubsection{Active process group}

A new concept, \emph{active process group}, is introduced. It is the
set of processes sharing the current thread of control.

In a traditional SPMD program, the concept of switching the active
process group is reflected by \texttt{if} statement,

\small
\begin{verbatim}
  if(myid>=0 && myid<4) {
    ...
  }
\end{verbatim}
\normalsize

means that inside the brace bracket, the processes numbered as 0 to 3
share the control thread.

In HPJava, this concept is expressed by a \texttt{Group} reference.
When a HPJava program starts, the active process group is a system
pre-defined value.  During the execution, the active process group can
be changed explicitly through an \texttt{on} construct in the language.

%for example

%\small
%\begin{verbatim}
%  on(p) {
%    ...
%  }
%\end{verbatim}
%\normalsize

%This will change the active process group of the code inside the
%bracket to \texttt{Group p}, which means that every statement inside
%the bracket is only executed by the processes inside \texttt{Group p}.

%\subsubsection{Accessing global variable}

In a shared memory program, accessing the value of a variable is
straight forward. In a message passing system, only the process which
holds data can read and write the data. A traditional SPMD program
achieves this by using \texttt{if} statements. For example,

\small
\begin{verbatim}
  if(myid==1) 
    my_data=3;
\end{verbatim}
\normalsize

will make sure that only \texttt{my\_data} on process 1 is assigned to
3.

In the language we present here, the same thing is required, and not
only for local variables but also for global variables, i.e. when
assigning data, the data owner must be the active process group.

Besides \texttt{on} construct, there is a more convenient way to
change the active process group according to the array element we want
to access, \texttt{at} construct.

Suppose we still have \texttt{a} defined in previous section,

\small
\begin{verbatim}
  on (q) {
    Location i=x[1];
    at(i)
      a[i]=3; //correct

    a[i]=3;   //error
  }
\end{verbatim}
\normalsize

The assign statement guarded by an \texttt{at} construct is correct,
the one without it may cause run time error if there is run time range
checking.

%In general, \texttt{at} construct has the form,

%\small
%\begin{verbatim}
%  at(Location i= ...) {
%    array[i]=...
%  }
%\end{verbatim}
%\normalsize

%inside the brace bracket, the active process group will be restricted
%by \texttt{Location i}. If \texttt{i} has already been declared,
%\texttt{Location} can be omitted in the construct.

%This is similar to a traditional SPMD program like,

%\small
%\begin{verbatim}
%  if( own(array[global_local(i)]) ) {
%    array[global_local(i)]=...
%  }
%\end{verbatim}
%\normalsize

% without at, the compiler need to insert guard before each statement.

In HPJava, a more powerful construct \texttt{overall} can be used to
combine the switching of the active process group with a loop,

% can we use at again or atall?

\small
\begin{verbatim}
  on(q)
    overall(i= x|0:3)
      a[i]=3;
\end{verbatim}
\normalsize

is semantically equivalent to\footnote{But a compiler can implement
  \texttt{overall} construct in a more efficient way. For detail definition
on \texttt{overall} construct, please refer to \cite{Car97}}

\small
\begin{verbatim}
  on(q) 
    for(int n=0;n<4;n++)
      at(i=x[n])
        b[i]=3;
\end{verbatim}
\normalsize

Inside each iteration, the active process group is changed to
\texttt{q/i}.

%In general, \texttt{over} construct has the form,

%\small
%\begin{flushleft}
%\begin{math}
%\begin{array}{l}
%\;\;\texttt{over}\; \mathtt{(Location\; 
%  i=\emph{range\_expression}\texttt{|}\emph{triplet\_expression})\; \{ }\\
%\;\;\;\;\texttt{...} \\
%\;\;\mathtt{\}}\\
%\end{array}
%\end{math}
%\end{flushleft}
%\normalsize

%Note, the \texttt{=} inside \texttt{over} construct header does not
%represent an assignment expression. It is used to compose an
%\texttt{over} loop \emph{control header}, with its left hand side as a
%loop index and its right hand side as loop range in which the loop
%index takes value.

%Similar as in \texttt{at} construct, if the loop index has already
%been declared in the program, keyword \texttt{Location} can be
%omitted.

In section \ref{examples}, we will use more programs to show that by
using the \texttt{at} and \texttt{overall} construct it is quite
convenient for a program to keep the active process group equal to the
data owner group of the assigned data.

%Generally speaking, when writing global data, the active process group
%should be equal to the data owner group. Bigger than the data owner
%group may cause runtime problem, smaller than the data owner group may
%cause the global variable have different values on different
%processes.  When reading global data, the active process group should
%be not bigger than the data owner group. In any situations, the active
%process group must be contained in the data owner group. We call this
%\emph{access rule} for global data. Some optional run-time checking
%may be added at compiling time to find code violating this rule, but
%it also should be kept in mind of the programmer to avoid the
%accessibility violation.

When accessing data on another process, HPJava needs explicit
communication as in a ordinary SPMD program. 

% special treat in function calls? It better not.
% switch APG among function calls
% each function keep its own policy on accessibility violation.

%\subsection{Operators}
%\label{Operators}

%Table \ref{tab:operator} summarize the operators which is new to or
%overloaded from Java, and their functionalities in HPJava.

%\begin{table}[htb]
%  \begin{center}
%    \leavevmode
%    \begin{tabular}{l|p{1.75in}|p{2.25in}}
%      \textbf{Operator} & \textbf{Operand type(s)} & \textbf{Operation performed} \\
%      \hline
%      \texttt{/} & \texttt{Group}, \texttt{Location} & restrict a group to a subgroup by a location,
%      used as the divide operator in Java \\  
%      \hline
%      \texttt{|} & \texttt{Range}, triplet expression & restrict a range to 
%      a location by an integer expression or a subrange by a triplet expression; also in 
%      \texttt{over} construct control header. used as the bit-or operator in Java \\
%      \hline
%      \texttt{:} & \texttt{int}, \texttt{int} & form a triplet expression \\
%      \hline
%      \texttt{\#} & global scalar reference & access values of the global scalar reference, 
%      also in definition of a global scalar reference, and a non collapsed dimension\\
%      \hline 
%      \texttt{[[]]} & global array reference, {\tt Location}, \texttt{Range} or triplet expression 
%      & section subscript a global array,
%      also in definition of a global array reference \\
%      \hline
%      \texttt{[]} & global array reference, \texttt{Location} & access array element \\
%      \hline
%      \texttt{=} & & in \texttt{over} construct control header. used as an assignment expression in Java \\
%      \hline
%%      \texttt{<<}, \texttt{>>} & \texttt{Location}, \texttt{int} & shift locations of the element accessed, 
%%      used as shift operator in Java \\
%%      \hline
%    \end{tabular}
%    \caption{Operator}
%    \label{tab:operator}    
%  \end{center}
%\end{table}

%The first three items are used upon built-in classes in HPJava.
%Though we list symbol \texttt{:} here, it is different from other
%operators. As we introduced earlier, when it is used on integer, no
%value in Java type is returned, only a triplet expression is formed.
%The next four items are concerned with defining and accessing global
%data. We consider \texttt{[]} as an operator on array reference here.

%There are two things we need to pay attention to in this section.

%\paragraph{Operator \texttt{new}}

%When \texttt{new} is used to allocate global variables in the program,
%the new data are created on the current active process group. In
%HPJava, there is an optional \texttt{on} clause, which can be used
%after \texttt{new} operator to specify the data owner group. Here
%again, it should be noticed that the active process group as an
%executor of \texttt{new} is different from the data owner group, the
%one specified by the \texttt{on} clause.

%\small
%\begin{verbatim}
%  on(p) {
%    int # s = new int # on q;
%    ...
%  }
%\end{verbatim}
%\normalsize

%will create a global scalar similar but different to the one created in
%the following,

%\small
%\begin{verbatim}
%  on (p) {
%    int # s = new int #;
%    ...
%  }
%\end{verbatim}
%\normalsize

%In the first fragment, the data descriptor is duplicated on all
%process in \texttt{Group p}, but for those not in \texttt{Group q},
%the data reference field of the descriptor is undefined.

%We also have accessibility problem here. One can not define,

%\small
%\begin{verbatim}
%  on (q) 
%    int # s = new int # on p;
%\end{verbatim}
%\normalsize

%% duplicated data and dimension

%% create new group -- mapping

%% create new range and location without group?
%% what about a static range or location? 
%% a reference counting in group, 
%% when ever a range is created, increase the counter.
%% similar thing for range and location.

%\paragraph{Restricted type conversion}

%When an array has position information in its dimensions,
%\texttt{Location} references, instead of \texttt{int} values are used
%as indexes. Given a global index we can get a location reference by
%\texttt{|} operation from the range. Sometimes it is also convenient
%that given a location reference, we can get the order of the location
%in the range it comes from. So a type conversion is defined from
%\texttt{Location} to \texttt{int} inside \texttt{at} and \texttt{over}
%constructs.

%\small
%\begin{verbatim}
%  on(q)
%    over(Location i= x|0:3) {
%      b[i]=(int)i;
%    }
%\end{verbatim}
%\normalsize

%will assign the location id to each array element. It is equivalent to,

%\small
%\begin{verbatim}
%  on(q)
%    over(Location i= x|0:3) {
%      b[i]=x.id(i);
%    }
%\end{verbatim}
%\normalsize

%Whenever necessary, this conversion can be an implicit one. 

%We call it as a \emph{restricted conversion}, because it works only with 
%\texttt{at} and \texttt{over} constructs. For example,

%\small
%\begin{verbatim}
%  on(q)
%    over(Location i= x|0:3) {
%      Location j=i;
%      b[i]=j;          //error, j can not be converted;
      
%      Range y=x;   
%      Location k=y|i;  //correct, i converted to an integer;
%      b[i]=k;          //error, k can not be converted;
%    }
%\end{verbatim}
%\normalsize

%Another restricted type conversion is vice versa, from \texttt{int} to
%\texttt{Location}. This only happens when an integer used as an index
%in a dimension which is not a collapsed dimension, and it will be
%converted to the location mapping from the range which define the
%dimension of the array.

%For example, suppose \texttt{b} is a distributed array,

%\small
%\begin{verbatim}
%  int i=3;
%  b[(Location)i]=i;        
%\end{verbatim}
%\normalsize

%is equivalent to,

%\small
%\begin{verbatim}
%  int i=3;
%  b[b.range[0]|i]=i;        
%\end{verbatim}
%\normalsize

%Similarly, a triplet expression can be converted to a subrange. Both
%conversions are valid only when their results expected to be a
%location or subrange. And they also can be implicit ones.

%Adding integers and triplets as \emph{access keys} for distributed
%array provides a ``higher level'' access for programmers. But they are
%not intend to be abused. A programmer should consider their code to
%exploit the possibility to reuse concepts such as location and
%subrange to improve efficiency, instead of depending compiler to find
%reusable patterns. One more thing need to be noticed is that though it
%is actually correct to use both location reference and integer to
%access array element in a non-collapsed dimension, we still use symbol
%\texttt{\#} to mark non-collapsed dimension when defining a
%distributed array. The reason to do this is to help compiler generate
%better code for address calculation when an array dimension is
%collapsed.

%These type conversions are defined to simplify program writing. If
%they look confusing, one can always use inquiry functions to get the
%desired results.

%One typical use of the type conversion is location shift. It supports
%\emph{ghost regions}, which require a new constructor for {\tt
%  BlockRange} with specification of ghost widths. A collective
%operation {\tt Adlib.writeHalo} can update the ghost regions of a
%distribute array, copying values from the physical segments of
%neighboring processes. For example, the following is a version of
%Jacobi iteration with only one iteration inside.

%\small
%\begin{verbatim}
%  Procs2 p(2, 4);

%  on(p) {
%    Range x = new BlockRange(100, p.dim(0), 1);  // ghost width 1
%    Range y = new BlockRange(200, p.dim(1), 1);  // ghost width 1

%    int [[#,#]] a = new int [[x,y]] ;

%    // ... some code to initialize `a'

%    int [[#,#]] b = new int [[x,y]];

%    Adlib.writeHalo(a);

%    over(Location i=x|:)
%      over(Location j=y|:)
%        b[i,j] = (a[i-1,j] + a[i+1,j] + a[i,j-1] + a[i,j+1]) / 4;
%        // location i, j converted to integer + or - one, converted back;

%    over(Location i=x|:)
%      over(Location j=y|:)
%        a[i,j] = b[i,j];

%  }
%\end{verbatim}
%\normalsize

\subsection{Communication library functions}
\label{communication}

Communication libraries are provided as packages in HPJava. Detailed
function specifications will be introduced in other papers. Here we
will only introduce a small number of top level collective
communication functions, through which data parallel applications may
have dead-lock free communication.

In the current design, the collective communications are member
functions of a static class \texttt{Adlib} in a HPJava package.
\texttt{Adlib.remap} will copy the corresponding element from one to
another, regardless of their distribution format. \texttt{Adlib.shift}
will shift certain amount in a specific dimension of the array in
either cyclic or off-edge mode. \texttt{Adlib.writeHalo} is used to
support ghost region.

Since the basic programming style is SPMD, it is also possible to
allow other communication library be integrated as part of the
communication packages of the language.  We have already implemented
Java MPI interface. Currently CHAOS \cite{Das94} and GA \cite{Nie96}
are being considered as ``add-on'' packages.

%This part will also be introduced else where.

%\subsubsection{Package \texttt{adlib}}
%As a Java language, HPJava use packages for communication functions.

%Several important collective communications are member functions of a
%static class \texttt{Adlib} in the packages.

%\paragraph{\texttt{Adlib.remap}}

%Given two global array of the same shape and element type, {\tt
%  Adlib.remap} will copy the corresponding element from one to
%another, regardless of their distribution format.

%\paragraph{\texttt{Adlib.shift}}

%This function will shift certain amount in a specific dimension of the
%array in either cyclic or off-edge mode. Explicit memory management
%for the shift is needed.

%\paragraph{\texttt{Adlib.writeHalo}}

%This function is used to support ghost region, it update the halo area
%of the global array from neighboring processes.

\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,

%\subsection{Choleski decomposition}

%In \cite{Ort89} different kinds of Choleski algorithm organization are
%discussed. Among them, column interleaved outer product form and row
%interleaved column Choleski form are considered more promising ones on
%a parallel computer system with distributed memory.  Here we only
%write one of them, the outer product form of Choleski algorithm, which
%is based on the following mathematic equation:

%\begin{displaymath}
%A_1
%%=
%%\left[ \begin{array}{cc}
%%a_{11}           & \mathbf{a}_1\mathit{^T}   \\
%%\mathbf{a}_{1}   & A_s                       \\
%%\end{array} \right]
%%=
%%\left[ \begin{array}{cc}
%%a_{11}                   & a_{11}^{1/2}\mathbf{l}_1\mathit{^T}      \\
%%a_{11}^{1/2}\mathbf{l}_1 & A_2+ \mathbf{l}_1l_1\mathit{^T}          \\
%%\end{array} \right]
%%\end{displaymath}
%%\begin{displaymath}
%=
%\left[ \begin{array}{cc}
%a_{11}^{1/2}    &  0  \\
%\mathbf{l}_{1}  &  I  \\
%\end{array} \right]
%\left[ \begin{array}{cc}
%1 & 0    \\
%0 & A_2  \\
%\end{array} \right]
%\left[ \begin{array}{cc}
%a_{11}^{1/2} & \mathbf{l}_1\mathit{^T}   \\
%   0         &  I                        \\
%\end{array} \right]
%\end{displaymath}

%the updating of the submatrix $A_2$ is accomplished by subtracting the
%outer product of $\mathbf{l}_1l_1\mathit{^T}$.

%%A simple description of the algorithm in a sequential code may be,

%%\begin{displaymath}
%%\begin{array}{l}
%%l_{11}=a_{11}^{1/2} \\
%%For\; k=1\; to\; n-1 \\
%%\;\;\;\; For\; s=k+1\; to\; n \\
%%\;\;\;\;\;\;\;\; l_{sk}=a_{sk}/l_{kk} \\
%%\;\;\;\;  For\; j=k+1\; to\; n \\
%%\;\;\;\;\;\;\;\;    For\; i=j\; to\; n \\
%%\;\;\;\;\;\;\;\;\;\;\;\;      a_{ij}=a_{ij}-l_{ik}l_{jk} \\
%%\;\;\;\; l_{k+1, k+1}= a_{k+1, k+1}^{1/2} \\
%%\end{array}
%%\end{displaymath}

%On a parallel computer with a distributed memory, the array may have a
%column-interleaved storage, then each processor can update its own
%column after getting the first updated column of the matrix or
%submatrix.

%We write the above algorithm in the following HPJava program. In the
%code, a cyclic range is used to allocate the original array on
%multiprocessors, the result $L$ can overwrite part of its storage.
%During the computation, collective communication \texttt{remap} is
%used for broadcasting updated columns.

\scriptsize
\begin{verbatim}
  Procs1 p = new Procs1(4);
  on(p) {
    Range x = new CyclicRange(size, p.dim(0));
    float a[[*,]] = new float [[size, x]];
    // initialize the array here;
    float b[[*]] = new float [[size]]; // as a buffer

    at(j=x[0])
      a[0,j]=Math.sqrt(a[0,j]);

    for(int k=0; k<size-1; k++) {
      for(int s=k+1; s<size; s++)
        at(j=x[k])
          a[s,j]/=a[j,j];

      Adlib.remap(b[[k+1:]],a[[x[k+1:], k]]);

      overall (j=x|k+1:)
        for (int i=x; i<size; i++)
          a[i,j]-=b[i]*b[j];

      at(j=x[k+1])
        a[k+1,j]=Math.sqrt(a[k+1,j]);

    }
  }
\end{verbatim}
\normalsize

Here, \texttt{remap} is used to broadcast one updated column to each
process.

The second example is Jacobi iteration,

\scriptsize
\begin{verbatim}
  Procs2 p = new Procs2(2, 4);
  Range x = new BlockRange(100, p.dim(0), 1); 
  Range 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] = (a[i-1,j] + a[i+1,j] + 
                 a[i,j-1] + a[i,j+1]) * 0.25;
    overall(i=x|:)
      overall(j=y|:)
        a[i,j] = b[i,j];
  }
\end{verbatim}
\normalsize

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. 

%\subsection{Fox's algorithm for matrix multiplication}

%Recall that if $A$ and $B$ are square matrix of order $n$, then 
%$C=AB$ is also a square matrix of order $n$, and $c_{ij}$ is obtained
%by taking the dot product of the $i$th row of $A$ and $j$th column of
%$B$. That is,

%\begin{displaymath}
%c_{ij}=a_{i0}b_{0j}+a_{i1}b_{1j}+...+a_{i,n-1}b_{n-1,j}  
%\end{displaymath}

%Fox's algorithm \cite{Unu97} for multiplication organize $A$, $B$ and
%$C$ into submatrix on a P by P process array. It take $P$ steps, in
%each step, broadcast corresponding submatrix of $A$ on each row of the
%processes, do local computation and then shift array $B$ for the next
%step computation. Write this algorithm in HPJava, we still use
%\texttt{Adlib.remap} to broadcast submatrix, \texttt{matmul} is a
%subroutine for local matrix multiplication. \texttt{Adlib.shift} is
%used to shift array $B$, and \texttt{Adlib.copy} copies data back
%after shift, it can also be implemented as nested \texttt{over} and
%\texttt{for} loops.
%\scriptsize
%\begin{verbatim}
%  Procs2 p=new Procs2(P,P);
%  Range x=p.dim(0); Range y=p.dim(1);
%  on(p) {
%    float [[#,#, , ]] a = new float [[x,y,B,B]]; 
%    float [[#,#, , ]] b = new float [[x,y,B,B]]; 
%    //input a, b here;

%    float [[#,#, , ]] c = new float [[x,y,B,B]]; 
%    float [[#,#, , ]] temp = new float [[x,y,B,B]]; 
                  
%    for (int k=0; k<P; k++) {
%      over(i=x|:) {
%        float [[,]] sub = new float [[B,B]];    

%        //Broadcast submatrix in 'a' ...
%        Adlib.remap(sub, a[[i, (i+k)%P, z, z]]);

%        over(j=y|:) { 
%          //Local matrix multiplication ...
%          matmul(c[[i, j, z, z]], sub, b[[i, j, z, z]]);
%        }
%      }
          
%      //Cyclic shift 'b' in first dim, amount 1 ...
%      Adlib.shift(tmp, b, 1, 0, 0); 

%      Adlib.copy(b, tmp);
%    }
%  }
%\end{verbatim}
%\normalsize

\section{Project in progress}

The related projects of our work may include development of MPI, HPF,
and other parallel languages such as ZPL and Spar, which are
introduced else where\footnote{For more analysis, please refer to our
  documents at http://www.npac.syr.edu/projects/pcrc/doc}. Here we
explain more backgrounds and future developments about our own
project.

The work originated in our compilation practice in HPF. As introduced
in \cite{Zha97}, our compiler emphasize runtime system support.
\emph{Adlib}\cite{Car98}, as PCRC runtime kernel library, provides a
rich set of collective communication functions. During the practice,
it is realized that the runtime interface can be effectively raised to
a higher level, and a rather straight-forward (compared to HPF)
compiler can be developed to translate the high level language code to
a node program calling runtime interface functions.

Currently, Java interface has been implemented on top of the Adlib
library. With classes such as \texttt{Group}, \texttt{Rang} 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 out side loop constructs. This is the basic idea of the
HPJava compiler.

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

Figure \ref{fig:performance} shows a preliminary benchmark for hand
translated codes 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.

\begin{figure}[htb]
  \begin{center}
    \leavevmode
    \psfig{figure=Choleski.eps,height=2.45in,width=3.5in} 
    \psfig{figure=Jacobi.eps,height=2.45in,width=3.5in}
    \caption{Preliminary performance}
    \label{fig:performance}
  \end{center}
\end{figure}

We also compared the sequential C++ version of the code. As shown
in the figure.

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. Yet the overall performance is not as
good, because the JIT compiler on irix. The whole system are also
being ported to Windows NT.

\section{Summary}

Through the simple examples in the report, we can see the programming
language presented here has the flexibility of a SPMD program, and the
convenience of HPF. The language encourages programmers to express
parallel algorithms in a more explicit way. We believe it will help
programmers to solve real application problems easier compared with
using communication packages such as MPI directly, and allow the
compiler writer to implement the language compiler without the
difficulties met in the HPF compilation.

The Java binding is only an introduction of the new programming style.
(A Fortran binding is being developed.) It can be used as a software
tool for teaching parallel programming. And as Java for scientific
computation become more mature, it will be a practical programming
language to solve real application problems in parallel and distribute
environments.

% how about irregular

\begin{thebibliography}{99}
  
%\bibitem{Ken96} Ken Arnold, James Gosling, ``The Java programming
%  language'', Addison-Wesley Publishing Company, Inc., 1996.
  
\bibitem{HPF96} High Performance Fortran Forum, ``High Performance
  Fortran Language Specification'', version 2.0, Oct. 1996
  
\bibitem{Zha97} Guansong Zhang, Bryan Carpenter, Geoffrey Fox,
  Xiaoming Li, Xinying Li, and Yuhong When. ``PCRC-based HPF
  compilation'', 10th International Workshop on Languages and
  Compilers for Parallel Computing, 1997.
  
\bibitem{Car97} Bryan Carpenter, Guansong Zhang, Geoffrey Fox, Xinying
  Li, and Yuhong Wen. ``Introduction to Java-Ad''.
  http://www.npac.syr.edu/projects/pcrc/doc.
  
%\bibitem{Zha97a} Guansong Zhang, Bryan Carpenter, Geoffrey Fox,
%  Xinying Li, and Yuhong Wen. ``Structured SPMD programming''.
%  http://www.npac.syr.edu/projects/pcrc/doc.

\bibitem{Das94} R. Das, M. Uysal, J.H. Salz, and Y.-S. Hwang.
  ``Communication optimizations for irregular scientific computations
  on distributed memory architectures''. Journal of Parallel and
  Distributed Computing, Sep. 1994
  
\bibitem{Nie96} J. Nieplocha, R.J. Harrison, and R.J. Littlefield. The
  Global Array: Non-uniform memory access programming model for
  high-perfomance computers.  The Journal of Supercomputing, 1996.
  
\bibitem{Car98} Bryan Carpenter, Guansong Zhang and Yuhong Wen, ``NPAC
  PCRC Runtime Kernel (Adlib) definition'',
  http://www.npac.syr.edu/projects/pcrc/doc

%\bibitem{Ort89} J. Ortega, ``Introduction to parallel and vector
%  solution of linear system'', Plenum Press, 1989.

%\bibitem{Unu97} E Pluribus Unum, ``Programming with MPI'', Morgan
%  Kaufmann Publishers, Inc. 1997.

\end{thebibliography}

\end{document}
