摘要
已有的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.
出处
《计算机学报》
EI
CSCD
北大核心
2014年第7期1538-1547,共10页
Chinese Journal of Computers
基金
国家自然科学基金(61073047)
中央高校基本科研业务费专项资金(HEUCFT1007
HEUCF100607)资助~~
关键词
LRFU
自适应
替换算法
局部性
访问模式
访问分析模型
LRFU; self-adaptation; replacement algorithm; locality; access pattern; accessanalysis model