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].