\documentstyle[psfig]{article}
%\usepackage{psfig}

\textwidth5.8in
\textheight7.8in
\voffset-0.5in
\hoffset-0.5in

\begin{document}

\title{\textbf{Structured SPMD programming}\linebreak -- \emph{Java
    language binding}}

\author{Guansong Zhang, Bryan Carpenter, Geoffrey Fox\\
  Xinying Li, Yuhong Wen  \\
  \\
  \emph{NPAC at Syracuse University} \\
  \emph{Syracuse, NY 13244} \\
  \\
  \emph{\{zgs, dbc, gcf, xli, wen\}@npac.syr.edu}}


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

\date{Oct. 1, 1997}

\maketitle

\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 \cite{Ken96} for parallel processing,
targeting at multi-processor system with distributed memory.

%\emph{background}

The language introduces a new programming style, called
\emph{structured SPMD programming}(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 has a single thread control on a well organized
  process group. As 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, at the same time, presents a well defined
  loosely synchronization mechanism among the processors.
  
\item \textbf{Global name space} Besides local variables, the language
  provides variables associated with \emph{data descriptor}, a global
  name space, especially, global addressed array with different
  distribute patterns among processors in a process group.  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}

In fact, the programming style introduced here is language
independent, it can also be binded with other programming
languages like C/C++ and Fortran.

However, we believe in the near future, Java will play a more
important role in the programming world. In addition Java language
itself is simple. So we explain the new language constructs inside
Java language, and implementing our prototype based on it.

%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, yet treated almost as a primary data-type in Java
language, we call it as a build-in class. In HPJava, we add more
build-in classes to represent basic concepts in our language.

\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);

\subsubsection{Process group}

A new class, \emph{Group}, is defined, it represents a process group,
typically with a grid structure and an associated set of {\em process
  dimensions}.

Class \texttt{Group} has subclasses derived from it to represent
different grid shape, such as \texttt{Procs1}, \texttt{Procs2}, etc.
For example,

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

defines a group \texttt{p} of a 2X4 2-dimension process grid. These 8
processes will have 2 \emph{processes dimensions} associate with
them.

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)}

\subsubsection{Distributed dimension and index with position}

In a programming language, array elements are corresponding to 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

In fact, we have two concepts here, an index \texttt{i} and a range
where the index can be chosen from, specified by \texttt{length}.
They are both of type \texttt{int}.

When describing an array with position information, we need two new
build-in classes in HPJava to represent those two concepts,

\begin{description}
\item{\bf Range.}  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.
  
\item{\bf Location.}  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.
\end{description}

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
\texttt{Group 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,

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

here ``\texttt{|}'' is 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.id(i);
\end{verbatim}
\normalsize

will assign variable \texttt{order} to 0.

\subsubsection{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}.  A subrange is a {\tt Range}.
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.

The symbol ``\texttt{:}'' is a special separator. It is used to
compose a \emph{triplet} expression, with three optional \texttt{int}
expression to represent an integer subset by pointing out the initial
position, final position and an optional stride size. Expression
\texttt{:98:2}, \texttt{1:98} and \texttt{1::2} are all legal triplet.
The default initial and finial value are zero and the maximum value of
the array index respectively. The default stride size is 1.  Unlike
other expressions in Java, there is no type information associate with
them.

\subsubsection{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}
    \label{fig:group}
  \end{center}
\end{figure}

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

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

\texttt{Group.dim(int)} is a member function return a \texttt{Range}
reference. It corresponds to a processor dimension, which reflects the
basic meaning of a range. This range can be considered either a block
range with its size as one, or a cyclic range of its extent the same
as the processor number. 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 \texttt{Range u}, and use it
to create a new group,

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

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

\small
\begin{verbatim}
  v|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}.

\small
\begin{verbatim}
  Location j = v|0;
\end{verbatim}
\normalsize

