Cache Replacement Policy: Cache 替换策略
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，那么访问的顺序如下：
比较有意思的是很多面试题都会实现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
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采用。
Adaptive Insertion Policies for High Performance Caching