
\documentstyle[11 pt]{article}
\textwidth=6.0in
\textheight=8.0in
\voffset=-0.5in
\hoffset=-0.5in

\begin{document}

\title{An HPF Program Generator for Testing HPF Compilers}

\author{Xiaoming Li}


\maketitle

\section*{Background}

As a guideline for our initial compilation effort, we have proposed 
a three HPF program templates, presenting different levels of
complexities and HPF features \cite{forall:3}. This work can be seen as 
an extension of 
that proposal. More specifically, we provide a design of an HPF
program generator based on the templates. Programs produced by
this generator will serve as a handy tester for our HPF compiler
and runtime system (in fact, they can be used to test any HPF compilation 
system for its performance on FORALL statement handling).

\section*{Basic considerations}

The first requirement for the generator is that it should
produce valid HPF program together with expected output after
running this program. The output is important --- we should at least
know whether the program out of our compiler can produce correct result.
(It may not be necessary in NPAC, though, since NPAC has a few
commercial HPF compilers which may be used as comparison basis, namely
we may run the HPF program produced by the generator with a commercial
compiler and see what output is.)

We decide the second requirement for the generator is to allow user
to specify communication patterns that must be observed from the
generated program. Doing this, we may further investigate the quality of
our compiler/runtime, in terms of the performance of executables produced
by the compiler. 

As studied in an early document \cite{forall:1}, communication patterns
involved in FORALL statement are classified in three categories, which
set up a basis for the optimization performed by our compiler/runtime
system. Thus, we allow user to specify the following to the generator.

\begin{itemize}
\item
No communication.
\item
Shift communication only.
\item
Remap communication only.
\item
Both shift and remap communications are needed.
\end{itemize}

Nevertheless, we shall enforce these requirements to their full extent
only for level 1 template. For level 2 and level 3, we enforce them
only for FORALL statement in main program. The rationals behind this
decision is: the main points of level 2 and level 3  are
not communication patterns in the subroutines, thus it may not be worth
to make effort to enforce the requirement thoroughly.

The basic approach I am taking to program the generator is
\begin{itemize}
\item
Identify changeable parameters in the templates.
\item
Figure out the constraints among those parameters, based on the
requirement of being a valid HPF program and that specified by the 
user. These constraints usually results in a set of inequalities.
\item
Realize the inequalities by setting proper values for those parameters.
\end{itemize}

\section*{Derivations}

In this section, we formulate the constraints among changeable
parameters in the templates level by level. For each level, we
first list the template with changeable parameters identified by {\em
emphasized} font, then layout a set of inequalities those parameters 
must meet.

\subsection*{Level 1}

\begin{small}
\begin{tabbing}
~~~~~~~~~~ \= ~~~~~~~~~~ \\
\> PROGRAM MAIN \\
\> REAL X({\em lx:ux}), Y({\em ly:uy}) \\
!HPF\$ \>PROCESSORS P({\em p}) \\
!HPF\$ \>TEMPLATE TX({\em ltx:utx}),TY({\em lty:uty}) \\
!HPF\$ \>DISTRIBUTE TX({\em d1}) ONTO P \\
!HPF\$ \>DISTRIBUTE TY({\em d2}) ONTO P \\
!HPF\$ \>ALIGN X(i) WITH TX({\em ax}*i+{\em bx}) \\
!HPF\$ \>ALIGN Y(i) WITH TY({\em ay}*i+{\em by}) \\

\> FORALL (i={\em lx:ux}) X(i) = 0 \\
\> FORALL (i={\em ly:uy}) Y(i) = i \\ \\

\> FORALL (i={\em l:u:s}) X(i) = Y({\em a1}*i+{\em b1}) + 
                                 Y({\em a2}*i+{\em b2}) \\ \\

\> PRINT *, (X(i),i={\em lx,ux}) \\
\> END 
\end{tabbing}
\end{small}

We see 22 changeable parameters in this template.
For ease of reference, I list them below.
\begin{small}
\begin{verbatim}
   lx, ux; ly, uy
   p
   ltx, utx; lty, uty   (with tx = utx-ltx+1, ty = uty-lty+1)
   d1, d2
   ax, bx; ay, by
   l, u, s
   a1, b1; a2, b2   
\end{verbatim}
\end{small}

