As we mentioned at the outset of Section , reuse only translates to locality if the subsequent use of data occurs before the data are displaced from the cache. The likelihood of displacement depends on (i) the amount of data brought into the cache between reuses, which is influenced by factors such as loop iteration counts, and (ii) the ability of the cache to retain data, which depends on factors such as the cache size. In this subsection, we describe how our algorithm takes such factors into account to compute locality through the notion of a localized iteration space.
We begin with the example in Figure which illustrates how loop iteration counts and cache size affect locality. The code in Figures (a) and (b) is similar to our original example in Figure (a), except that the upper bound of the j loop is small in Figure (a) (8 iterations) and large in Figure (b) (10,000 iterations). The B[j+1] reference in both cases has temporal reuse along the outer loop (as discussed earlier in Section ). In Figure (a), this reuse is likely to result in temporal locality since the eight j iterations bring only 192 bytes into the 8 Kbyte cache between reuses of the same B[j+1] locations. In Figure (b), however, the temporal reuse does not result in locality since the 10,000 j iterations will sweep 240 Kbytes of data through the 8 Kbyte cache, flushing a given B[j+1] location before it can be reused.
Predicting accurately whether data will remain in the cache is infeasible for the compiler, due to factors such as symbolic loop iteration counts, cache mapping conflicts, etc. Rather than trying to represent exactly which reuses would result in cache hits, we adopt Wolf and Lam's approach of capturing only the dimensionality of the iteration space that has data locality . We define the localized iteration space to be the set of loops that can exploit reuse. For example, the localized iteration space includes both loops in Figure (a), and only the innermost loop in Figure (b). In the latter case, data fetched in the loop body will be available to subsequent iterations within the same innermost loop, but not to subsequent iterations of the outer loop.