A Data Prefetch Mechanism for Accelerating General-Purpose Computation

We describe a simple hardware device, the Indirect Reference Buffer , that can be used to speculatively prefetch pointer-linked, sparse matrix, or dense matrix data structures into primary data caches. The indirect reference buffer (IRB) identifies recurrent patterns of memory access in such computations, and uses these patterns to prefetch data that it anticipates will be used shortly by the processor, thereby reducing the cache miss penalty associated with such references. Previously described schemes (both hardware and software) have focused on prefetching regular array references only, which makes them inadequate for computations that generate complex memory access patterns. The IRB rectifies these deficiencies. In addition, because of the decoupling between prefetch pattern recognition and the actual prefetch address generation in the IRB design, it is possible to tune the device's behavior for processors with varying memory subsystems. The IRB is designed to be situated between t..