For the program being a valid HPF program, the following
two conditions must be met (we use {\em a} and {\em b} in place
of {\em a1, a2} and {\em b1, b2} in the formulas, respectively.

\paragraph{within-array-bound condition:}
\begin{equation}
lx \leq l < u \leq ux; ~~~ ly \leq a*l+b < a*u+b \leq uy
\end{equation}

\paragraph{within-template-bound condition:}
\begin{equation}
\begin{array}{c}
ltx \leq ax*lx+bx < ax*ux+bx \leq utx; \\
lty \leq ay*ly+by < ay*uy+by \leq uty
\end{array}
\end{equation}

These two sets of condition give rise to the following inequalities.

\begin{equation}
\frac{ltx-bx}{ax} \leq lx \leq l, ~and~~ \frac{lty-by}{ay} \leq ly
\leq a*l+b
\label{ineq:3}
\end{equation}

For the program satisfying the communication requirement set by
the user, the following two conditions play essential roles. 

\paragraph{shift-homomorphic condition: \\} 
\begin{itemize}
\item For BLOCK distribution.
\begin{equation}
\frac{ax}{ay*a} = \frac{tx}{ty}
\end{equation}

\item For CYCLIC distribution.
\begin{equation}
ax*s \equiv ay*a*s ~~(mod ~p)
\end{equation}
\end{itemize}

\paragraph{canonical-equal-element condition:\\} 
\begin{itemize}
\item For BLOCK distribution.
\begin{equation}
(a*l+b)*ay+by-lty+1 = \lceil(ax*l+bx-ltx+1)\frac{ay*a}{ax}\rceil
\end{equation}

\item For CYCLIC distribution.
\begin{equation}
(a*l+b)*ay+by-lty \equiv (ax*l+bx-ltx) ~~(mod ~p)
\end{equation}
\end{itemize}

Notice that the communication requirement is only associated with the 
third FORALL statement in the template, we conclude the following:

\begin{itemize}
\item No communication --- both terms at rhs of the FORALL statement
      satisfy both "shift-homomorphic" and "equal-element" conditions.
\item Shift communication only --- both terms at rhs of the FORALL
      statement satisfy "shift-homomorphic" condition, but not "equal-element" 
      conditions.
\item Remap communication only --- both terms at rhs of the FORALL statement
      satisfy neither "shift-homomorphic" nor "equal-element" conditions.
\item Shift and remap communication --- one term at rhs of the FORALL
      statement satisfies the "shift-homomorphic" condition, the other
      does not.
\end{itemize}

See \cite{forall:1} for reasoning. As programming goes, it is a 
heuristic process of determining the parameters one by one, observing
the above conditions. Sequence of these parameters in the process
is of importance. For instance, we determine lx after ax, bx, l, and
ltx have been determined. Noticing the above inequality \ref{ineq:3},
we must make sure there is room left between $\frac{ltx-bx}{ax}$ and
$l$ when assigning values to the four parameters. 


\paragraph{Level 2}
\begin{small}
\begin{tabbing}
~~~~~~~~~~ \= ~~~~~~~~~~ \\
\>PROGRAM MAIN \\
\>REAL X({\em lx:ux}), Y({\em ly:uy}) \\
!HPF\$ \> PROCESSORS P({\em p}) \\
!HPF\$ \> TEMPLATE TX({\em ltx:utx}),TY({\em lty:uty}) \\
!HPF\$ \> DISTRIBUTE TX({\em d1}) ONTO P \\
!HPF\$ \> DISTRIBUTE TY({\em d2}) ONTO P \\
!HPF\$ \> ALIGN X(i) WITH TX({\em ax}*i+{\em bx}) \\
!HPF\$ \> ALIGN Y(i) WITH TY({\em ay}*i+{\em by}) \\

\>    FORALL (i={\em lx:ux}) X(i) = 0 \\
\>    FORALL (i={\em ly:uy}) Y(i) = i \\

\>    FORALL (i={\em l:u:s}) X(i) = Y({\em a1}*i+{\em b1}) + 
             Y({\em a2}*i+{\em b2}) \\

\>    CALL FOO(X({\em lxs1:uxs1:sxs1}),Y({\em lys1:uys1:sys1})) \\
\>    CALL FOO(X({\em lxs2:uxs2:sxs2}),Y({\em lys2:uys2:sys2})) \\

\>    PRINT *, (X(i),i={\em lx,ux}) \\
\>    END \\

\>    SUBROUTINE FOO(X,Y) \\
\>    REAL X({\em slx:sux}), Y({\em sly:suy}) \\
!HPF\$ \> INHERIT X,Y \\

\>    FORALL (i={\em sl:su:ss}) X(i) = X(i) - Y(i) - Y(i+1) \\

\>    RETURN \\
\>    END
\end{tabbing}
\end{small}

This template is just a simple extension from level 1 by adding the
calls to a subroutine and a trivial subroutine with one FORALL
statement. The purpose of this template is to test how INHERIT
directive is processed by a compiler. (We note, DEC HPF compiler
requires {\em assumed-shape} for a dummy array to have INHERIT
attribute, though HPF 1.0 spec does not claim such an requirement.)

We identify the additional variables and constraints that 
must be met. The following additional variables correspond to
the triplets involved in the CALL statements.
\small
\begin{verbatim}
      lxs1,uxs1,sxs1; lys1,uys1,sys1
      lxs2,uxs2,sxs2; lys2,uys2,sys2
      slx, sux; sly, suy; sl, su, ss
\end{verbatim}
\normalsize

They should satisfy the following additional conditions.
\begin{equation}
\begin{array}{c}
lx \leq lxs1 < uxs1 \leq ux, ~~ly \leq lys1 < uys1 \leq uy \\
lx \leq lxs2 < uxs2 \leq ux, ~~ly \leq lys2 < uys2 \leq uy 
\end{array}
\end{equation}

and
\begin{equation}
\begin{array}{c}
\frac{uxs1-lxs1}{sxs1} = \frac{uxs2-lxs2}{sxs2} = sux-slx, \\
\frac{uys1-lys1}{sys1} = \frac{uys2-lys2}{sys2} = suy-sly, \\
max(slx,sly) \leq sl < su \leq min(sux,suy-1) 
\end{array}
\end{equation}

The second set of conditions is needed since we are using the
same subroutine twice.

For the subroutine FOO, we adjust sizes of the arrays and FORALL
index range based on the above conditions. In particular, we
must ensure the range of FORALL does not cause out-of-bound
array access.

\paragraph{Level 3}

\begin{small}
\begin{tabbing}
~~~~~~~~~~ \= ~~~~~~~~~~ \\
\>PROGRAM MAIN \\
\>REAL X(lx1:ux1,lx2:ux2), Y(ly1:uy1,ly2:uy2) \\
!HPF\$ \> PROCESSORS P({\em p}) \\
!HPF\$ \> TEMPLATE TX({\em ltx1:utx1},{\em ltx2:utx2}),
                  TY({\em lty1:uty1},{\em lty2:uty2}) \\
!HPF\$ \> DISTRIBUTE TX({\em d[0],d[1]}) ONTO P \\
!HPF\$ \> DISTRIBUTE TY({\em d[2],d[3]}) ONTO P \\
!HPF\$ \> ALIGN X(i,j) WITH 
         TX({\em ax1}*i+{\em bx1},{\em ax2}*j+{\em bx2}) \\
!HPF\$ \> ALIGN Y(i,j) WITH 
         TY({\em ay1}*i+{\em by1},{\em ay2}*j+{\em by2}) \\

\>    FORALL (i={\em lx1:ux1},j={\em lx2:ux2}) X(i) = 0 \\
\>    FORALL (i={\em ly1:uy1},j={\em ly2:uy2}) Y(i,j) = i + j \\
\>    FORALL (i={\em l1:u1:s1},j={\em l2:u2:s2}) X(i,j) = Y(i+1,j) + Y(i,j+1) \\
\>    FORALL (i={\em lx1:ux1}:2,j={\em lx2:ux2}:2,X(i,j)/=0) X(i,j) = 1 \\

\>    CALL FOO(X({\em lxs1:uxs1:sxs1},{\em lxs2:uxs2:sxs2})) \\

\>    PRINT *, (X(i,1),i={\em lx1,ux1},2) \\
\>    END \\ \\

\>    SUBROUTINE FOO(X) \\
\>    REAL X({\em slx:sux}) \\
!HPF\$ \> INHERIT X \\
\>    REAL Y({\em sly:suy}) \\
!HPF\$ \> PROCESSORS P({\em p}) \\
!HPF\$ \> DISTRIBUTE Y({\em d[4]}) ONTO P \\

\>    FORALL (i={\em sly:suy}) Y(i) = 2 \\
\>    FORALL (i={\em sl:su}) X(i) = Y(i) + 1 \\

\>    RETURN \\
\>    END 
\end{tabbing}
\end{small}

This template contains  48 adjustable parameters.

\begin{small}
\begin{verbatim}
   lx1,ux1,lx2,ux2; ly1,uy1,ly2,uy2
   p
   ltx1,utx1,ltx2,utx2; lty1,uty1,lty2,uty2
   d[0], d[1], d[2], d[3], d[4]
   ax1,bx1,ax2,bx2
   ay1,by1,ay2,by2
   l1,u1,s1,l2,u2,s2
   lxs1,uxs1,sxs1,lxs2,uxs2,sxs2
   slx,sux, sly,suy
   sl,su
\end{verbatim}
\end{small}

We impose some constraints on the parameters.
\begin{itemize}
\item One of d[0] and d[1] must be 3 (for *); so must be one of d[2] and d[3];
\item One of lxs1:uxs1:sxs1 and lxs2:uxs2:sxs2 must be scalar ---
      we emphasize how to pass array slices to subroutines.
\end{itemize}

The following two conditions must be met for a generated program
to be valid.

\paragraph{within-array-bound-condition:}
\begin{equation}
\begin{array}{c}
lx1 \leq l1 < u1 \leq ux1; ~~~ lx2 \leq l2 < u2 \leq ux2; \\
ly1 \leq l1 < u1+1 \leq uy1; ~~~ ly2 \leq l2 < u2+1 \leq uy2
\end{array}
\end{equation}

\begin{equation}
lx1 \leq lxs1 < uxs1 \leq ux1; ~~~ lx2 \leq lxs2 < uxs2 \leq ux2; \\
\end{equation}

\paragraph{within-template-bound-condition:}
\begin{equation}
\begin{array}{c}
ltx1 \leq ax1*lx1+bx1 < ax1*ux1+bx1 \leq utx1; \\
ltx2 \leq ax2*lx2+bx2 < ax2*ux2+bx2 \leq utx2; \\
lty1 \leq ay1*ly1+by1 < ay1*uy1+by1 \leq uty1; \\
lty2 \leq ay2*ly2+by2 < ay2*uy2+by2 \leq uty2
\end{array}
\end{equation}

\section*{Results}

We have finished the initial development of three programs that
the HPF program generator consists of. And we use DEC HPF compiler
to check if the generated programs are valid. We have found that
the HPF programs generated corresponding level 1 template have
no problem to be compiled and run with DEC HPF compiler. Outputs
are correct. But we have some problem with DEC HPF compiler
with regard to level 2 and level 3 template. Firstly, DEC compiler
requires {\em assumed-shape} for dummy array to have INHERIT
attribute, though HPF 1.0 does not require. Secondly, DEC compiler
seems not able to handle INHERIT directive, even if we specify
dummy array with assumed-shape. The symptom is: when we run the
executables produced from DEC compiler, they do not
generate any output for level 2 and level 3 programs.

\section*{Programming notes}

As mentioned early, programming such a generator is a heuristic
process. While we have some inequalities to be met, the fact that
there are many more variabls than inequalities in the system 
provides a rich selection domain for how things may be done.
In what follows, I give a detail description on the heuristics
for the case of no communication (the most difficult case).

First of all, we note that the variables are not of equal
importance. For instance, {\tt p, l, u}, and {\tt s} are of
particular importance, since they determine how much computation
is involved in the program. Others, such as {\tt lx, ltx, ...},
have only cosmetic effects.

The difficult part is to meet inequality (3) and equation (6)
simultaneously, after selecting all related variables, except
for {\tt ltx, bx, lty}, and {\tt by}. Here is my heuristics:

To make life easy, suppose {\tt bx-ltx+1} is a multiple of {\tt ax},
say $bx-ltx+1 = m*ax$. Then (6) becomes
\begin{equation}
by-lty+1 = (l+m)*ay*a - (a*l+b)*ay
\end{equation}

From inequality (3), we must have
\begin{equation}
bx-ltx+1 > -lx*ax + 1, ~~~by-lty+1 > -ly*ay + 1
\end{equation}

The first inequality above suggests $m \geq -lx+1$. And teh second one
suggests we must have
\begin{equation}
m > \frac{-ly*ay+1+(a*l+b)*ay}{ay*a} - l
\end{equation}

Once we pick an {\tt m} that meets the above requirement, we then
are safe to pick proper values for {\tt ltx, bx, lty}, and {\tt by}
that make (3) and (6) hold simultaneously.

For the case of CYCLIC distribution, our strategy is to let both
sides of (7) be multiples of p, respectively. This way, code is
much clearer.

\section*{Findings after meeting of July 1}

Thanks to Tom, we identified two problems associated with
our level 2 and level 3 programs.
\begin{itemize}
\item
Subroutines with assumed-shape arrays as dummy argument should have 
explicit interface specified in calling program, see page 531 of
\cite{f90:2} for detailed information.
\item
DEC HPF compiler apparently has some problem in handling ALGIN
directive or INHERIT directive --- it does not like 
\begin{small}
\begin{verbatim}
       !HPF$ ALIGN X(i) WITH TX(2*i+1)
\end{verbatim}
\end{small}
if a section of X is passed to some dummy with INHERIT attribute.
It is OK if we change {\tt TX(2*i+1)} to {\tt TX(i+1)}.
\end{itemize}

Our generator programs have been modified to reflect the above
observations.

\begin{thebibliography}{99}
\bibitem{forall:1}
Xiaoming Li, "Efficient compilation of FORALL statement with runtime,"
NPAC Technical Report, SCCS 77x, March 20, 1996.

\bibitem{forall:3}
Xiaoming Li, "The HPF program template for initial FORALL statement 
compilation," NPAC internal Technical Report, SCCS 77x, April 20, 1996.

\bibitem{f90:2}
Jeanne C. Adams, Walter S. Brainerd, Jeanne T. Martin, et al, Fortran 90
Handbook. McGraw-Hill Book Company, 1992.

\end{thebibliography}
\end{document}
