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] 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] and B[j] 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] is the leading reference, since it accesses the data during an earlier iteration than B[j].
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.