Since locality can only occur if there is reuse, the first step in locality
analysis is determining the intrinsic data reuse through reuse
analysis. Reuse analysis attempts to discover those instances of array
accesses that refer to the same memory line.
There are three
kinds of reuse, which parallel the three kinds of locality described in
Section 
: temporal, spatial, and group. The
difference is that while reuse is an inherent property of code, locality
also depends on the ability of the cache to retain data. Therefore if we
had an infinitely large cache, which would retain data perfectly, reuse
would be equivalent to locality.
Our reuse analysis step is nearly identical to that proposed by Wolf and Lam [87][86], which we will briefly summarize in this subsection. Our terminology is slightly different, however, since we tailor our reuse categories to more closely match our prefetching algorithm. What they refer to as self-temporal reuse is the same as what we refer to as temporal reuse, and corresponds to whenever a given array reference accesses the same data location multiple times within a loop nest. However, whereas they define self-spatial reuse to include accesses anywhere within the same cache line, we define spatial reuse only as accesses to different locations within the same line. Therefore their definition of self-spatial reuse includes self-temporal reuse as a subset, while our definition of spatial reuse does not. Finally, what they call group-spatial reuse is the same as what we call group reuse, and occurs whenever different array references access the same cache line. We do not treat their group-temporal reuse (different references accessing exactly the same location) as a special case, since it is a subset of our group reuse. As we will demonstrate later in this chapter, our categories of reuse correspond to different cases for scheduling prefetches.
A key simplification of reuse analysis is that rather than trying to
precisely compute the sets of iterations (i.e. actual loop index values)
that use the same data, which is prohibitively expensive, we instead
succinctly capture the intuitive notion that reuse is carried by a specific
loop with the following mathematical formulation. We represent an
-dimensional loop nest as a polytope in an
-dimensional iteration
space (i.e. a finite convex polyhedron bounded by the loop bounds), with
the outermost loop represented by the first dimension in the space. We
represent the shape of the set of iterations that use the same data by a
reuse vector space [87]. The remainder of this
subsection describes how this mathematical representation is used to
compute temporal, spatial, and group reuse.