\documentstyle{article}
\begin{document}

\section{About dimension reduced array sections}

This appendix serves as theoritical basis of DAD\_inherit\_caller().
Term {\em dimension reduced array section} specifically means an
array section expressed with one or more dimensions fixed, such as
A(1,2:10:2), A(1:10,5,3:21:3), and A(3,2:22:4,7).

\paragraph{}
Given an array defined as $A(d_1, d_2, ..., d_m)$ with column major
storage scheme. Consider a section

\begin{equation}
A(l_1\!:\!d_1\!:\!s_1, l_2\!:\!d_2\!:\!s_2, ..., l_i\!:\!d_i\!:\!s_i, ...,
 l_m\!:\!d_m\!:\!s_m)
\end{equation}

We claim that a dimension reduced section, such as

\begin{equation}
A(l_1\!:\!d_1\!:\!s_1, l_2\!:\!d_2\!:\!s_2, ..., l_{i-1}\!:\!d_{i-1}\!:\!s_{i-1}, 
k, l_{i+1}\!:\!d_{i+1}\!:\!s_{i+1}, ...,
 l_m\!:\!d_m\!:\!s_m)
\end{equation}

can be effectively seen as a section with one less dimension as

\begin{equation}
A'(l_1\!:\!d_1\!:\!s_1, l_2\!:\!d_2\!:\!s_2, ..., l_{i-1}\!:\!d_{i-1}\!:\!s_{i-1}, 
l_{i+1}\cdot d_i\!:\!d_{i+1}\cdot d_i\!:\!s_{i+1}\cdot d_i, ...,
 l_m\cdot d_i\!:\!d_m\cdot d_i\!:\!s_m\cdot d_i)
\end{equation}

when its first location (bass address) aligned with 
$A(l_1, l_2, l_{i-1}, k, l_{i+1}, ..., l_m)$.

\paragraph{}
Before we get into a proof, let's see some examples.

\paragraph{Example 1.} Two dimensional array A(n,m). Consider A(k,1:m).
The location of its $i^{th}$ element A(k,i) is LOC(A(1,1))+(k-1)+n(i-1),
and LOC(A(1,1))+(k-1) is the location of A(k,1), the first element.
On the other hand, the location of the $i^{th}$ element of array section A'(n:m*n:n)
is LOC(A'(n))+(i-1)*n. Align A'(n) with A(k,1), we see A(k,1:m) and A'(n:m*n:n)
are identical.

\paragraph{Example 2.} Three dimensional array $A(d_1, d_2, d_3)$. Consider
$A(1:d_1,k,1:d_3)$.
The location of its $(i,j)^{th}$ element A(i,k,j) is 
LOC(A(1,k,1))+(i-1)+(k-1)*d1+(j-1)*d1*d2,
and LOC(A(1,k,1))+(k-1)*d1 is the location of A(1,k,1), the first element.
On the other hand, the location of the $(i,j)^{th}$ element of array section
A'(1:d1,d2:d3*d2:d2)
is LOC(A'(1,d2))+(i-1)+(j-1)*d1*d2. Align A'(1,d2) with A(1,k,1), 
we see A(1:d1,k,1:d3) and A'(1:d1,d2:d3*d2:d2) are identical.

\paragraph{Concept of {\bf identical layout} for array sections.

According to Fortran 90, {\bf whole} arrays and array {\bf sections} are all {arrays}.
Two arrays A and B have the same shape if their {\em extent vectors} are identical.
Thus, arrays A(5) and B(1:9:2) have the same shape, both having extent vector (5).

But in memory, A(5) and B(1:9:2) have different {\em spans}. Let's refine the concept
of shape to {\em memory layout}, or simply {\em layout}. A {\em layout} of an array of 
shape $(e_1,e_2,...,e_m)$ is
the mapping from $(1:e_1,1:e_2,...,1:e_m)$ to memory locations, based on Fortran storage
scheme.

For example, array A(5,3), shape = (5,3), the mapping is 

(i,j) --> LOC(A(1,1)) + (i-1) + 10*(j-1).

B(2:10:2,3:9:3) of B(10,9), shape = (5,3), the mapping is 

(i,j) --> LOC(B(2,3)) + 2*(i-1) + 10*3*(j-1)

C(2:10:2,3:9:3) of C(15,10), shape = (5,3), the mapping is 

(i,j) --> LOC(C(2,3)) + 2*(i-1) + 15*3*(j-1)

\paragraph{Definition:} Two arrays have the same layout, if they have the same shape
and they have the same layout once their first elements are aligned.

Thus, the above three arrays have the same shape, but different layout.


\paragraph{A generalized array addressing formula.} We know, for array A(d1,d2,d3),
A(i,j,k) is at LOC(A(1,1,1))+(i-1)+d1*(j-1)+d1*d2*(k-1).

For A(l1:d1:s1,l2:d2:s2,l3:d3:s3), A(i,j,k) is at
LOC(A(1,1,1))+(i-1)+d1*(j-1)+d1*d2*(k-1) for 

i=l1,l1+s1,l1+2*s1,...,l1+(e1-1)*s1, e1 = (d1-l1)/s1 + 1
j=l2,l2+s2,l2+2*s2,...,l2+(e2-1)*s2, e2 = (d2-l2)/s2 + 1
k=l3,l3+s3,l3+2*s3,...,l3+(e3-1)*s3, e3 = (d3-l3)/s3 + 1

or

i = l1+(i'-1)*s1, i'=1,2,...,e1
j = l2+(j'-1)*s2, j'=1,2,...,e2
k = l3+(k'-1)*s1, k'=1,2,...,e3

that is, A(i,j,k) is at 

LOC(A(1,1,1)) + (l1+(i'-1)*s1-1) + d1*(l2+(j'-1)*s2-1) + d1*d2*(l3+(k'-1)*s3-1)

LOC(A(1,1,1)) + (l1-1)+d1*(l2-1)+d1*d2*(l3-1) + (i'-1)*s1 + d1*(j'-1)*s2 + d1*d2*(k'-1)*s3

or (replace primed indices by non primed),

LOC(A(l1,l2,l3)) + (i-1)*s1 + d1*(j-1)*s2 + d1*d2*(k-1)*s3, 

where (i,j,k) is taken from (1:e1,1:e2,1:e3). Similarly,
For A(l1:u1:s1,l2:u2:s2,l3:u3:s3) of A(d1,d2,d3), A(i,j,k) is at
LOC(A(l1,l2,l3)) + (i-1)*s1 + d1*(j-1)*s2 + d1*d2*(k-1)*s3, 
where (i,j,k) is taken from (1:e1,1:e2,1:e3), but e1=(u1-l1)/s1 + 1,
e2 = (u2-l2)/s2 + 1, e3 = (u3-l3)/s3 + 1. 

Now, we can say A(...) of equation(2) and A'(...) of equation (3) have the same layout.

Proof: ... (obvious from the examples) ...

For A(k,d2,d3) and A'(d1:d1*d2:d1,d1:d1*d3:d1), if the first dimension of A(k,:,:) is aligned with
some template T(a*i+b), then the first dimension of A' is equivalently aligned with
{\em some} template T'(a*i*d1+b*d1)....

Template T is distributed on p processors, T' is also distributed on the same processors, 
BLOCK is preserved, {\ul CYCLIC becomes CYCLIC(d1)}.
\end{document}
