一种改进的Pseudo-LRU替换算法  

An Optimized Pseudo-LRU Replacement Algorithm

作　　者：韩立敏[1] 高德远[1] 黄小平[1] 

机构地区：[1]西北工业大学航空微电子中心,陕西西安710072

出　　处：《微电子学与计算机》2009年第6期54-57,61,共5页Microelectronics & Computer

基　　金：国家自然科学基金项目(60573107)

摘　　要：Pseudo-LRU替换算法可以避免复杂的硬件设计,所以在很多流行的Cache内存系统被使用.但是该算法的主要缺点是二叉树结构的顶层节点不能包含所有底部叶子节点的信息,在某些情况下会做出错误的替换决策.针对PLRU算法存在的问题,在分析PLRU算法的原理的基础上,通过增加处理二叉树顶层节点信息的逻辑,得到一种新的替换算法.测试结果表明,这种新的替换算法使Cache命中率提高到98.73%.Pseudo-LRU algorithm is used extensively in many Cache memory systems, because it can avoid the disadvantages of a complex hardware design. But the key disadvantage of this algorithm is that nodes at the top of the binary tree don＇t contain sufficient information about nodes at the bottom of the binary tree, and can make incorrect replacement decisions in some cases. Based on Pseudo-LRU, this paper proposes a new algorithm by adding logic of processing the information of nodes at the top of the binary tree. Experiment results reveal that PLRU-0 significantly increases hit rate to 98.73 %.

关 键 词：高速缓存 最近最少使用替换算法 伪最近最少使用替换算法 微处理器 

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