Intuitively, a data access has locality (i.e. hits in the cache) if it is
reusing a cache line that was referenced sometime in the past and
this previous reference occurred recently enough that the data is still in
the cache. We can isolate these instances by intersecting the reuse
vector space with the localized vector space, i.e.
For example, the B[j+1][0] reference in
Figure 
(a) has a temporal reuse vector space of
(i.e. there is temporal reuse along the outer
loop), as described earlier in Section
. If both
loops in the nest are localized (as in Figure (a)),
then the temporal locality vector space is
i.e. the temporal reuse does result in temporal locality.
However, if only the innermost loop is localized (as in
Figure (b)), then the temporal locality vector space
is
i.e. there is no temporal locality.
Similar mathematical treatment determines whether spatial reuse translates
into spatial locality (i.e. ).
For group reuse, the localized iteration space is used to partition the references that share group reuse into equivalence classes. An equivalence class is a set of references for which group locality exists, and therefore can be treated as a single reference. Equivalence classes are computed by finding a particular solution to the difference between the array index equations of two references. If a particular solution exists, and if it is within the localized iteration space, then the references belong in the same equivalence class. In addition, the particular solution result is used to determine the leading reference within an equivalence class, which is the reference within the set that will actually suffer the cache miss. The compiler only has to schedule prefetches for leading references.
For example, is a particular solution to the
difference between the B[j+1][0] and B[j][0] references in
Figure
. Even if the localized iteration space
includes only the innermost loop, these two references will be within the
same equivalence class since
Also, since the first non-zero element in
is positive, this
indicates that B[j+1][0] is the leading reference, since it
accesses the data during an earlier iteration than B[j][0].
As a counterexample, references A[i+1][j] and A[i][j] in
Figure share group reuse but not group locality. In this case, the particular solution is , and the localized iteration space contains only the innermost loop.
Therefore, since
A[i+1][j] and A[i][j] do not share group locality, and will be
partitioned into separate equivalence classes.
After computing the localized iteration space and intersecting it with the reuse vector space, we now have a precise description of data locality expressed as a locality vector space. The final step in our locality analysis algorithm is converting this vector space representation of data locality into prefetch predicates, as described in the next subsection.