Next: Locality Analysis Up: Design and Evaluation of Previous: An Overview

A Prefetch Algorithm

In this section, we will use the code in Figure 2(a) as a running example to illustrate our prefetch algorithm. We assume, for this example, that the cache is 8K bytes, the prefetch latency is 100 cycles and the cache line size is 4 words (two double-word array elements to each cache line). In this case, the set of references that will cause cache misses can be determined by inspection (Figure 2(b)). In Figure 2(d), we show code that issues all the useful prefetches early enough to overlap the memory accesses with computation on other data. (This is a source-level representation of the actual code generated by our compiler for this case). The first three loops correspond to the computation of the i=0 iteration, and the remaining code executes the remaining iterations. This loop splitting step is necessary because the prefetch pattern is different for the different iterations. Furthermore, it takes three loops to implement the innermost loop. The first loop is the prolog, which prefetches data for the initial set of iterations; the second loop is the steady state where each iteration executes the code for the iteration and prefetches for future iterations; the third loop is the epilog that executes the last iterations. This software pipelining transformation is necessary to issue the prefetches enough iterations ahead of their use[24][18].

This example illustrates the three major steps in the prefetch algorithm:

  1. For each reference, determine the accesses that are likely to be cache misses and therefore need to be prefetched.
  2. Isolate the predicted cache miss instances through loop splitting. This avoids the overhead of adding conditional statements to the loop bodies.
  3. Software pipeline prefetches for all cache misses.
In the following, we describe each step of the algorithm and show how the algorithm develops the prefetch code for the above example systematically.


Robert French