From lxm@alphard.npac.syr.edu Thu Apr 25 11:46 EDT 1996
Received: from alphard.npac.syr.edu (alphard.npac.syr.edu [128.230.14.30]) by postoffice.npac.syr.edu (8.7.5/8.7.1) with ESMTP id LAA03703 for <dbc@npac.syr.edu>; Thu, 25 Apr 1996 11:46:15 -0400 (EDT)
Received: (from lxm@localhost) by alphard.npac.syr.edu (8.7.5/8.7.1) id LAA09395; Thu, 25 Apr 1996 11:46:14 -0400 (EDT)
Date: Thu, 25 Apr 1996 11:46:10 -0400 (EDT)
From: Xiaoming Li <lxm@npac.syr.edu>
To: Bryan Carpenter <dbc@alphard.npac.syr.edu>
Message-ID: <Pine.3.89.9604251143.C9166-0100000@alphard.npac.syr.edu>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Content-Length: 5544
Status: RO


\documentstyle[11 pt]{article}

\textwidth=6.0in
\textheight=8.0in
\voffset=-0.5in
\hoffset=-0.5in

\begin{document}
\title{The HPF program template for FORALL statement compilation}

\author{NPAC PCRC Group}

\date{April 18, 1996}

\maketitle

\section*{First, some general thought}

\paragraph{Purpose:} providing a concrete and visible picture of what the FORALL
compilation effort should be responsible. 

The reason we start with such a ``template'' instead of a grammar
is two folded
\begin{itemize}
\item
I consider a grammar is not visible, though may be more precise.
\item
I consider a template view is easier to be used for testsuite
generation.
\end{itemize}

In this initial compilation effort, we only deal with some kind of FORALL 
statements, instead of general FORALL constructs. This agrees with our
primary objective: 
\begin{itemize}
\item
Testing the overall shape of our front-end. We need to see a streamlined
process from our front-end: take an HPF program as input, convert it into
an internal representation, (do some transformation on the IR), unparse
the transformed IR to Fortran 77 source program. 
\item
Identifying detailed issues in further compiler and runtime development,
and their coordination. Conceptually, this has been done, but we need
detailed understanding from implementation point of view by streamlining
a process: have a non trivial HPF program compiled into a node program, 
linked to required runtime functions, run on a real parallel
architecture.
\end{itemize}

I consider three levels of testing (corresponding to three sets of
testing programs.

\begin{enumerate}
\item
One index variable, main program only. This test is for primary
compilation issues such as 
\begin{itemize}
\item
Operations on internal representation of a program.
\item
Data distribution directive processing
\item
Runtime functions
\item
Temporary storage allocation scheme.
\end{itemize}
\item
One index variable, subprogram included. This test is mainly
for INHERIT directive, which is considered a strong point of
our DAD specification.
\item
Two non-coupled index variables, subprogram included. If we
can do this, some useful programs (such as Jacobi iteration)
may be handled by the compiler.
\end{enumerate}

\section*{Level one template}

The following would be a sample level one testing program.

\begin{verbatim}
       PROGRAM MAIN
       REAL X(2:99), Y(100)
 !HPF$ PROCESSORS P(4)
 !HPF$ TEMPLATE TX(400),TY(-200:199)
 !HPF$ DISTRIBUTE TX(BLOCK) ONTO P
 !HPF$ DISTRIBUTE TY(BLOCK) ONTO P
 !HPF$ ALIGN X(i) WITH TX(2*i+1)   
 !HPF$ ALIGN Y(i) WITH TY(3*i-50)

       FORALL (i=2:99) X(i) = 0
       FORALL (i=1:100) Y(i) = i

       FORALL (i=2:99) X(i) = Y(i+1) + Y(i-1)

       PRINT *, (X(i),i=2,99)       
       END
\end{verbatim}

\paragraph{Variations}
\begin{itemize}
\item
All constants may be changed, including those implied '1' or '0' in the
above sample. In particular, shapes of X and Y or 
TX and TY may not be the same.
\item
Distribution mode may be changed. In particular, one array may be
BLOCK-distributed, while the other CYCLIC-distributed.
\item
More FORALL statements of the same nature may repeat.
\end{itemize}

\paragraph{Constraints}
\begin{itemize}
\item
Only two arrays may be involved in a FORALL statement.
\item
The number of terms at right hand side of the assignment statement
may not be more than 3.
\item
If the array appearing at left hand side also appears at right hand side,
it should have the same subscript expression.
\end{itemize}

\section*{Level two template}
We include subroutine processing in this level of testing.
A sample program is as:
\begin{verbatim}
      PROGRAM MAIN
      REAL X(2:99), Y(100)
!HPF$ PROCESSORS P(4)
!HPF$ TEMPLATE TX(400),TY(-200:199)
!HPF$ DISTRIBUTE TX(BLOCK) ONTO P
!HPF$ DISTRIBUTE TY(BLOCK) ONTO P
!HPF$ ALIGN X(i) WITH TX(2*i+1) 
!HPF$ ALIGN Y(i) WITH TY(3*i-50)

      FORALL (i=2:99) X(i) = 0
      FORALL (i=1:100) Y(i) = i

      FORALL (i=2:99) X(i) = Y(i+1) + Y(i-1)

      CALL FOO(X(2:98:2),Y(1:99:2))
      CALL FOO(X(3:99:2),Y(2:100:2))

      PRINT *, (X(i),i=2,99)
      END

      SUBROUTINE FOO(X,Y)
      REAL X(49), Y(50)
!HPF$ INHERIT X,Y

      FORALL (i=1:49) X(i) = X(i) - Y(i) - Y(i+1)

      RETURN
      END
\end{verbatim}

\paragraph{Variations}
The same variations for level one testing apply. In addition,
local arrays in subprogram may be declared and distributed.

\paragraph{Constraints}
The same constraints for level one testing apply. 

\section*{Level three template}
We allow two-dimensional arrays in this level.
A sample program is as:
\begin{verbatim}
      PROGRAM MAIN
      PARAMETER (N=100)
      REAL X(N,N), Y(N,N)
!HPF$ PROCESSORS P(4)
!HPF$ TEMPLATE TX(200,200),TY(100,100)
!HPF$ DISTRIBUTE TX(BLOCK,*) ONTO P
!HPF$ DISTRIBUTE TY(BLOCK,*) ONTO P
!HPF$ ALIGN X(i,j) WITH TX(2*i,2*j)
!HPF$ ALIGN Y(i,j) WITH TY(i,j)

      FORALL (i=1:N,j=1:100) X(i) = 0
      FORALL (i=1:100,j=1:N) Y(i) = i + j

      FORALL (i=26:50,j=26:50) X(i,j) = Y(i+1) + Y(j+1)
      FORALL (i=1:100:2,j=1:N:2,X(i,j)/=0) X(i,j) = 1

      CALL FOO(X(1:100:2,1))

      PRINT *, (X(i,1),i=1,100,2)
      END

      SUBROUTINE FOO(X)
      REAL X(50)
!HPF$ INHERIT X
      REAL Y(50)
!HPF$ PROCESSORS P(4)
!HPF$ DISTRIBUTE Y(BLOCK) ONTO P

      FORALL (i=1:50) Y(i) = 2
      FORALL (i=1:50) X(i) = Y(i) + 1

      RETURN
      END
\end{verbatim}

The same variations and constraints as for level two apply.

\end{document}

----------
Xiaoming Li    (315)443-3890 (o)
NPACT          (315)443-1973 (f)


