Although vector space representations are attractive when we compute data locality, a more convenient representation for the purpose of scheduling prefetches is to associate a logical predicate with each reference such that the predicate is true during each dynamic instance when the reference is expected to suffer a cache miss. These miss instances are precisely the cases we want to prefetch, and therefore we refer to these predicates as prefetch predicates. In this subsection we describe how the prefetch predicates are constructed based on the locality vector spaces.
The expected dynamic miss instances vary according to the different types of locality. If an access has no locality, it will miss on every iteration. 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. If an access has group locality and is not the leading reference, it will hardly ever suffer cache misses.
Table 
shows the prefetch predicates corresponding
to each type of locality. To simplify this exposition (and without loss of
generality), we assume here that the iteration count starts at 0, and that
the data arrays are aligned to start on a cache line boundary.
As we see in
Table , the prefetch predicate for a reference with
no locality is simply ``True'', since misses are expected to occur on
every iteration. For an access with temporal locality, the prefetch
predicate is only true during the first loop iteration (i.e. when ``i = 0''). With spatial locality, the prefetch predicate contains a modulo
function such that it is true each time a cache line boundary is crossed
(i.e. when ``i mod = 0'', where
is the number of accesses
per cache line). Finally, for references with group locality that are not
leading references, the prefetch predicate is ``False'', since they
are not expected to suffer a significant number of misses and hence should
not be prefetched.
The prefetch predicate of a reference within a multi-level loop nest is
simply the conjunction of all the predicates imposed by each form of
locality within the loop nest. For example, the A[i][j] reference in
Figure has no locality with respect to the i
loop, which corresponds to a predicate of ``True'', and spatial
locality along the j loop, which corresponds to a predicate of
``(j mod 2) = 0''; therefore the overall prefetch predicate for A[i][j] is
Similarly, the B[j+1][0] reference in this example has temporal
locality along the i loop, which corresponds to a predicate of
``i = 0'', and no locality along the j loop, which
corresponds to a predicate of ``True''; hence the overall prefetch
predicate for B[j+1][0] is
The B[j][0] reference in Figure
has a prefetch
predicate of ``False'', since it has group locality with B[j+1][0].
Once these prefetch predicates have been constructed, our algorithm has answered the question of ``what to prefetch''; the answer is each reference should be prefetched whenever its prefetch predicate is true. Now that the analysis phase of our algorithm is complete, the next step is to schedule the prefetches, as we describe in the next section.