


\documentstyle{article}

\input{psfig} 

\begin{document}

\sloppy

\pagestyle{plain}

\title{HPJava Suggestions  \large \em [email dated 5 Aug 1996]}

\author{Bryan Carpenter}

\date{}

\maketitle


For debate, some suggestions for a Java syntax (ie, class library
interface).

I'm trying to incorporate the basic idea of everything being collective
operations on array objects.  I haven't defined FORALL ``scripts'', but
the expression trees suggested here could be regarded as a sort of
pre-parsed script.  The advantage is that we don't need parsers and
symbol tables in the run-time.  The disadvantage is that the syntax is
quite awkward.  This is really a peculiarity of Java (see comments below).

One intention with this interface is that it is sufficiently high-level
that it can be implemented in terms of a SIMD-style Java controller for
an HPC back-end, or of a pure SPMD parallel Java model.

I'm using my ``Range'' structures because they allow a simple definition
of ``conformance'', and they are useful in indexed array expressions, which
go some way to replacing FORALL.

Unlike HPF, the notation defined here forces communication operations
to be explicitly specified.  In that sense it is lower level than
HPF---closer to a run-time library.

The syntax is quite awkward in practise.  A big problem is still that
Java doesn't allow library-defined operator overloading, so expressions
quickly become difficult to read.


\section*{Index ranges}

\begin{itemize}
\item
An index range is specified by a member of the `Range' class.
\item
A ``primitive range'' is either collapsed (sequential),
or distributed over a particular dimension of a particular process array.
\begin{verbatim}
     Range x = new Range(100) ;
     Range y = new Range(50, BLK, p.dim(0)) ;
     Range z = new Range(50, BLK, p.dim(1)) ;
\end{verbatim}
\verb$x$ is collapsed.  \verb$y$ is distributed blockwise over the
first dimension of process array \verb$p$, \verb$z$ over the second.
\item
Two distributed primitive ranges are ``orthogonal'' if they are
distributed over different dimensions of the same process array.  A
collapsed primitive range is orthogonal to {\em any} primitive range
except itself.
\end{itemize}

\section*{Arrays}

\begin{itemize}
\item
The shape and mapping of an array are defined by an ordered list of
orthogonal index ranges.
\item
The types of array elements are restricted to one of the Java
primitive types (cf, F77).  There is a separate (sub)class of array
for each primitive type.
\begin{verbatim}
     ArrayInt a = new ArrayInt(x, y) ;
     ArrayFloat b = new ArrayFloat(y, x) ;
     ArrayDouble c = new ArrayDouble(y) ;
     ArrayDouble d = new ArrayDouble(z) ;
\end{verbatim}
\verb$a$ and \verb$b$ are rank 2.  \verb$c$ is rank 1.
\end{itemize}

\section*{Expressions}

\begin{itemize}
\item
An ``expression'' is an array expression.

An expression node may correspond to a complete temporary array
constructed at run-time, or through some process of interpretation
(akin to interpretation of the mooted of forall scripts) it may
simply correspond to a scalar temporary inside a loop in some
``node code''.

The classes for expressions parallel the classes for arrays:
\begin{verbatim}
     ExprInt, ExprFloat, ExprDouble, ...
\end{verbatim}
\item
The shape and mapping of an expression are defined by an {\em unordered
set} of orthogonal index ranges.
\item
An array is an expression.  It's shape and mapping are defined by
the set of ranges of the array.
\item
A range is an integer expression.  It's shape and mapping are
defined by the singleton set containing the range itself.
\item
Members on the expression class provide arithmetic, eg
\begin{verbatim}
     b.plus(c) 
\end{verbatim}
corresponds to the array expression
\begin{verbatim}
     b + c
\end{verbatim}
The shape of the result is the union of the shape of the addend
and the argument.  {\em The operation is illegal if this union contains
any non-orthogonal range pairs.}

Certain arithmetic coercions can be defined by overloading \verb$plus$, eg
\begin{verbatim}
     ExprInt   ExprInt :: plus(ExprInt) ;

     ExprFloat ExprInt :: plus(ExprFloat) ;

     ExprFloat ExprFloat :: plus(ExprFloat) ;

     ExprFloat ExprFloat :: plus(ExprInt) ;
\end{verbatim}
Other analogous members (\verb$times$, \verb$if$, and so on) are provided.
\end{itemize}

\section*{Simple operations on arrays}

\begin{itemize}
\item
An expression ``conforms'' with an array if its index range set
is a subset of the index range list of the array.
\item
Assignment is through through suitable members, eg
\begin{verbatim}
     void ArrayInt    :: assign(ExprInt) ;
     void ArrayFloat  :: assign(ExprFloat) ;
     void ArrayDouble :: assign(ExprDouble) ;
     ...
\end{verbatim}
   Eg,
\begin{verbatim}
     a.assign(b) ;    // a = b
     b.assign(c) ;    // b = c
\end{verbatim}
The argument of \verb$assign$ must conform with the array being assigned.
\begin{verbatim}
     c.assign(d) ;    // ILLEGAL
\end{verbatim}

\item
The fact that a range is an expression provides some of the power of
a ``forall'' statement\ldots
\begin{verbatim}
     a.assign(x.plus(y)) ;   // forall (x, y) a(x, y) = x + y ;
\end{verbatim}

\item
A masked assignment operation `where' could also be provided.
\end{itemize}

