Feasibility analysis of correlation based prefetching using digital signal processing

As the gap between processor performance and memory performance continues to broaden with time, techniques to hide memory latency such as correlation based prefetching become exceedingly important. When a memory reference issued by the processor misses the level one cache, the request propagates down the memory hierarchy until it finally finds the requested datum. With each layer traversed, the latency grows exponentially. Prefetching is a technique used to hide this latency by attempting to predict which memory references will be requested in the near future, and then load them into cache before they are needed. This work investigates the use of digital signal processing techniques in designing an effective prefetch algorithm. The algorithm proposed in this work uses the Kalman Filter as the basic digital signal processing block. The sequence of memory address references with respect to time is interpreted as a digital signal. By applying Kalman filtering techniques, a robust prediction algorithm is presented to predict future miss references based on the pattern of previous miss references. The algorithm was simulated using 40 benchmark programs from the Olden, MediaBench, and SPEC benchmark suites for the Alpha 21264 and the PISA (a MIPS-like ISA) instruction set architectures. A main difference between these two ISAs is that the Alpha 21264 ISA contains software prefetch instructions, and the PISA instruction set architecture does not. The simulations place a prefetcher unit between the level one data cache and the level two unified cache. SimpleScalar simulation results for a broad set of benchmark programs using 32 Kalman filter blocks show an average of 6.5% speedup for the Alpha 21264 ISA, and an average of 5.6% speedup for the PISA instruction set architecture for those benchmark programs which have a potential speedup from prefetching greater than 10%