Techniques for Coverage-Driven Data Prefetching and Hidden Markov Based Prefetch Filtering

Abstract

The "Memory wall", the performance gap between the execution speed of the processor and memory latency, has led to the implementation of cache memory hierarchy, which strives for reducing the average memory access time due to the performance gap. The introduction of the hierarchical cache memory reduces the performance gap by improving average memory access time. However, the cache memory is still limited in reducing the gap due to its capacity. So, prefetching technique has been suggested.

First, we propose a novel hardware data prefetcher called Buffer-referred Prefetcher (BRP), which provides effective techniques for major challenges in designing a prefetcher. BRP achieves high performance gain with low hardware overhead as using multiple compressed history-based scheme that predicts diverse address patterns. BRP leverages referring mechanism so that it provides higher prefetch coverage with no additional hardware overhead.

Second, we propose Hidden Markov Model-based Prefetch Filtering (HPF), which is an additional filter layer that improves prefetch accuracy of baseline prefetcher. HPF filters out prefetch candidates that an underlying prefetcher generates by evaluating the usefulness of the prefetch candidate. Hidden Markov Model is introduced to estimate the prefetch candidate’s likelihood of being prefetch hit and miss when the candidate is issued as a prefetch. Based on measuring the likelihood, HPF increases prefetch accuracy as enabling an adjustment of prefetch requests. We also propose diverse features that are eligible to training the parameters of the HMM.