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.