Cache Replacement Policy: Cache 替换策略

时间:2024-04-01 09:04:54

cache 是 CPU和memory中间的缓存,如果访问时选中的set已经满了,就需要从set中选择一个way

Least recently used (LRU)

replace最近最少使用的block。算法记录访问的cache block以及时间顺序,完整的实现这个方式代价比较大。实现时需要为每个cache line记录“age bit”,基于age bit 记录“Least Recently Used” 。

每次访问cache-line,所有的其他的cachline的age都需要修改。

如果访问顺序是A B C D E D F,那么访问的顺序如下:
Cache Replacement Policy: Cache 替换策略
比较有意思的是很多面试题都会实现LRU Cache,一般的做法是实现

  • 双向list,最近访问的放在list head,如果list内部已经有,就移到头部;如果list内部没有,就在head新建立插入一个,并删除末尾的
  • Map 用于在list中索引,以log(n)的复杂度找到match的节点

Pseudo-LRU (LRU)

因为LRU的代价较大,实际上并不需要严格的替换掉最近最少访问的那一个,只需要实现从最近最少访问的几个中挑选出一个作为victim,因此很多CPU实际上采用了PLRU的方式,每个cache block 只需要1bit。PLRU会有有相比LRU更低的miss rate,更低的latency(毕竟计算逻辑简单了)。

如果访问顺序是A B C D E
Cache Replacement Policy: Cache 替换策略

BIP/DIP

常规的LRU,会将最近一次访问的放置在list的head位置,在victim时从list的tail。

文章将cache replacement 分为两个部分:victim selection policy 和 insertion policy。常规的LRU都是将最新更新的insert到list的head,也就是MRU的位置,然而这样就合理吗?在传统的LRU策略中,发现超过60%的lines加载到L2 cache中之后,从insert到evict期间再没有被访问过。这就说明常规的LRU策略是有问题的。

因此考虑到这样的情况,Paper提出了将新的cache line insert到LRU的位置,也就是队尾的位置(LRU Insertion Policy)。除此之外,考虑到这样可能过于激进,又提出了将LRU和MRU insertion结合的BIP (Bimodal Insertion Policy)。

通过将BIP和LRU结合在一起,采用Set Dueling 技术实现了Dynamic Insertion Policy (DIP)。

Set Dueling 的方式就是将cache 中设置specific的set,分别实现BIP和LRU的策略,作为竞争,miss rate的效果好的,将会被剩余的set采用。
Cache Replacement Policy: Cache 替换策略
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200926204525616.png?x-oss-process=imageCache Replacement Policy: Cache 替换策略
,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hpdF9zaGFvcWk=,size_16,color_FFFFFF,t_70#pic_center)

Adaptive Insertion Policies for High Performance Caching

RRIP

欢迎关注我的公众号《处理器与AI芯片》