So far in this chapter, we have focused entirely on prefetching affine array references-i.e. where the access pattern is a linear function of the surrounding loop variables. These affine references were a good starting point for our compiler algorithm, since they are an important source of memory latency, and because their regular and predictable access patterns make them amenable to prefetching.
In this section, we extend our core algorithm to handle another important array access pattern: indirect references. Figure shows an example of such a pattern, where the index of the A array is itself an array reference (index[i]). Indirect references commonly occur in scientific and engineering applications such as sparse-matrix algorithms (to look up the sparse element in a dense storage array), particle-in-windtunnel simulations (to look up the cell containing the particle), etc. We begin in Section by describing the modifications to our prefetching algorithm that are necessary for handling indirect references. Then in Section , we present experimental results to evaluate the success of our extended algorithm.