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.

Sat Jun 25 15:13:04 PDT 1994