next up previous
Next: Legality Up: Data Transformation Model Previous: Strip-mining

Permutation

A permutation transform T maps an n-dimensional array space to another n-dimensional space; that is, if is the original array index vector, the transformed array indices is . The array bounds must also be transformed similarly.

For example, an array transpose maps to . Using matrix notation this becomes

The result of transposing the array in Figure 2(b) is shown in Figure 2(c). Figure 2(c) shows the data in the original layout, and each item is labeled with its new indices in the transposed array in the center, and its new linearized address in the upper right corner. As high-lighted in the diagram, this example shows how a combination of strip-mining and permutation can make every fourth data element in a linear array contiguous to each other. This is used, for example, to make contiguous a processor's share of data in a cyclically distributed array.

In theory, we can generalize permutations to other unimodular transforms. For example, rotating a two-dimensional array by 45 degrees makes data along a diagonal contiguous, which may be useful if a loop accesses the diagonal in consecutive iterations. There are two plausible ways of laying the data out in memory. The first is to embed the resulting parallelogram in the smallest enclosing rectilinear space, and the second is to simply place the diagonals consecutively, one after the other. The former has the advantage of simpler address calculation, and the latter has the advantage of more compact storage. We do not expect unimodular transforms other than permutations to be important in practice.



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