\paragraph{Figure out communication.} 

We first develop a concept of {\em shift-isomorphism} beteween two array
sections.

Recalling arrays X and Y are aligned with templates $T_x$ and $T_y$, as
illustrated in previous section, we can see a mapping from array sections
to template sections, i.e., from
$X(l_x:u_x:s_x)$, we have $T_x(l'_{tx}:u_{tx}':s'_{tx})$. And from
$Y(l_y:u_y:s_y)$, we have $T_y(l'_{ty}:u_{ty}':s'_{ty})$.


The mapping functions are

\begin{center}
$l'_{tx} = stride_x \cdot l_x + offset_x,~~
u'_{tx} = stride_x \cdot u_x + offset_x,~~
s'_{tx} = stride_x \cdot s_x$
\end{center}

With our model, it is

\begin{center}
$l'_{tx} = a_x \cdot l_x + b_x,~~
u'_{tx} = a_x \cdot u_x + b_x,~~
s'_{tx} = a_x \cdot s_x$
\end{center}

A similar situation exists for Y .

We say $X(l_x:u_x:s_x)$ and $Y(l_y:u_y:s_y)$ are {\em shift-isomorphic}
iff $\lfloor\frac{u_x - l_x}{s_x}\rfloor = \lfloor\frac{u_y -
l_y}{s_y}\rfloor$ and 
$s'_{tx} = s'_{ty}$ (attention: these are parameters in
corresponding template sections).

And the {\em shift-amount} from $Y(l_y:u_y:s_y)$ to $X(l_x:u_x:s_x)$
is equal to $(l'_{ty} - l_{ty}) - (l'_{tx} - l_{tx})$
(again, parameters from templates). Here we imply
that positive amount indicates {\em shift to the left}, while
negative indicates {\em shift to the right}.

The intention is clear: we want a condition for {\tt eoshift} being
adequate.

Instantiating it with our model,
\begin{verbatim}
   FORALL (i=l:u:s) X(i) = Y(a*i+b)
\end{verbatim}

we have,

\begin{tabular}{l l} \\
$X(l_x:u_x:s_x) = X(l:u:s)$, &
$Y(l_y:u_y:s_y) = Y(a \cdot l+b:a \cdot u+b:a \cdot s)$ \\
\vspace{0.2in}
\end{tabular}

and

\vspace{0.2in} 
\begin{tabular}{l|l} \hline 
$l'_{tx} = a_x \cdot l + b_x$ & 
$l'_{ty} = a_y \cdot (a \cdot l + b) + b_y$ \\

$u'_{tx} = a_x \cdot u + b_x$ & 
$u'_{ty} = a_y \cdot (a \cdot u + b) + b_y$ \\

$s'_{tx} = a_x \cdot s$ &
$s'_{tx} = a_y \cdot a \cdot s$ \\
\hline 
\end{tabular}
\vspace{0.2in}

Thus, $X(l:u:s)$ is {\em shift-isomorphic} to 
$Y(a \cdot l+b:a \cdot u+b:a \cdot s)$ iff 
$a_x \cdot s = a_y \cdot a \cdot s$, or simply 
\begin{equation}
a_x = a_y \cdot a
\end{equation}

and 
\begin{equation}
amount_{shift} = (a_y \cdot (a \cdot l + b) + b_y - l_{ty})
             - (a_x \cdot l + b_x - l_{tx})
\end{equation}

We note, two array sections are {\em shift isomorphic} {\bf does not}
necessarily mean one can achieve the communication required by
shifting Y with so-determined amount -- we have to consider the
effect of different distributions, too. We discuss the following
cases.

\begin{itemize}
\item
If $T_x$ and $T_y$ have the same size (i.e., $u_{tx}-l_{tx} =
u_{ty}-l_{ty})$, and are distributed in the same fashion (both
BLOCK, or both CYCLIC), a shift of Y with that amount does the job.
Then the node program would look like:

\begin{verbatim}
    CALL loopBounds(l,u,s,DAD_X,ll,lu,ls)
    CALL detectCommunication(DAD_X,DAD_Y,amount)
    CALL eoshift(Y,amount,T)
    DO i = ll,lu,ls
      X(i) = T(i)
    END DO
\end{verbatim}

\paragraph{Example 1:} Consider the following program.

\begin{verbatim}
       REAL X(1:20),Y(1:20),Z(1:20)
!HPF$  PROCESSORS P(4)
!HPF$  ALIGN Y(i) WITH X(i)
!HPF$  ALIGN Z(i) WITH X(i)
!HPF$  DISTRIBUTE X(block) 
       ...
       FORALL (i=3:18:3) X(i) = Y(i+2)
       ...
       FORALL (i=3:18:5) X(i) = Z(i+2)
       ...
       END
\end{verbatim}

Here is the situition in templates for the first FORALL

\begin{verbatim}
Tx:    --x--x--x--x--x--x--
       11111222223333344444

Ty:    ----y--y--y--y--y--y
       11111222223333344444
\end{verbatim}

We see a shift of Y with amount +2 {\em is necessary}.
For the situition of the second FORALL,

\begin{verbatim}
Tx:    --x----x----x----x--
       11111222223333344444

Tz:    ----z----z----z----z
       11111222223333344444
\end{verbatim}

A shift of Z with amount +2 will make the elements in Tx and Tz
aligned, but {\em is not necessary}.

As we may have noticed in this example, a shift may not be needed
if we allow {\tt X(i) = T(i+v)} in the DO loop, under certain
condition. We defer its discussion after getting a good picture
on the main stream. 

\item
If $T_x$ and $T_y$ have the same size, but they
are distributed in different fashions, we generally can not meet 
the communication requirement by a shift. 

\paragraph{Example 2:} Consider the same program, but Y being
cyclically distributed.

\begin{verbatim}
Tx:    --x--x--x--x--x--x--
       11111222223333344444

Ty:    ----y--y--y--y--y--y
       12341234123412341234
\end{verbatim}

We see it is not possible to accomplish the communication required
by a shift.

\item
If $T_x$ and $T_y$ {\em does not} have the same size, no matter if they
are distributed in the same fashion or not, we generally can not meet 
the communication requirement by a shift. 

\paragraph{Example 3:} Consider the same X, but Y with 32 elements.

\begin{verbatim}
Tx:    --x--x--x--x--x--x--
       11111222223333344444

Ty:    --------y--y--y--y--y--y--------
       11111111222222223333333344444444
\end{verbatim}

We see it is not possible to accomplish the communication required
by a shift, since a shift can not make each processor contain
the same number of x's and y's, respectively.

\end{itemize}

The above discussion actually motivates a generalization of the
concept of {\em shift-isomorphic} to {\em shift-homomorphic}.
We first state the following useful lemma.

\newtheorem{lemma}{Lemma}

\begin{lemma}

Consider two intervals $I_1 = [1:t_1]$ and $I_2 = [1:t_2]$.
Assume p (some positive integer) is a common divisor of $t_1$ and $t_2$,
and write $w_1 = \frac{t_1}{p}$ and $w_2 = \frac{t_2}{p}$.
Let $s_1$ and $s_2$ be two positive integers satisfying

\begin{equation}
\frac{s_1}{s_2} = \frac{t_1}{t_2}
\end{equation}

Then the mapping $\Phi$ from 
$I_1$ to $I_2$: $i \longmapsto \lceil{i \cdot \frac{t_2}{t_1}}\rceil$
has the following property:

For any strided subinterval of $I_1$,
\begin{center}
$i, i+s_1, i+2\cdot s_1, ..., i+k\cdot s_1$
\end{center}
if 
\begin{center}
$(n-1) \cdot w_1 + 1 \leq i$, and~ $i+k\cdot s_1 \leq n \cdot w_1$ 
\end{center}
for some positive integer n, then
\begin{center}
$(n-1) \cdot w_2 + 1 \leq \Phi(i)$, and~ $\Phi(i)+k\cdot s_2 \leq n \cdot w_2$.
\end{center}
\end{lemma}

\paragraph{Proof: }

From $(n-1) \cdot w_1 + 1 \leq i$, we can have
\begin{center}
$((n-1) \cdot w_1 + 1)\cdot \frac{t2}{t1} \leq i \cdot\frac{t2}{t1}$, 

$\lceil ((n-1) \cdot w_1 + 1)\cdot \frac{t2}{t1}\rceil \leq 
     \lceil i \cdot\frac{t2}{t1} \rceil = \Phi(i)$, 

$\lceil (n-1) \cdot w_2 + \frac{t2}{t1}\rceil \leq \Phi(i)$

$(n-1)\cdot w_2 + 1 \leq (n-1) \cdot w_2 + \lceil \frac{t2}{t1}\rceil 
      \leq \Phi(i)$
\end{center}

Furthermore, from $i+k\cdot s_1 \leq n \cdot w_1$, we have
\begin{center}
$(i+k\cdot s_1) \cdot \frac{t2}{t1} \leq n \cdot w_1 \cdot\frac{t2}{t1}$ 

$\lceil{i\cdot\frac{t_2}{t_1}}\rceil + k\cdot s_2 = 
\lceil (i+k\cdot s_1) \cdot \frac{t2}{t1}\rceil
     \leq \lceil n \cdot w_1 \cdot\frac{t2}{t1}\rceil$ 

$\Phi(i)+k\cdot s_2 \leq \lceil n \cdot w_1 \cdot\frac{t2}{t1}\rceil =
   n \cdot w_2 $ 
\end{center}
\begin{flushright}
$\Box$
\end{flushright}

\paragraph{Example 4: } Consider

\begin{center}
 $t_1=60, ~t_2=84, ~p=4, ~s_1=5, ~s_2=7$
\end{center}

\begin{verbatim}
    1--...15--...30--...45--...60

    1----....21----....42----....63----....84
\end{verbatim}

We have $w_1=60/4=15, ~w_2=84/4=21$. The subinterval of $I_1$, 18,
23, 28 is bounded by $w_1 + 1$ and $2 \cdot w_1$. The correspond
subinterval in $I_1$, according to the lemma, is 26, 33, 40, which
is bounded by $w_2 + 1$ and $2 \cdot w_2$.

\vskip0.3in

Let $t$ be the size of a template T. We use $\overline{t(p)}$ to denote
$p \cdot \lceil\frac{t}{p}\rceil$. When no ambiguity results, we
may simply use $\overline{t}$ for $\overline{t(p)}$.
Thus, $\overline{t_x} = \overline{u_{tx}-l_{tx}+1}$ and
$\overline{t_y} = \overline{u_{ty}-l_{ty}+1}$.

We say $X(l_x:u_x:s_x)$ and $Y(l_y:u_y:s_y)$ are {\em shift-homomorphic}
if
\begin{equation}
\lfloor\frac{u_x - l_x}{s_x}\rfloor = \lfloor\frac{u_y -
l_y}{s_y}\rfloor 
\end{equation}

and

\begin{equation}
s'_{tx} = s'_{ty} \cdot \frac{\overline{t_x}}{\overline{t_y}}
\end{equation}

for BLOCK-distributed X and Y, or

\begin{equation}
s'_{tx} \equiv s'_{ty} ~~ (mod~p)
\end{equation}

for CYCLIC-distributed X and Y. 

\vskip0.3in
{\em Shift-homomorphism} allows us to efficiently handle some
cases where X and Y have templates of different sizes. Clearly,
shift-isomorphism is a special case of shift-homomorphism. 

Instantiating it with our model,
\begin{verbatim}
   FORALL (i=l:u:s) X(i) = Y(a*i+b)
\end{verbatim}

we have,

\begin{tabular}{l l} \\
$X(l_x:u_x:s_x) = X(l:u:s)$, &
$Y(l_y:u_y:s_y) = Y(a \cdot l+b:a \cdot u+b:a \cdot s)$ \\
\end{tabular}

and

\vspace{0.2in}
\begin{tabular}{l|l} \hline
$l'_{tx} = a_x \cdot l + b_x$ &
$l'_{ty} = a_y \cdot (a \cdot l + b) + b_y$ \\

$u'_{tx} = a_x \cdot u + b_x$ &
$u'_{ty} = a_y \cdot (a \cdot u + b) + b_y$ \\

$s'_{tx} = a_x \cdot s$ &
$s'_{tx} = a_y \cdot a \cdot s$ \\
\hline
\end{tabular}
\vspace{0.2in}

Thus, $X(l:u:s)$ is shift-homomorphic to
$Y(a \cdot l+b:a \cdot u+b:a \cdot s)$ if
$a_x \cdot s \cdot \overline{t_y} = a_y \cdot a \cdot s\cdot \overline{t_x}$, 
or simply
\begin{equation}
\frac{a_x}{a_y \cdot a} = \frac{\overline{t_x}}{\overline{t_y}}
\end{equation}

for BLOCK-distribution, or

\begin{equation}
a_x\cdot s \equiv a_y\cdot a \cdot s ~~(mod~p)
\end{equation}

for CYCLIC-distribution.

\newtheorem{theo}{Theorem}

\begin{theo}
If $X(l_x:u_x:s_x)$ and $Y(l_y:u_y:s_y)$ are shift-homomorphic,
then a shift of Y safices to make X(i) and Y(j) in the same
processor for $i= l_x:u_x:s_x, ~j=l_y:u_y:s_y,$ correspondingly.
\end{theo}

\paragraph{Proof: } Let $k_x$ be the relative position of $X(l_x)$
in $T_x$. We locate $k_y = \lceil k_x\cdot\frac{\overline{t_y}}
{\overline{t_x}}\rceil$ in $T_y$. Shift Y such that $Y(l_y)$ takes
the position $k_y$ in $T_y$. We claim the job is done, since
we can easily see an ``isomorphism'' between lemma one and the
theorem, namely we can have a 1-1 onto mapping between the
parameters of the two systems. Thus, an ``isomorphic'' conclusion
is obtained.

\begin{flushright}
$\Box$
\end{flushright}

\paragraph{Example: } Consider $X(l_x:u_x:s_x)$ takes position
33,40,47,54,61,68 in its template. And $Y(l_y:u_y:s_y)$ takes
1,6,11,16,21,26 in its template.

\begin{verbatim}
Tx:   ----....21----....42----....63----....84

Ty:   --...15--...30--...45--...60
\end{verbatim}

$k_y = \lceil 33\cdot\frac{5}{7}\rceil = 24$. That is, we move
Y such that $Y(l_y:u_y:s_y)$ takes the positions 24,29,34,39,44,49.
It is easy to verify that each processor contains the same number
of x's and y's, correspondingly. That is, the shift amount for Y is
1-24 = -23.

\paragraph{Parameters in the node program:} Once it is detected that
$X(l:u:s)$ and $Y(a\cdot l+b:a\cdot u+b:a\cdot s)$ are shift-homomorphic,
the node program will have the form
\begin{verbatim}
    shift Y to some temporary T
    DO i=ll,lu,ls
      X(i)=T(u*i+v)
    END DO
\end{verbatim}

We want to determine u and v. First of all, we claim u and v are processor
independent. $u = \frac{s_y}{s_x}$, and solving 
$(k_x - l\_tlb_x + 1) \cdot u + v = (k_y - l\_tlb_y + 1)$ to get v. 
For the example,
$u = \frac{5}{7}$, and 
$v = (24 - 16 + 1) - (33 - 22 + 1)\cdot u = \frac{3}{7}$

\begin{verbatim}
    shift Y to some temporary T
    DO i=ll,lu,ls
      X(i)=T((5*i+3)/7)
    END DO
\end{verbatim}

where (ll,lu,ls) = (12,19,7), (5,19,7), and (5,5,7) for processors
2, 3, and 4, respectively, which have corresponding (9,14,5),
(4,14,5), and (4,4,5) triples for T, respectively.

\paragraph{Improve efficiency:} We also want to know the condition
for no communication. We claim, no communication needed iff the first 
processor that has
some elements of $X(l_x:u_x:s_x)$ has the same number of elements
from $Y(l_y:u_y:s_y)$.

