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] 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] is The B[j] reference in Figure has a prefetch predicate of ``False'', since it has group locality with B[j+1].
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.