Computing spatial reuse requires a slight variation on how we compute
temporal reuse. Assuming the data are stored in row major order (an
assumption we make without loss of generality), accesses to the same
cache line will only occur when the same row is accessed.
In
addition, the row index expressions must be different, but still fall
within the size of a cache line. We can test for all of these conditions
as follows.
Two different iterations access the same row whenever all but the row index
are equivalent. This is in contrast with temporal reuse, where all
indices, including the row, must be equivalent. To extract this spatial reuse vector space, we simply replace the last row in
with zeros to create
, and solve for the nullspace of
. For
example, consider the A[i][j] reference in
Figure
, where =
, and therefore
=
. The resulting
nullspace of
is
, which indicates that the same row of A[i][j] is accessed along the inner loop.
To check whether different elements are being accessed within the same
row, we compare whether the temporal and spatial reuse vector spaces are
identical. This can occur since reusing the same data item is a degenerate case
of reusing the same cache line (i.e. the nullspace of is a subset of the
nullspace of
). If the temporal and spatial reuse vector spaces are
identical, then there is strictly temporal reuse-if they differ, then there
is spatial reuse along the vectors that are unique to the spatial reuse vector
space. For example, the A[i][j] reference in
Figure
has a temporal reuse vector space of
(i.e. there is no temporal reuse), and a spatial reuse
vector space of
; therefore unique elements within
the row are accessed along
(i.e. the inner loop).
For the B[j][0] reference, however, the temporal and spatial reuse vector
spaces are both
, and therefore there is only
temporal reuse.
Once we identify accesses to different elements within the same row, the final step is to check whether the stride is less than the cache line size. If so, then the reference has spatial reuse.