To facilitate the design of our data layout algorithm, we have
developed a data transformation model that is analogous to the
well-known loop transformation theory[6,35].
We represent an n-dimensional array as
an n-dimensional polytope whose boundaries are given by the array
bounds, and the interior integer points represent all the elements in
the array. As with sequential loops, the ordering of the axes is
significant. In the rest of the paper we assume the FORTRAN
convention of column-major ordering by default, and for clarity the
array dimensions are 0-based. This means that for an n-dimensional
array with array bounds 
, the linearized address for array element 
is 
.
Below we introduce two primitive data transforms: strip-mining and
permutation.