\section*{Communication}

\begin{itemize}
\item
The conformance rules for the previous operations mean no
communication is needed in their implementation.
\item
The array member \verb$remap$ takes an argument of the same {\em shape} as
the array (which does not, however, conform with the array) and
copies its value into the array.
\begin{verbatim}
     void ArrayInt    :: remap(ArrayInt) ;
     void ArrayFloat  :: remap(ArrayFloat) ;
     void ArrayDouble :: remap(ArrayDouble) ;
     ...
\end{verbatim}
   Eg
\begin{verbatim}
     c.remap(d) ;  // c = d
\end{verbatim}
This operation clearly {\em does} require communication.
\item
\verb$shift$ is similar to \verb$remap$, except that the argument {\em does}
conform with the array, but the copy is a shifted copy.

Again, communication is required.
\item
Other analogous members are provided.
\end{itemize}

\section*{Subranges and Array sections}

\begin{itemize}
\item
A ``subrange'' is a triplet subrange of some primitive range,
created by a suitable member function, eg
\begin{verbatim}
     x.sub(lb, ub, stride) ;
\end{verbatim}
The signature of \verb$sub$ would be
\begin{verbatim}
     Range Range :: sub(int, int, int) ;
\end{verbatim}
Subranges inherit the orthogonality properties of their parent
primitive range.
\item
A section of an array is created by passing subranges of the array's
range set to a suitable member, eg
\begin{verbatim}
    a.sect(x.sub(0, 99, 2), y) ;  // a(0 : 99 : 2, :)
