Next: Temporal Reuse Up: Locality Analysis Previous: An Example

Reuse Analysis

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.

Next: Temporal Reuse Up: Locality Analysis Previous: An Example

Sat Jun 25 15:13:04 PDT 1994