\documentstyle{article}

\input{psfig} 

\begin{document}

\sloppy

\pagestyle{plain}

\section*{\em ``Shift Homomorphism''}

Consider the following fragment of HPF pseudocode:
\begin{tabbing}
{\tt  !HPF\$ } \= {\tt TEMPLATE tx (0 : ), ty (0 : )} \\
{\tt  !HPF\$ } \> {\tt DISTRIBUTE tx (BLOCK (}$w_x${\tt )) ONTO p} \\
{\tt  !HPF\$ } \> {\tt DISTRIBUTE ty (BLOCK (}$w_y${\tt )) ONTO p} \\
\\
{\tt  !HPF\$ } \> {\tt DIMENSION x (0 : n - 1), y (0 : n - 1)} \\
{\tt  !HPF\$ } \> {\tt ALIGN x (i) WITH tx (}$k_x${\tt + }$s_{tx}${\tt * i)} \\
{\tt  !HPF\$ } \> {\tt ALIGN y (i) WITH ty (}$k_y${\tt + }$s_{ty}${\tt * i)} \\
\\
               \> {\tt x = y}
\end{tabbing}
By suitable composition of section and alignment parameters, possibly
combined with trivial relabelling so that index ranges start at 0,
any assignment between one-dimensional sections block-distributed over the
same one-dimensional processor arrangement can be reduced to this case.

The arrays {\tt x} and {\tt y} are ``shift-homomorphic'' iff
\begin{displaymath}
  s_{tx} / w_x = s_{ty} / w_y
\end{displaymath}
If this condition holds the assignment of {\tt y} to {\tt x} can
be implemented by shifting the values of {\tt y} along template
{\tt ty} then performing a local copy.

\subsection*{Proof:}

The element $i$ of {\tt x} is aligned with element $k_x + s_{tx} i$ of
template {\tt tx} and
the element $i$ of {\tt y} is aligned with element $k_y + s_{ty} i$ of
template {\tt ty}.

A temporary array {\tt y'} is created by shifting the values in {\tt y}
by amount
\begin{displaymath}
  a = k_y' - k_y
\end{displaymath}
along template {\tt ty}.
So element $i$ of {\tt y'} is aligned with element $k_y' + s_{ty} i$ of
template {\tt ty}.

In particular, choose
\begin{displaymath}
  k_y' = \lfloor k_x w_y / w_x \rfloor
\end{displaymath}
so the alignment of element $i$ of {\tt y'} is to element
\begin{eqnarray*}
k_y' + s_{ty} i & = & \lfloor k_x w_y / w_x \rfloor + s_{ty} i \\
                & = & \lfloor k_x w_y / w_x + s_{ty} i \rfloor \\
                & = & \lfloor (k_x w_y + s_{ty} w_x i) / w_x \rfloor
\end{eqnarray*}
of template {\tt ty}.

Now, element $j_x$ of template {\tt tx} is mapped to processor
$\lfloor j_x / w_x \rfloor$ and
element $j_y$ of template {\tt ty} is mapped to processor
$\lfloor j_y / w_y \rfloor$.

So element $i$ of {\tt x} is mapped to processor 
\begin{displaymath}
\lfloor (k_x + s_{tx} i) / w_x \rfloor
\end{displaymath}
and element $i$ of {\tt y'} is mapped to processor 
\begin{displaymath}
\lfloor (k_y' + s_{ty} i) / w_y \rfloor
\end{displaymath}

But
\begin{eqnarray*}
\lfloor (k_y' + s_{ty} i) / w_y \rfloor & = &
        \lfloor \lfloor (k_x w_y + s_{ty} w_x i) / w_x \rfloor / w_y \rfloor \\
 & = &  \lfloor (k_x w_y + s_{ty} w_x i) / w_x w_y \rfloor \\
 & = &  \lfloor k_x / w_x + s_{ty} i / w_y \rfloor \\
 & = &  \lfloor (k_x + s_{tx} i) / w_x \rfloor
\end{eqnarray*}
In the second step we used a general property of non-negative integers:
\begin{displaymath}
\lfloor \lfloor l / m \rfloor / n \rfloor = \lfloor l / m n \rfloor
\end{displaymath}
and in the last step we used the shift homomorphism condition.

This establishes that elements $i$ of {\tt x} and {\tt y'} map to the same
processor.  Suppose this is processor $n$.  Assuming array segments are
allocated according to the template size, the local subscript in {\tt x}
is
\begin{displaymath}
  l_x = k_x + s_{tx} i - n w_x
\end{displaymath}
and the local subscript in {\tt y'} is
\begin{displaymath}
  l_y' = k_y' + s_{ty} i - n w_y
\end{displaymath}
Using the shift homomorphism condition gives
\begin{displaymath}
  w_x l_y' - w_y l_x = w_x k_y' - w_y k_x
\end{displaymath}
or
\begin{displaymath}
  l_y' = (w_y / w_x) l_x + (k_y' - w_y k_x / w_x)
\end{displaymath}
as the relation between the local subscripts.

\end{document}

