next up previous
Next: Strip-mining Up: Data Transformations Previous: Data Transformations

Data Transformation Model


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.

Saman Amarasinghe
Fri Apr 7 11:22:17 PDT 1995