For reuse among different array references, Gannon et al. observe that data reuse is exploitable only if the references are uniformly generated; that is, references whose array index expressions differ in at most the constant term . For example, references B[j] and B[j+1] in Figure are uniformly generated, while references C[i] and C[j] in Figure are not. In the former case, B[j] is accessing data brought into the cache by B[j+1] during the previous j iteration, making it very likely that this reuse will result in locality. In the latter case, only iterations near the diagonal (i.e. when i = j) are likely to have exploitable reuse. Thus we will only consider group reuse among sets of uniformly generated references.
Although uniformly generated references are the likely candidates for group reuse, it is still possible that they never access the same data. For example, the C[2i][j] and C[2i+1][j] references in Figure are uniformly generated, but never overlap since C[2i][j] only accesses even rows while C[2i+1][j] only accesses odd rows of matrix C. To exclude such cases, we check whether a particular solution to the common transformation matrix exists that yields the constant difference between the two array index functions. We express this mathematically by saying that two distinct references A and A access the same data if and only if
For example, the two references in Figure would be represented as These two references access the same data if an integer solution exists to However, there is no integer solution in this case, since there is no integer such that . In contrast, the B[j] and B[j+1] references in Figure access the same data since is one particular solution to
While equation () specifies cases where distinct references access the same data item, we are interested in cases where distinct references access the same cache line. In Wolf and Lam's terminology, the former case is group-temporal reuse, and the latter case is group-spatial reuse. We refer to group-spatial reuse simply as group reuse, since it is a superset of group-temporal reuse and we have no need to distinguish the two cases.
Figure shows an example of two references that access the same cache lines, although never the same data items. Similar to our earlier example in Figure , C[i][2j] and C[i][2j+1] never overlap since they only access even and odd columns of C, respectively. However, since they access adjacent elements within the same row on each iteration, they will reuse the same cache lines, provided the lines are long enough to hold at least two array elements.
To detect all of these group reuse cases (including group-spatial, we modify equation () slightly by replacing the last rows in , , and with zeros to form , , and , respectively. We therefore say that two distinct references A and A have group reuse if and only if
and also provided that the constant difference between the last rows of and is less than the cache line size divided by the element size. For the C[i][2j] and C[i][2j+1] references in Figure , where , , and , and hence , , and , group reuse only occurs if an integer solution exists to Since is a particular solution to this equation, and given a cache line size of at least two array elements, group reuse does occur for this case.
Now that we have demonstrated how the various types of reuse can be computed, the next step in our algorithm is determining when reuse actually results in a locality benefit, given that we have a finite rather than an infinite cache. To make this distinction, we use the concept of a localized iteration space, which is described in the following subsection.