\section{Determination of local loop bounds}

As mentioned in previous section, a runtime function loop\_bounds()
is called in node program to compute local loop bounds on each
processor for corresponding global FORALL index range, with respect
to array (left hand side in the assignment statement). We discuss
algorithms used by loop\_bound() in this section.

\paragraph{}
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}

Local bounds is also a function of index base of local array declared
in node program. In what follows, we consider 0-based index for all
local arrays, though global HPF arrays may be declared arbitrarily.
For ease of reference, we recall our {\em model} again.

\begin{center}
\begin{tabular}{l l l} \hline
p; ~~ l:u:s & $X(a_0i+b_0)$ & $Y(a_1i+b_1)$ \\ \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}

The algorithm is different for different distribution mode. 

\begin{itemize}
\item
BLOCK distribution

\begin{small}
\begin{verbatim}
if s does not divede (u-l), set u=floor((u-l)/s)*s;
w = ceil(tx/p);
tl = l_tx + (i-1)*w;    tu = l_tx + i*w - 1;
if (tu < ax*l+bx) or (ax*u+bx < tl), then
   set ll = 0; lu = -1; ls = 1;    // no effective element
else
   find the least j in (l:u:s)
      such that ax*j+bx >= tl;
   set ll = ax*j+bx - tl;
   find the greatest j in (l:u:s)
      such that ax*j+bx <= tu;
   set lu = ax*j+bx - tl;
   set ls = ax*s;
end if
\end{verbatim}
\end{small}


\item
CYCLIC distribution

We see two arithmetic progressions here
\paragraph{processor i's relative positions in template: } i, i+p, i+2*p, ..., i+n*p, ...

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

where o = ax*l+bx - l\_tx + 1, q = ax*s. Then we would have to
solve the following Diophantine equation for each processor i:

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

with the boundary conditions,
\begin{equation}
    n \geq 0, i + n*p \leq u_{tx} - l_{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(q,p) divides $\mid i-o \mid$.
And if so, we may employ Extended  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(q,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 satisfy the constraints 
   for n and m;
   if the subset is not empty, then
      ll = minimum n; lu = maximum n;
   else
      ll = 0; lu = -1; ls = 1; no effective element
   end if
else
   ll = 0; lu = -1; ls = 1; no effective element
end if
\end{verbatim}
\end{small}

Banerjee \cite{cmpi:9} had a very practical treatment on how to solve
the Diophantine equation. We have included it in Appendix B for the
sake of completeness of this document.

To figure out {\tt ls}, we need the least common multiple of ax*s and p,
and denote it by {\em lcm(ax*s,p)}.
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 ax*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(ax*s,p)$. 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(ax*s,p)}{p}$ away, i.e., {\tt ls} = $\frac{lcm(ax*s,p)}{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

q = 2*3 = 6

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, lu(1) = 8.
\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, lu(3) = 9.
\end{itemize}

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

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


