
\section{Model}

We consider the following canonical form

\begin{verbatim}
   FORALL (i=l:u:s) X(a0*i+b0) = Y(a1*i+b1)
\end{verbatim}

where X and Y are distributed onto the same processor grid (assume $p$
processors, numbered as 0, 1, ..., p-1) by HPF directives.
More specifically, we observe the following attributes pertaining to
X and Y.

\begin{center}
\begin{tabular}{l l l} \hline
dimension: & $X(l_x:u_x)$ & $Y(l_y:u_y)$ \\
template:  & $T_x(l_{tx}:u_{tx})$ & $T_y(l_{ty}:u_{ty})$ \\
alignment: & $(a_x*i+b_x)$  & $(a_y*i+b_y)$ \\
distribution: & $d_x$ & $d_y$ \\ \hline
\end{tabular}
\end{center}

This is a 22 variable system, where 
   $l, u, s, a_0, b_0, a_1, b_1, p, l_x, u_x, l_y, u_y, l_{tx}, u_{tx}, 
l_{ty}, u_{ty}, a_x, b_x,$ $ a_y, b_y$ are integer variables and 
$d_x, d_y$ are either
{\tt BLOCK} or {\tt CYCLIC}. 

Let $t_x = u_{tx} - l_{tx}+1$, the {\em declared size} of template $T_x$, 
and we call $\overline{t_x} = \lceil\frac{t_x}{p}\rceil\cdot p$ the {\em
effective size} of it, i.e. each of the p processors actually allocates
$\overline{t_x}/p$ storage for local array X. A similar statement goes for
$T_y$.

When we say ``variables'' in the above, we mean they can actually be
variables defined in source program so that their values may not
be determined at compile time, for instance, input when program is
running, or dummies in subprograms.

For convenience of illustration, we shall use a table similar to
the above table to represent
a piece of HPF program that involves one FORALL statement. For example,
the following program

\small
\begin{verbatim}
       REAL X(80), Y(100)
!HPF$  PROCESSORS P(4)
!HPF$  TEMPLATE TX(200), TY(300)
!HPF$  ALIGN X(i) WITH TX(2*i+5)
!HPF$  ALIGN Y(i) WITH TY(3*i-1)
!HPF$  DISTRIBUTE TX(BLOCK) ONTO P
!HPF$  DISTRIBUTE TY(CYCLIC) ONTO P
       FORALL (i=-1:30:2) X(2*i+5) = Y(3*i+10)
       END
\end{verbatim}
\normalsize

will be identified as

\begin{center}
\begin{tabular}{l l l} \hline
4;~~ -1:30:2 & X(2*i+5) & Y(3*i+10) \\ \hline
dimension: & X(1:80) & Y(1:100) \\
template:  & Tx(1:200) & Ty(1:300) \\
alignment: & (2*i+5)  & (3*i-1) \\
distribution: & BLOCK & CYCLIC \\ \hline
\end{tabular}
\end{center}

The task is to design a scheme that turns this FORALL statement
to an SPMD node program segment, such that a collective execution of multi
copies of the node program achieves the same semantic effect of the FORALL
statement.

What we are interested is communication patterns that may present in such a
FORALL statement. For instance,

\begin{center}
\begin{tabular}{l l l} \hline
8;~~ 0:28:2 & X(i) & Y(2*i+13) \\ \hline
dimension: & X(-5:77) & Y(4:127) \\
template:  & Tx(1:1328) & Ty(1:664) \\
alignment: & (4*i+21)  & (i+8) \\
distribution: & BLOCK & BLOCK \\ \hline
\end{tabular}
\end{center}

has no communication need, while

\begin{center}
\begin{tabular}{l l l} \hline
8;~~ 0:10:3 & X(i) & Y(i+15) \\ \hline
dimension: & X(-9:83) & Y(6:91) \\
template:  & Tx(1:186) & Ty(1:190) \\
alignment: & (2*i+20)  & (2*i+8) \\
distribution: & CYCLIC & CYCLIC \\ \hline
\end{tabular}
\end{center}

needs a shift type communication, and

\begin{center}
\begin{tabular}{l l l} \hline
8;~~ 6:271:4 & X(i) & Y(2*i-2) \\ \hline
dimension: & X(0:341) & Y(3:859) \\
template:  & Tx(-2:362) & Ty(7:1788) \\
alignment: & (i+7)  & (2*i+3) \\
distribution: & BLOCK & CYCLIC \\ \hline
\end{tabular}
\end{center}