From the figure, we can see that \texttt{Group 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 we introduced above, for example, it is not
difficult to think that the following code

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

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

Further more, the language provided well defined constructs to switch
execution control among processes according to data items we want to
access. Therefor, we call the programming model introduced here
\emph{structured SPMD programming}.

\subsection{Global variables}

HPJava is a SPMD programming style 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 Java language. The variables created in this way are
\emph{local variables}, they are \emph{replicated} names on each
process, which will be accessed by each process 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 obtained 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 it is created. We will further introduce
this concept.

\subsubsection{Global scalar and data owner}

The following code,

\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 of \texttt{s} as
\texttt{Group q}. 

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 scalar.

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

will create a global array of size 100 on \texttt{Group p}. Here
\texttt{a} is a descriptor handle, which describes an one dimension
\texttt{float} type array. The distribution format is the same as a
collapsed range. We call it \emph{collapsed dimension}. In HPJava
term, \texttt{a} is also called a \emph{global or distributed array
  reference}.

A global array can also be created with different kinds of ranges we
introduced before. Unlike the global array defined with collapsed
dimension, array element in a range defined dimension is not
duplicated in that process dimension. 

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 [[#]] b = new float [[x]];
\end{verbatim}
\normalsize

will create a global array with \texttt{Range x} on \texttt{Group q}.
Here \texttt{a} is a descriptor handle, which describes an one
dimension \texttt{float} type array of size 100, distributed with
block range on the first dimension of \texttt{Group p}. 

Note, when defining a global array, if its dimension is not collapsed,
then a symbol \texttt{\#} is marked in double brackets.

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)
    b[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 something simpler here.

When a global array is defined with a collapsed dimension, accessing
its element is simpler.

\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, there is also no need to
allocate a descriptor on each dimension. 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 array introduced here is Fortran-style multi-dimension arrays
rather than C-like array-of-arrays, hence it can be clearly showed
that which dimensions the descriptor is describing.

The array-of-arrays in Java is still useful, global arrays can be
combined with 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}

\subsubsection{Array section and type signature}

HPJava provides array section of global arrays. The syntax of section
subscripting is similar to array definition, a double bracket is used.
The subscripts can be locations or ranges.

Suppose we still have

\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

then, \texttt{c}, \texttt{c[[i, y|1::2]]}, \texttt{c[[i, z]]} and
\texttt{b[[i]]} are all array sections. Here {\tt i} is a location in
the first range of {\tt b} 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 {\tt c}. Expression \texttt{b[[i]]} contains a single
element of {\tt b}, yet the result is a global scalar reference, not a
simple variable.

When section is made in a collapsed dimension, a triplet expression
instead of a range reference is used directly. 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.


In HPJava, array section expression will be used as arguments in
member function calls. As in any programming language, only the dummy
argument and actual argument have the same type signature, the
function call can be completed. 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 variable}& \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.

When used in method calls, \texttt{\#} marked type is a
\emph{super-type} of the one without the symbol. 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.

% 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 on 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 here. 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, \texttt{Adlib.global}.  During the execution, the
active process group can be set 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 single process program, accessing the value of a variable is
straight forward. Given a data reference, there is only one process
can be used to read or write it. In a SPMD program, 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. Say it in
HPJava terms: when assigning data, the data owner must be the active
process group.

We have already introduced the \texttt{on} construct to switch the
active process group, 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{b} defined in previous section,

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

    b[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{over} can be used to
combine the switching of the active process group with a loop,

% can we use at again?

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

is semantically equivalent to\footnote{But a compiler can implement
  \texttt{over} construct in a more efficient way.}

\small
\begin{verbatim}
  on(q) 
    for(int n=0;n<4;n++)
      at(Location 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}
\;\;{\tt over}\; \mathtt{(Location\; 
  i={\em range\_expression}{\tt |}{\em triplet\_expression})\; \{ }\\
\;\;\;\;{\tt...} \\
\;\;\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{over} 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. The most important
communication functions are introduced in section \ref{communication}.

% 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 noticeed 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 caculation 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. In this
section, we will only introduce a small number of top level collective
communication functions, through which data parallel applications may
have dead-lock free communication.

It should be noticed that the SPMD programming style of the language
also allow MPI library be integrated as part of the communication
libraries of the language. This part will also be introduced else
where.

\subsubsection{Package \texttt{adlib}}

As a Java language, HPJava has a special package \texttt{adlib}.
Several important collective communications are member functions of
a static class \texttt{Adlib} in the package.

\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 when is called.

\section{Programming examples in HPJava}
\label{examples}

We already saw one example program, Jacobi iteration, in section
\ref{Operators}. In this section, we have two more examples.

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

\small
\begin{verbatim}
  on(Adlib.global) {
    Range x = new CyclicRange(size, Adlib.global.dim(0));

    float a[[,#]] = new float [[size, x]];
    // initialize the array here;

    float b[[]] = new float [[size]]; // used as a buffer

    Location j;

    at(j=x|0)
      a[0,j]=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[[k,x|k+1:]]);

      over (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]=sqrt(a[k+1,j]);
    }
  }
\end{verbatim}
\normalsize

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

\small
\begin{verbatim}
  Group 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(Location i=x|:) {
        float [[,]] sub = new float [[B,B]];    

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

        over(Location j=y|:) { 
          //Local matrix multiplication ...
          matmul(c[[i, j, z, z]], sub, b[[i, j, z, z]]);
        }
      }
          
      //Cyclic shift 'b' in 'y' dimension ...
      Adlib.shift(tmp, b, 1, 0, 0); // dst, src, shift, dim, mode;
      Adlib.copy(b, tmp);
    }
  }
\end{verbatim}
\normalsize

\section{Summary}

Through the three simple examples in the report, we can see the
programming language we present here has all the power of a SPMD
program with MPI can have, yet, it has the convenience of programming
in 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 here 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 when Java plays a
more significant role in scientific and engineering computation, it
can be an intermediate language to implement high level programming
language such as HPF, or as a practical programming language itself 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{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}
