Cache动态插入策略模型研究

J4 ›› 2013, Vol. 35 ›› Issue (10): 159-165.

Cache动态插入策略模型研究

石文强，倪晓强，金作霖，张民选

（国防科学技术大学计算机学院，湖南长沙 410073）

收稿日期:2011-08-11 修回日期:2011-12-08 出版日期:2013-10-25 发布日期:2013-10-25
基金资助:
国家自然科学基金资助项目（60970036，61003075）

An analytical model for Cache dynamic insertion replacement

SHI Wenqiang,NI Xiaoqiang,JIN Zuolin,ZHANG Minxuan

(School of Computer Science,National University of Defense Technology,Changsha 410073,China)

Received:2011-08-11 Revised:2011-12-08 Online:2013-10-25 Published:2013-10-25

摘要/Abstract

摘要：

多核下，末级Cache容量、组相联数不断增大，传统Cache替换算法LRU会出现Cache死块增多、Cache有效利用率下降等问题。Cache动态插入策略可以有效地避免LRU算法中出现的这些问题，因而受到了广泛的关注。但是，目前对Cache插入策略的研究只停留在策略水平上，缺乏定量的模型研究。针对此问题，提出了一个Cache插入策略的解析模型，该模型以应用的重用信息为输入，使用状态概率递归计算的方法，可预测不同插入策略下Cache的失效率。SPEC2006模拟验证表明，模型的精度较高，最大绝对误差为15.6%，平均绝对误差为3.1%。

关键词: 多核Cache, Cache替换策略, 动态插入策略, 递归概率模型

Abstract:

Chip MultiProcessor(CMP) commonly employs last level cache with large capacity and high associativity, but the traditional cache replacement policy LRU gradually loses its performance due to the cache dead block problem caused by high cache associativity. As a result, dynamic insertion policy, which can effectively solve such problems of LRU, has received much more attention. However, current researches mainly focus on the replacement policy, while there are few studies on the quantitative analysis of the replacement policies. This paper presents an entire new analytical cache model for cache dynamic insertion replacement. The model, which inputs the application's reuse distance information and employs the recursive iterating probability method, is always able to give an accurate miss rate prediction for different insertion policies. The simulation results reveal that the average absolute error of the model is 3.1% and the max is 15.6%。

Key words: CMP cache;cache replacement policy;dynamic insertion policy;recursive probability model

石文强，倪晓强，金作霖，张民选. Cache动态插入策略模型研究[J]. J4, 2013, 35(10): 159-165.

SHI Wenqiang,NI Xiaoqiang,JIN Zuolin,ZHANG Minxuan. An analytical model for Cache dynamic insertion replacement [J]. J4, 2013, 35(10): 159-165.