needs some 'chaotic' communication, which we shall refer as {\em remap}
communication. The core of this paper is a development of an algorithm that
distinguish the above three types of communication patterns. The idea behind
this distinction is
\begin{itemize}
\item[-] For {\em no communication}, our node program should result in no
data movement in runtime.
\item[-] For {\em shift communication}, a ghostarea support will reduce
runtime data movement to minimum.
\item[-] For {\em remap communication}, a general data movement runtime 
routine, {\em remap()}, is supplied to handle this case. Optimization
is achived in the design and implementation of this runtime routine.
\end{itemize}

One possible question is: why just three ? can we further break down the
case {\em remap} ? Our understanding is: possible, but may not be worthy
the effort.

Using {\em owner computes} rule, we see the node program segment
corresponding to the FORALL statement might be reasonablly generated 
by the following 
procedure: (we assume some runtiem support, but no ghostarea support.)

\begin{enumerate}
\item
Insert a call to runtime function as
\small
\begin{verbatim}
      CALL loop_bounds(dad_x,1,l,u,s,ll,lu,ls)
\end{verbatim}
\normalsize
where {\em dad\_x} is a descriptor for distributed array X.
\item 
Check if communication is detectable. Communication is
detectable if all the above 22 parameters are constants. If not
detectable, go to 6.
\item
Detect communication pattern between arrays X and Y under this
FORALL statement. If {\em shift communication} is detected, the
shift {\em amount} is also determined.
\item
If {\em no communication}, insert
\small
\begin{verbatim}
      CALL coef(dad_y,1,l,u,s,a1,b1,0,u,v)
      DO i = ll,lu,ls
         X(i) = Y(u*i+v)
      END DO
\end{verbatim}
\normalsize
where {\em dad\_y} is a descriptor for distributed array Y.
\item
Else if {\em shift communication}, insert
\small
\begin{verbatim}
      tshift(dad_tmpy, dad_y, 1, amount)
      CALL coef(dad_tmpy,1,l,u,s,a1,b1,amount,u,v)    
      DO i = ll,lu,ls
         X(i) = tmpy(u*i+v)
      END DO
\end{verbatim}
\normalsize
where {\em dad\_tmpy} is a descriptor for some temporary storage
distributed the same as Y.
\item
Else {\em remap communication} is needed, insert
\small
\begin{verbatim}
      remap(dad_tmpx, dad_y)
      DO i = ll,lu,ls
         X(i) = tmpx(i)
      END DO
\end{verbatim}
\normalsize
where {\em dad\_tmpx} is a descriptor for some temporary storage
distributed the same as X.
\end{enumerate}

The above procedure has some small problem, since coefficient u and v
so calculated may not be integers, though u*i+v for effective value of
i is always integer. Thus, an alternative is the following:

\begin{enumerate}
\item
Insert a call to runtime function as
\small
\begin{verbatim}
      CALL loop_upper_bound(dad_x,1,l,u,s,ub)
\end{verbatim}
\normalsize
where {\em dad\_x} is a descriptor for distributed array X.
\item 
Check if communication is detectable. Communication is
detectable if all the above 22 parameters are constants. If not
detectable, go to 6.
\item
Detect communication pattern between arrays X and Y under this
FORALL statement. If {\em shift communication} is detected, the
shift {\em amount} is also determined.
\item
If {\em no communication}, insert
\small
\begin{verbatim}
      CALL coef(dad_x,1,l,u,s,a0,b0,0,u0,v0)
      CALL coef(dad_y,1,l,u,s,a1,b1,0,u1,v1)
      DO i = 0, ub
         X(u0*i+v0) = Y(u1*i+v1)
      END DO
\end{verbatim}
\normalsize
where {\em dad\_y} is a descriptor for distributed array Y.
\item
Else if {\em shift communication}, insert
\small
\begin{verbatim}
      tshift(dad_tmpy, dad_y, 1, amount)
      CALL coef(dad_x,1,l,u,s,a0,b0,0,u0,v0)    
      CALL coef(dad_tmpy,1,l,u,s,a1,b1,amount,u,v)    
      DO i = 0, ub
         X(u0*i+v0) = tmpy(u1*i+v1)
      END DO
\end{verbatim}
\normalsize
where {\em dad\_tmpy} is a descriptor for some temporary storage
distributed the same as Y.
\item
Else {\em remap communication} is needed, insert
\small
\begin{verbatim}
      remap(dad_tmpx, dad_y)
      CALL coef(dad_x,1,l,u,s,a0,b0,0,u0,v0)    
      DO i = 0, ub
         X(u0*i+v0) = tmpx(u0*i+v0)
      END DO
