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 [24]. For example, references
`B[j][0]` and `B[j+1][0]` in Figure are
uniformly generated, while references `C[i]` and `C[j]` in
Figure are not. In the former case, `B[j][0]` is accessing data brought into the cache by `B[j+1][0]` 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][0]` and `B[j+1][0]` 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.

Sat Jun 25 15:13:04 PDT 1994