一种基于重用距离预测与流检测的高速缓存替换算法

传统的缓存替换算法由于不能适应应用程序的流式访问行为而导致缓存性能不佳.设计基于周期检测的预测方法,分析程序访存重用距离的规律性和流式访问的复杂性,提出用重用距离预测能同时适应简单流和复杂流访问模式的RDP算法.RDP的基本思想是预测重用距离并动态维护重用距离计数,动态调整缓存数据的替换顺序,通过流采样缩减存储开销.实验结果表明,RDP算法能够很好地适应程序中多样化的流访问模式,其总体性能优于LRU算法和DIP算法,在32MB缓存上比传统LRU算法平均减少了27.5%的缓存缺失.

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 32 MB cache,RDP reduces the cache misses by 27.5% on average over LRU policy.