\section{Treatment}

As the first attempt, we may see the process divided in three steps.

\begin{enumerate}
\item
Determine local loop bounds according to {\em owner computes} rule.
\item
Each processor converts its local bounds to global indices, respectively.
\item
Determine communication pattern for Y according to the separated global indices.
\end{enumerate}

This way, it is easy for processor to know what off-processor elements it needs,
but hard for it to know where it should send elements that are needed by others.\\

We take a different approach.

\begin{enumerate}
\item
Determine local loop bounds according to {\em owner computes} rule.
\item
Compare the distribution patterns of X and Y based on their DADs.
Decide on one of the three actions:
\begin{itemize}
\item
No communication.
\item
A global shift is adequate.
\item
Go for the last resort -- concatenation.
\end{itemize}
\end{enumerate}

\paragraph{Determine the local loop bounds.} It is equivalent to ask:
\begin{quote}
Given array section X(l:u:s) and DAD of X, what is the corresponding 
local index-triplet (ll(i),lu(i),ls(i)) for each processor $i \in (1:p)$.
\end{quote}

With a DAD of X(lx:ux) in mind, we have,

\begin{itemize}
\item
BLOCK distribution

\begin{small}
\begin{verbatim}
if s does not divedes (u-l), set u=floor((u-l)/s)*s;
if (l_tub < stride*l+offset) or (stride*u+offset < l_tlb), then
   set ll > lu = 0    // no effective element
else
   find the least j in (l:u:s)
      such that stride*j+offset >= l_tlb, i.e,
      j=l;
      while (stride*j+offset < l_tlb) j = j + s;
   set ll = stride*j+offset-l_tlb + 1;
   find the greatest j in (l:u:s)
      j=u;
      while (stride*j+offset > l_tub) j = j - s;
   set lu = stride*j+offset-l_tlb + 1;
end if

set ls = stride*s  // this is processor independent
\end{verbatim}
\end{small}

This is essentially the same procedure for generating DAD of X(l:u:s) from
that of X(lx:ux).

\item
CYCLIC distribution

We see two arithmetic progressions here

\paragraph{processor i's positions in template: } i, i+p, i+2*p, ..., i+n*p, ...

\paragraph{(l:u:s) element positions in template: } o, o+q, o+2*q, ..., o+m*q, ...

where o = l*stride+offset - t\_lb + 1, q = stride*s. Then we would have to
solve the following Diophantine equation:

\begin{equation}
    i+n*p = o+m*a
\label{dio:1}
\end{equation}

with the boundary conditions,
\begin{equation}
    n \geq 0, i + n*p \leq l_{tx}-u_{tx}+1
\end{equation}
\begin{equation}
    0 \leq m \leq \frac{u - l}{s}
\end{equation}

We know the equation (\ref{dio:1}) has solution iff gcd(a,p) divides $\mid i-o \mid$.
And if so, we may employ Euclidean algorithm to find all pairs of (n,m)
that satisfy the equation, and then impose the boundary conditions.

Now, the algorithm outline for computing ll and lu on processor i,
\begin{small}
\begin{verbatim}
if gcd(a,p) divides |i-o| then
   using Euclidean algo. to compute the solution (n,m) of eq. (1);
   find the subset from the solution set that all element satisfy
   the constraints for n and m;
   if the subset is not empty, then
      ll = minimum n + 1, lu = maximum n + 1
   else
      no effective element
   end if
else
   no effective element
end if
\end{verbatim}
\end{small}

Once again, this is essentially the same as we do for DAD of X(l:u:s).

To figure out {\tt ls}, we need the least common multiple of stride*s and p,
and denote it by {\em lcm}.
Here is the idea: processor i see its `name' in template every p positions, while
X(l:u:s) sees its element in template every stride*s positions. Thus, 
if processor i and X(l:u:s) meet at position t of the template then the next
time they meet again will be at position $t+lcm$. Since template is cyclically
distributed (p positions in template is equal to 1 position in local array), 
processor i will see the next element of X(l:u:s) {\bf locally} at position 
$\frac{lcm}{p}$ away, i.e., {\tt ls} = $\frac{lcm}{p}$, processor independent.

\end{itemize}

\paragraph{Example. } Consider the following program.

\begin{small}
\begin{verbatim}
      PROGRAM MAIN
      DIMENSION X(1:20)
!HPF$ PROCESSORS P(4)
!HPF$ TEMPLATE T(1:60)
!HPF$ DISTRIBUTE T(CYCLIC) ONTO P
!HPF$ ALIGN X(i) WITH T(2*i+1)
      ...
      FORALL (i=4:19:3) X(i) = ...
      ...
      END
\end{verbatim}
\end{small}

To compute {\tt ll and lu} for processor i= 1,2,3,4, we see

o=2*4+1-1+1=9

o, o+6, o+12, o+18, ..., o+6*m, ...

i, i+4, i+8, i+12, ..., i+4*n, ...

The equation to be solved is
\begin{equation}
i+4n = 9 + 6m 
\end{equation}

\begin{itemize}
\item[i=2,4: ]
No solution.
\item[i=1: ]

$1+4n = 9 + 6m, n=2+ \frac{3}{2}\cdot m $

constraint: $ 1+4n \leq 60-1+1, n \leq 14 $

$0 \leq m \leq (19-4)/3 = 5$

m = 0, 2, 4

n = 2, 5, 8

That is, ll(1) = 2+1 = 3, lu(1) = 8+1 = 9.
\item[i=3: ]

$3+4n = 9 + 6m, n= \frac{3+3m}{2}$

constraint: $ 1+4n \leq 60-1+1, n \leq 14 $

$0 \leq m \leq (19-4)/3 = 5$

m = 1, 3, 5

n = 3, 6, 9

That is, ll(3) = 3+1 = 4, lu(3) = 9+1 = 10.
\end{itemize}

Finally, lcm = lcm(2*3,4) = 12.  ls = lcm/p = 3

In summary, global (4:19:3) maps to local (3:9:3) for processor 1,
(4:10:3) for processor 3, and processor 2 and 4 get no elements of
X(4:19:3).


