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

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

作　　者：韩永[1] 姚念民[1] 蔡绍滨 

机构地区：[1]大连理工大学计算机科学与技术学院,辽宁大连116024

出　　处：《计算机学报》2014年第7期1538-1547,共10页Chinese Journal of Computers

基　　金：国家自然科学基金(61073047);中央高校基本科研业务费专项资金(HEUCFT1007;HEUCF100607)资助~~

摘　　要：已有的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.

关 键 词：LRFU 自适应 替换算法 局部性 访问模式 访问分析模型 

分 类 号：TP333[自动化与计算机技术—计算机系统结构]