\end{verbatim}
The signatures of `sect' would be
\begin{verbatim}
    ArrayInt ArrayInt :: sect(Range x) ;
    ArrayInt ArrayInt :: sect(Range x, Range y) ;
    ...
\end{verbatim}
\end{itemize}

\section*{Example}

     The HPF/F90 program\ldots
\begin{verbatim}
  integer n
  parameter(n = 8)

  real u(n, n)

  !hpf$ distribute u (block, block) onto p
  !hpf$ processors p (2, 2)

  integer i, j
  integer iter

  do i = 1, n
    do j = 1, n
      if(i == 1 .or. i == n .or. j == 1 .or. j == n) then
        u(i, j) = 1.0
      else
        u(i, j) = 0.0
      endif
    enddo
  enddo

  do iter = 1, 5
    u(2 : n - 1, 2 : n - 1) = &
        0.25 * (u(2 : n - 1, 1 : n - 2) + u(2 : n - 1, 3 : n) + &
                u(1 : n - 2, 2 : n - 1) + u(3 : n, 2 : n - 1))
  enddo

end
\end{verbatim}
could be translated as\ldots
\begin{verbatim}
  final integer n = 8 ;

  Procs p = new Procs(2, 2) ;

  Range x = new Range(n, BLK, p.dim(0)) ;
  Range y = new Range(n, BLK, p.dim(1)) ;

  ArrayFloat  u = new ArrayFloat(x, y) ;
  ArrayInt mask = new ArrayInt(x, y) ;

  mask = x.gt(0).and(x.lt(n - 1)).and(y.gt(0)).and(y.lt(n - 1)) ;

  u.where(mask, 0.0, 1.0) ;

  ArrayFloat tmp1 = new ArrayFloat(x, y) ;
  ArrayFloat tmp2 = new ArrayFloat(x, y) ;
  ArrayFloat tmp3 = new ArrayFloat(x, y) ;
  ArrayFloat tmp4 = new ArrayFloat(x, y) ;

  for(int iter = 1 ; iter <= 5 ; iter++) {
    tmp1.shift(u, -1, 0) ;
    tmp2.shift(u,  1, 0) ;
    tmp4.shift(u, -1, 1) ;
    tmp3.shift(u,  1, 1) ;

    u.where(mask, tmp1.plus(tmp2).plus(tmp3).plus(tmp4).
                       times(0.25)) ;

        // where(mask) u = 0.25 * (tmp1 + tmp2 + tmp3 + tmp4)
  }
\end{verbatim}
This assumes that the arithmetic members on arrays include boolean
arithmetic, and that two variants of masked assignment (\verb$where$) are
provided (one with two arguments corresponds to F90 simple WHERE;
one with three arguments corresponds to F90 WHERE/ELSEWHERE).

{\em Variation:} the \verb$where$ operation in the loop could be replaced
by use of sections\ldots
\begin{verbatim}
  Range i = x.sub(1, n - 2) ;  // subrange 1 : n - 2
  Range j = y.sub(1, n - 2) ;  // subrange 1 : n - 2

    ...

    u.sect(i, j).assign(tmp1.sect(i, j).plus(tmp2.sect(i, j)).
                   plus(tmp3.sect(i, j)).plus(tmp4.sect(i, j)).
                                                  times(0.25)) ;

        // u(2 : n - 1, 2 : n - 1) = 0.25 *
        //      (tmp1(2 : n - 1, 2 : n - 1) + 
        //       tmp2(2 : n - 1, 2 : n - 1) +
        //       tmp3(2 : n - 1, 2 : n - 1) +
        //       tmp4(2 : n - 1, 2 : n - 1))
\end{verbatim}
{\em Variation:} the \verb$shift$ operations could be replaced by \verb$remap$
operations\ldots
\begin{verbatim}
  ArrayFloat tmp1 = new ArrayFloat(i, j) ;
  ArrayFloat tmp2 = new ArrayFloat(i, j) ;
  ArrayFloat tmp3 = new ArrayFloat(i, j) ;
  ArrayFloat tmp4 = new ArrayFloat(i, j) ;

  ...

    tmp1.remap(u.sect(x.sub(2, n - 1), j)) ;
    tmp2.remap(u.sect(x.sub(0, n - 3), j)) ;
    tmp3.remap(u.sect(i, y.sub(2, n - 1))) ;
    tmp4.remap(u.sect(i, y.sub(0, n - 3))) ;

    // tmp3 = u(1 : n - 2, 2 : n - 1)
    // tmp2 = u(0 : n - 3, 1 : n - 2)
    // tmp1 = u(2 : n - 1, 1 : n - 2)
    // tmp4 = u(1 : n - 2, 0 : n - 3)

    u.sect(i, j).assign(tmp1.plus(tmp2).plus(tmp3).plus(tmp4).
                        times(0.25)) ;

        // u(2 : n - 1, 2 : n - 1) = 0.25 * 
        //                           (tmp1 + tmp2 + tmp3 + tmp4)
\end{verbatim}
This corresponds more directly to the original Fortran which uses
arithmetic on array sections, rather than shift operations.

\end{document}

