Next: Localized Iteration Space Up: Locality Analysis Previous: Locality Analysis

Reuse Analysis

Reuse analysis attempts to discover those instances of array accesses that refer to the same cache line. There are three kinds of reuse: temporal, spatial and group. In the above example, we say that the reference A[i][j] has spatial reuse within the innermost loop since the same cache line is used by two consecutive iterations in the innermost loop. The reference B[j][0] has temporal reuse in the outer loop since iterations of the outer loop refer to the same locations. Lastly, we say that different accesses B[j][0] and B[j+1][0] have group reuse because many of the instances of the former refer to locations accessed by the latter.

Trying to determine accurately all the iterations that use the same data is too expensive. We can succinctly capture our intuitive characterization 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, 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[29].

For example, the access of b[j][0] in our example is represented as B(), so reuse occurs between iterations and whenever That is, temporal reuse occurs whenever the difference between the two iterations lies in the nullspace of , that is, . We refer to this vector space as the temporal reuse vector space. This mathematical approach succinctly captures the intuitive concept that the direction of reuse of B[j][0] lies along the outer loop. This approach can handle more complicated access patterns such as C[i+j] by representing their reuse vector space as .

Similar analysis can be used to find spatial reuse. For reuse among different array references, Gannon et al. observe that data reuse is exploitable only if the references are uniformly generated; that is, references whose array index expressions differ in at most the constant term[11]. For example, references B[j][0] and B[j+1][0] are uniformly generated; references C[i] and C[j] are not. Pairs of uniformly generated references can be analyzed in a similar fashion[29]. For our example in Figure 2(a), our algorithm will determine that A[i][j] has spatial reuse on the inner loop, and both B[j][0] and B[j+1][0] share group reuse and also have temporal reuse on the outer loop.

Next: Localized Iteration Space Up: Locality Analysis Previous: Locality Analysis

Robert French