近期cache替代算法和模型综述

《近期cache替代算法和模型综述》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、近期Cache替代算法和模型综述1引言尽管近几年来，各种提升性能的体系结构和算法层出不穷，CacheReplacement的效率依然非常重要。在今日的双缓存的CMP体系结构中，第一层通常是处理器私有的，第二层缓存则一般是多处理器共享的。目前这种结构在遇到cachemiss的有以下两个问题[1]：1)当一个处理器发生miss的时候，该处理器在stall的同时向内存请求调度数据。这个时候由于chip之间的带宽有限，无形中增加了通讯竞争，从而导致所有处理器的性能下降；2)当一个miss发生的时候，需要的cacheline会从内存中调度到二级共享缓存里面。由

2、于二级缓存可用空间有限，直接导致其他处理器为争夺空间而增加了cachemiss。这样，一个处理器的cachemiss也会潜在的增加其他处理器的cachemiss；所以，一个处理器的cachemiss会从以下三方面导致真个CMP的性能下降，即目标处理器stall；潜在的消耗了宝贵的off-chip贷款；可能增加其他处理器的cachemiss。LRU是目前体系中用的最多的cache替代算法。但是，应用程序的访问模式除了不全部都是LRU偏好的，存在着以下一些缺陷：1)缺少重用信息，遇到内存需求强烈的程序时，效率低下，性能不及LFU；2)遇到带有周期性性质，

3、工作集大于缓存大小的应用程序会发生抖动，效率不及MRU；3)不区分miss的代价，总是以miss的总数表示处理器stall的次数，在某些体系下没有很好的减少处理器stall的次数而影响了性能；针对以上几点传统LRU算法的缺陷，近期解决思路主要集中在两个方面：1)改进LRU算法，以解决某类传统LRU解决不好的问题，比如LRU-LFU[1],BIP[2],LIN[3]；2)使用自适应混合模型两个方面，以一方面解决LRU的效能问题，又可以通过自适应的调整来实现通用性,比如AC[4]模型，SBAP[3]和SetDueling[2]；于此同时，也有人针对一级缓

4、存的直接映射模式的缺点如访问不均衡性提出了自己的解决方案，以最小硬件的代价来获得均匀访问并提高性能，如B-cache[5]。无论哪种解决方案，其目标不过以下几点：1)尽可能的减少miss带来的性能损失；2)尽可能少的硬件代价；3)尽可能少的额外能源需求，甚至在总体上降低能耗；4)尽可能容易实现；5)尽可能的通用，可以满足不同的平台，不同的应用。以下几章将从不同的类型和角度出发，对近期cache算法、模型进行分类、比较和介绍。其中第二章主要介绍几类通过改善LRU在某些环境下表现的算法；第三章主要介绍混合模型，如何自适应的调整和选择更好的替代算法；第四章

5、介绍其他思路的方法，主要是改进第一层缓存非均匀访问情况；最后一章进行了总结。1改善LRU算法该类型解决方案通过分析LRU在某类访问模式、工作集以及体系结构下的缺陷，有针对性的将其与一些特性比如访问频率、miss代价以及周期访问特性等互相融合以改进原有的LRU算法。2.1结合重用信息HaakonDybdahl,PerStenstroem和LasseNatvig提出了基于LRU并以访问频率加强的cache替换算法LRUbasedreplacementalgorithmaugmentedwithfrequencyofaccess[1]该算法针对CMP的共享

6、缓存，在考虑accesspattern时同时考虑频率和访问时间，可提高对那些内存需求强烈的应用的效率。该替换算法以保护那些潜在的将来会重新访问的cacheline免于被替换出去。它同时结合了LRU和访问频率概念，在选择替换cache时，在一个LRU块集合里面再挑选被访问次数最少的块。同时它也能与WBscheme[6]结合，使得系统能够在发现该算法不能提高性能的时候自动关掉。改进二级缓存的性能能够减少芯片外cache的带宽需求和处理器的停顿此数。通过增强替换算法使其能够保护那些很有可能被访问到的cache块不被替换出去，以提高二级缓存的性能，进而提供总

7、体性能。算法实现细节如下：在每个cacheline上增加一个计数器，用来和LRU算法一起挑选替换对象。先用LRU算法挑选一系列潜在可替换者，然后在里面挑选访问频率最低的作为替代者。同时采用选择性缓存策略，即有时候直接将请求的数据块放进一级缓存，但没有在二级缓存内替换相应cache并放入数据，减少不必要的冲突miss。该算法的硬件结构如下：图2.1cache结构此外，为了实现switching，该设计还需要为二级缓存的某些cache集增加shadowtags，并另第二种算法跑在这个shadowtags上，以此代表第二种算法对整个二级缓存的工作性能。对应

8、cache块上的计数器在遇到以下的几种访问时会被修改：1)Hit：无论是writehits还是readhit