next up previous
Next: Permutation Up: Data Transformation Model Previous: Data Transformation Model

Strip-mining

Strip-mining an array dimension re-organizes the original data in the dimension as a two-dimensional structure. For example, strip-mining a one-dimensional d-element array with strip size b turns the array into a array. Figure 2(a) shows the data in the original array, and Figure 2(b) shows the new indices in the strip-mined array. The first column of this strip-mined array is high-lighted in the figure. The number in the upper right corner of each square shows the linear address of the data item in the new array. The ith element in the original array now has coordinates in the strip-mined array. Given that block sizes are positive, with the assumption that arrays are 0-based we can replace the floor operators in array access functions with integer division assuming truncation. The address of the element in the linear memory space is . Strip-mining, on its own, does not change the layout of the data in memory. It must be combined with other transformations to have an effect.

  
Figure 2: Array indices of (a) the original array, (b) the strip-mined array and (c) the final array. The numbers in the upper right corners show the linearized addresses of the data.



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