基于局部性定量分析模型的自适应替换算法LA-LRFU

Self-Adaptive Replacement Algorithm LA-LRFU Based on Locality Quantitative Analysis Model

已有的LRFU(Least Recency Frequency Used)自适应算法在实际应用中根据经验调整λ值,缺乏对访问局部性强弱的量化分析,因而其可适用的访问模式有限.该文首先建立基于K阶马尔可夫链(K→∞)的局部性定量分析模型,在访问过程中根据统计信息实时量化局部性特征.然后以此分析模型为基础设计自适应替换算法LA-LRFU(Locality-Aware LRFU),随着访问特征的变化动态调整参数λ.最后应用Trace仿真对算法进行测试.实验结果显示,针对多种访问模式,LA-LRFU均可显著提高Cache命中率;在由多种访问模式构成的具体访问过程中,LA-LRFU能比现有的各类LRFU自适应算法更合理地调整参数λ.

In practical application, the existing LRFU self-adaptive replacement algorithms adjust the it value based on experience and lack quantitative analysis of access locality strength. Consequently, the access patterns these algorithms can be applicable for are limited. Firstly the locality quantitative analysis model is created through K-order Markov Chain （K→∞）, and in the access course the model real-timely quantizes the locality strength in accordance with the statistical information. Then the self-adaptive replacement algorithm called LA-LRFU （Locality- Aware LRFU） is designed based on the analysis model. As the access feature changes, the algo- rithm dynamically adjusts the λ value correspondingly. Finally the LA-LRFU is tested under the trace simulations. The results shows that, for several access patterns LA-LRFU can significantly improve the cache hit rate. And during the practical access process consisting of several different patterns, the LA-LRFU can adjust the 3, value more rationally than other LRFU self-adaptive replacement algorithms.