\end{verbatim}
\normalsize
where {\em dad\_tmpx} is a descriptor for some temporary storage
distributed the same as X.
\end{enumerate}

This time, every u and v are integers. Nevertheless, one might
prefer the following:

\begin{enumerate}
\item
Insert a call to runtime function as
\small
\begin{verbatim}
      CALL loop_bounds(dad_x,1,l,u,s,ll,lu,ls)
\end{verbatim}
\normalsize
where {\em dad\_x} is a descriptor for distributed array X.
\item 
Check if communication is detectable. Communication is
detectable if all the above 22 parameters are constants. If not
detectable, go to 6
\item
Detect communication pattern between arrays X and Y under this
FORALL statement. If {\em shift communication} is detected, the
shift {\em amount} is also determined.
\item
If {\em no communication}, insert
\small
\begin{verbatim}
      CALL loop_bounds(dad_y,1,l,u,s,lly,luy,lsy)
      iy = lly
      DO i = ll,lu,ls
         X(i) = Y(iy)
         iy = iy + lsy
      END DO
\end{verbatim}
\normalsize
where {\em dad\_y} is a descriptor for distributed array Y.
\item
Else if {\em shift communication}, insert
\small
\begin{verbatim}
      tshift(dad_tmpy, dad_y, 1, amount)
      CALL loop_bounds(dad_tmpy,1,l,u,s,lltmpy,lutmpy,lstmpy)
      itmpy = lltmpy
      DO i = ll,lu,ls
         X(i) = tmpy(itmpy)
         itmpy = itmpy + lstmpy
      END DO
\end{verbatim}
\normalsize
where {\tt dad\_tmpy} is a descriptor for some temporary storage
distributed the same as Y.
\item
Else {\em remap communication} is needed, insert
\small
\begin{verbatim}
      remap(dad_tmpx, dad_y)
      DO i = ll,lu,ls
         X(i) = tmpx(i)
      END DO
\end{verbatim}
\normalsize
where {\em dad\_tmpx} is a descriptor for some temporary storage
distributed the same as X.
\end{enumerate}

\paragraph{}
There are three issues here

\begin{itemize}
\item
Determine local loop bounds {\tt ll,lu}, and {\tt ls} or determine the
local upper bound {\tt lu}.
\item
Detect communication at compiler time, and generate appropriate 
communication calls in node program, if needed.
\item
Figure out coefficients u and v.
\end{itemize}

To facilitate communication, we have assumed the following two 
routines in runtime system.

\begin{itemize}
\item
{\tt tshift: } shift the distributed array Y to some temporary TMPY
by certain displacement, which has the same shape and distribution as Y.
\item
{\tt remap: } remap elements of Y that are involved in the FORALL
to a temporary TMPX, which has the same distribution as X.
\end{itemize}

As it will become clear later, the {\tt tshift } function is to shift 
the Y array in terms of TEMPLATE positions, instead of global array element
positions as for CSHIFT or EOSHIFT in Fortran 90. 

\paragraph{Example. } Consider the following case.

If we have the corresponding X array  elements and Y array elements
distributed in the following pattern.

\begin{verbatim}
   X:    processor 0                        processor 1
      ____________________              _____________________
      |* . . * . . * . . |              | * . . * . . . . . |
      --------------------              ---------------------

   Y:    processor 0                      processor 1
      ________________________          _________________________
      |. . . . * . . . * . . |  <===    | . * . . . * . . . * . |
      ------------------------          -------------------------
\end{verbatim}

When implementing the forall assignment in our model, we will keep the left
hand side clause unmoved. That means they will not be moved into a
temporary buffer and the operation will be directly on  the local array.
Apply this assumption to the above case, we just move the global template
of Y array one position from right to left, then Y array elements will have
the same shape and distribution as the corresponding X array elements. So
in this case, we only need to shift the template of Y array to complete the
operation and keep the X array unmoved. This is different from the shift
communication on Y array elements, and actually that is not able to
implement this.

The {\tt remap } function is to change the shape and distribution of Y
array to the shape and distribution of X array. It first forms a section of
Y array elements, then redistributed these data in the shape and
distribution the same as X array to ensure that every X array element in
the forall statement will get its corresponding Y array element in the same
processor. (some careful reader may laught here: since you have such a
wonderful runtime function, why can't you move Y directly
to X, instead of moving it first to some TMPX, then TMPX to X via a DO loop ?)

