Next: Loop Splitting Up: Locality Analysis Previous: Localized Iteration Space

The Prefetch Predicate

The benefit of locality differs according to the type of reuse. If an access has temporal locality within a loop nest, only the first access will possibly incur a cache miss. If an access has spatial locality, only the first access to the same cache line will incur a miss.

To simplify this exposition, we assume here that the iteration count starts at 0, and that the data arrays are aligned to start on a cache line boundary. Without any locality, the default is to prefetch all the time. However, the presence of temporal locality in a loop with index means that prefetching is necessary only when . The presence of spatial locality in a loop with index means that prefetching is necessary only when , where is the number of array elements in each cache line. Each of these predicates reduces the instances of iterations when data need to be prefetched. We define the prefetch predicate for a reference to be the predicate that determines if a particular iteration needs to be prefetched. The prefetch predicate of a loop nest with multiple levels of locality is simply the conjunction of all the predicates imposed by each form of locality within the loop nest.

Figure 2(c) summarizes the outcome of the first step of our prefetch algorithm when applied to our example. Because of the small loop iteration count, all the reuse in this case results in locality. The spatial and temporal locality each translate to different prefetch predicates. Finally, since B[j][0] and B[j+1][0] share group reuse, prefetches need to be generated only for the leading reference B[j+1][0].



Next: Loop Splitting Up: Locality Analysis Previous: Localized Iteration Space


Robert French