A Cache Replacement Policy Based on Reuse Distance Prediction and Stream Detection

Traditional cache replacement policy fails to accommodate the special streaming access patterns exhibited by many modern applications, leading to decreased cache performance, which is known as cache thrashing. This paper proposes a new reuse distance prediction mechanism based on period detection, which is able to capture the periodic regularity in reuse distance sequences. Then it analyzes the regularity in reuse distances and the complexity in streaming access sequences exposed by applications. Finally, a new replacement algorithm, RDP in short, is presented to accommodate both simple and complicate streaming access patterns with the proposed reuse distance prediction mechanism. The basic idea of RDP is to predict the reuse distance in memory accesses, maintain the reuse distance counters dynamically, and thus adjust the replacement priority of cache blocks dynamically according to the prediction results, against traditional replacement decision. In addition, it reduces storage overhead with stream sampling. The experiments show that RDP adapts well to diverse streaming access patterns in programs, and outperforms both LRU and DIP policies. On large last-level caches, RDP improves the cache performance across one class of programs with strong streaming access patterns significantly. For example, on a 32MB cache, RDP reduces the cache misses by 27.5% on average over LRU policy.