Next: Group Reuse Up: Reuse Analysis Previous: Temporal Reuse

### Spatial Reuse

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.

Next: Group Reuse Up: Reuse Analysis Previous: Temporal Reuse

tcm@
Sat Jun 25 15:13:04 PDT 1994