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.

Sat Jun 25 15:13:04 PDT 1994