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.
