\documentstyle[psfig]{article}

\begin{document}

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

\author{Guansong Zhang, Bryan Carpenter}

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

\begin{itemize}
\item \textbf{Structured SPMD programming}, a SPMD program, well
  defined loosely synchronization mechanism among organized process
  group.
  
\item \textbf{Global name space}, global addressed array with
  different distribute patterns among processors.
  
\item \textbf{Collective communication} through collective
  communication to access non-local data, data parallel applications
  can have dead-lock free communication.
  
\item \textbf{Hybrid of data and task parallel programming}
  facilitating both data parallel and task parallel programming.
  
\item \textbf{Flexible for future extension}.

\end{itemize}

\section{Java language Binding} 

build-in class

\subsection{Basic concepts}

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

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

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

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

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

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


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

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

\subsection{Global variables}

When a global variable is created, a \emph{data descriptor} is also
allocated to describe where it is created.  

\subsubsection{Global scalar and data owner}

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

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

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

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

In the first 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}

collapsed dimension

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

non-collapsed dimension

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

  on(q) 
    float [[#]] b = new float [[x]];
\end{verbatim}
\normalsize

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

array of array

\small
\begin{verbatim}
  float [[#,#]][] d;
  Range x[];
  Range y[];
  int[] size = {100, 200, 400};
  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}

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

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}

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

\subsubsection{Inquiry fields and functions}

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

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

\subsubsection{Active process group}

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

In HPjava,

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

\subsubsection{Accessing global variable}

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

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

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

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

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

\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

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

\small
\begin{flushleft}
\begin{math}
\begin{array}{l}
\;\;\;\;{\tt over}\; {\tt(Location\; i={\em subrange\_expression})\; \{}\\
\;\;\;\;\;\;{\tt...} \\
\;\;\;\;{\tt \}}\\
\end{array}
\end{math}
\end{flushleft}
\normalsize

\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,
      used as the bit-or operator in Java \\
      \hline
      \texttt{:} & \texttt{int}, \texttt{int} & form triplet expression \\
      \hline
      \texttt{\#} & global scalar reference & access values of the global scalar reference, 
      also used to define 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 used to define a global array reference \\
      \hline
      \texttt{[]} & global array reference, \texttt{Location} & access array element \\
      \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}

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

\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 a range. 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 equevalent 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 coversion}, 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;
      
      Range y=x;   
      Location k=y|i;  //correct;
      b[i]=k;          //error;
    }
\end{verbatim}
\normalsize

\paragraph{Location shifting}

Shifting a location is used specially to support \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.
Shift operators {\tt >>} and {\tt <<} applicable to locations return
locations a specified number of places to the right or left of the
current position (the results are only defined when used as an index
to access distributed array). For example,

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

    Adlib.writeHalo(a);

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

    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;

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

  }
\end{verbatim}
\normalsize

is a version of Jacobi iteration with only one iteration inside.

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

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

\texttt{Adlib.shift} will shift certain amount in a specific dimension
of the array. 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
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}

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}

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


Fox's algorithm 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
subrountion 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, y|((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 encourage programmer to express the parallel
algorithm in a more explicit way. We believe it will help programmers
to solve real application problems easier compared with using 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 is a testbed on
ideas, it can also be used as a tool for teaching parallel
programming.

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