Previous    Next

LOOP INTERCHANGE

The most fundamental way of using the cache effectively is the reuse of cached data. When nested loops access memory, successive iterations of a loop often reuse the same word, or use adjacent words that occupy the same cache block. If it is the innermost loop whose iterations reuse the same values, then there will be many cache hits. But if one of the outer loops reuses a cache block, it may be that execution of the inner loop stomps through the cache so heavily that by the time the next outer-loop iteration executes, the cache block will have been flushed. Consider the following nested loops, for example.

for i ← 0 to N - 1
 for j ← 0 to M - 1
 for k ← 0 to P - 1
 A[i, j, k] ← (B[i, j - 1, k] + B[i, j, k] + B[i, j + 1, k])/3


The value B[i, j + 1, k] is reused in the next iteration of the j loop (where its "name" is B[i, j, k]), and then is reused again in the iteration after that. But in the meantime, the k loop brings 3P elements of the B array, and P elements of the A array, through the cache. Some of these words may very well conflict with B[i, j + 1, k], causing a cache miss the next time it is fetched. The solution in this case is to interchange the j and k loops, putting the j loop innermost:

for i ← 0 to N - 1
 for k ← 0 to P - 1
 for j ← 0 to M - 1
 A[i, j, k] ← (B[i, j - 1, k] + B[i, j, k] + B[i, j + 1, k])/3


Now B[i, j, k] will always be a cache hit, and so will B[i, j − 1, k]. To see whether interchange is legal for a given pair of loops, we must examine the data-dependence graph of the calculation. We say that iteration (j, k) depends on iteration (j′, k′) if (j′, k′) computes values that are used by (j, k) (read-after-write), or stores values that are overwritten by (j, k) (write-after-write), or reads values that are overwritten (write-after-read). If the interchanged loops execute (j′, k′) before (j, k), and there is a dependence, then the computation may yield a different result, and the interchange is illegal. In the example shown above, there is no dependence between any iterations of the nested loops, so interchange is legal.

See the Further Reading section for a discussion of the analysis of dependence relations for array accesses in nested loops.


JaVaScreenshot Previous    Next
Comments