对页面5的访问并没有在Cache中命中，此时需要一个Free页面进行页面替换。LIRS算法首先淘汰在Q中页面7，同时将这页面在S中的状态更改为不在Cache命中；之后页面8从S落到Q中，状态从LIR迁移到HIR，但是这个页面仍在Cache中，需要重新压栈；页面5没有在Cache中命中，但是在S中命中，需要将其移出后重新压栈，状态改变为在Cache中命中。本篇不再介绍LIRS算法的实现细节，对此有兴趣的读者可以参照[40][41]。

而后出现的Clock-Pro算法是LIRS思想在Clock算法中的体现。Clock-Pro和LIRS都为LIRS类算法。其中Clock-Pro算法实现开销更小，适用于操作系统的Virtual Memory Management，并得到了广泛的应用，Linux和NetBSD使用了该算法；LIRS算法适用于I/O存储领域中，mySQL和Apache Derby使用了该算法。LIRS算法较为完美地解决了Weak Access Locality Access Pattern的处理。在LIRS算法出现之后，还有许多页面替换算法，这些后继算法的陆续出现，一次又一次证明了尚未出现更好的算法在这些领域上超越LIRS算法。

LIRS和Clock-Pro算法在这个领域的地位相当于Two-Level Adaptive Branch Prediction在Branch Prediction中的地位。在详细研读[40][42]的细节之后，发现更多的是作者的实践过程。LIRS算法类不是空想而得，是在试错了99条路之后的发现。这是创新的必由之路。

在掌握必要的基础知识后，也许我们最应该做的并不是研读他人的书籍和论文，更多的是去实践。经历了这些艰辛的实践过程，才会有真正的自信。这个自信不是盲从的排他，是能够容纳更多的声音，尽管发出这个声音的人你是如此厌恶。

与微架构设计相比，在操作系统和应用层面可以有更多的资源和更多的时间，使用更优的页面替换算法。虽然在操作系统和应用层面对资源和时间依然敏感，但是在这个层面上使用的再少的资源和再短的时间放到微架构中都是无比巨大。在微架构的设计中，很多在操作系统和应用层面适用的算法是不能考虑的。

假设一个CPU的主频为3.3GHz，在每一个Cycle只有300ps的情况之下，很多在操作系统层面可以使用的优秀算法不会有充足的时间运行。虽然LRU算法在Simplicity和Adaptability上依然有其优势，在微架构的设计中依然没有得到广泛的应用。即便是LRU算法，在Cache的Ways Number较大的情况之下也并不容易快速实现。当Way Number大于4后，LRU算法使用的Link Lists方式所带来的延时是Silicon Design不能考虑的实现方式。更糟糕的是，随着Way Number的增加，LRU算法需要使用更多的状态位。

下文讨论的Cache Block替换算法针对N-Way Set Associative组织方式。在这种情况下，Cache由多个Set组成，存储器访问命中其他Set时，不会影响当前Set的页面更换策略，所谓的替换操作是以Set为单位进行的。为简化起见，假设下文中出现的所有存储器访问都是针对同一个Set，不再考虑访问其他Set的情况。

通常情况，在N-Way Set Associative的Cache中，快速实现Full LRU最多需要N×(N-1)/2个不相互冗余的状态位，理论上的最小值是Floor(LOG₂(N!))个状态位[23]。因此当Way Number大于4之后，所需要的状态位不是硬件能够轻易负担的，所需要的计算时间不是微架构能够忍受的。这使得更多的微架构选用了PLRU算法进行Cache Block的Replacement。

与LRU算法相比，PLRU算法使用了更少的存储空间，查找需要替换页面的时间也较短，而且从Miss Rate指标的考量上与LRU算法较为类似，在某些特殊场景中甚至会优于LRU算法[36]，从而在微架构的设计中得到了大规模的应用。

PLRU算法有两种实现方式，分别为MRU-Based和Tree-Based方式。MRU-Based PLRU的实现方式是为每一个Cache Block设置一个MRU Bit，存储器访问命中时，该位将设置为1，表示当前Cache Block最近进行过访问。当因为Cache Miss而进行Replacement时，将寻找为0的MRU Bit，在将其替换的同时，设置其MRU Bit为1。

采用这种方式需要避免同一个Set所有Cache Block的MRU Bit同时为1而带来的死锁。考虑一个4-Way Set Associative的Cache，当在同一个Set只有一个Cache Block MRU Bit不为1时，如果CPU对这个Cache Block访问并命中时，则将该Cache Block的MRU Bit设置为1，同时将其他所有Cache Block的MRU Bit设置为0，如图2‑14所示。

 在上图中，假设MRU[0:3]的初始值为{1, 1, 0, 0}，当一次存储器访问命中 Cache Block2时，MRU[0:3]将迁移为{1, 1, 1, 0}；下一次访问命中Cache Block3时，MRU[0:3]的第3位置1，为了避免MRU[0:3]所有位都为1而出现死锁，此时其他位反转为0，即MRU[0:3]迁移为{0, 0, 0, 1}；再次命中Cache Block1时，将迁移为{0, 1, 0, 1}。

有些量化分析结果[36]认为MRU-Based实现方式在Cache Miss Ratio的比较上，略优于Tree-Based PLRU方式。但是从实现的角度上考虑，使用MRU-Based实现时，每一个Set都需要增加一个额外的Bit。这并不是问题关键，重要的是MRU-Based实现在搜索为第一个为0的MRU Bit时需要较大的开销，也无法避免为了防止MRU Bits死锁而进行反转开销。

本篇所重点讨论的是Tree-Based PLRU实现方式。下文将以一个4-Way Set Associative的Cache说明PLRU的使用方式，使用更多Way的方式可依此类推。在4-Way情况之下，实现PLRU算法需要设置3个状态位B[0~2]字段，分别与4个Way对应；同理在8-Way情况下，需要7个状态位B[0~7]；而采用N-Way Set Associative需要N-1个这样的状态位，是一个线性增长。Tree-Based PLRU使用的替换规则如图2‑15所示。

 在Cache Set初始化结束后，B0~2位都为0，此时在Set中的Cache Block的状态为Invalid。当处理器访问Cache时，优先替换状态为Invalid的Cache Block。只有在当前Set中，所有Cache Block的状态位都不为Invalid时，Cache控制逻辑才会使用PLRU算法对Cache Block进行替换操作。

在Tree-Based PLRU实现中，搜索过程基于Binary Search Tree，在N较大时，其搜索效率明显高于MRU-Based PLRU。在这种实现中，当所有Cache Block的状态不为Invalid时，将首先判断B0的状态，之后决定继续判断B1或者B2。如果B0为0，则继续判断B1的状态，而忽略B2的状态；如果B0为1，则继续判断B2的状态，而忽略B1的状态。

举例说明，如果B0为0而且B1为0时，则淘汰L0；否则淘汰L1。如果B0为1而且B2为0，则淘汰L2；否则淘汰L3。淘汰合适的Cache Block后，B0~B2状态将被更新。值得注意的是，除了发生Cache Allocate导致的Replacement之外，在Cache Hit时，B0~B2的状态同样需要更新。Cache Set替换状态的更新规则如表2-1所示。

表2-1 PLRU Bits的更新规则

以上更新规则比较容易记忆。从图2‑15中可以发现在替换L0时，需要B0和B1为0，与此对应的更新规则就是对B0和B1取反，而B2保持不变；同理替换L3时，需要B0和B2为1，与此对应的更新规则就是对B0和B2取反，而B1保持不变。

依照以上规则，我们简单举一个实例说明PLRU算法的替换和状态迁移规则。假设连续三次的存储器访问分别命中了同一个Set的不同Way，如顺序访问Way 3，0和2。其B0~2的状态迁移如图2‑16所示。

 由以上访问序列可以发现，当CPU访问Way 3，0和2之后，B0~B2的状态最后将为0b011，此时如果Cache Block需要进行Replacement时，将优先替换Way 1。这个结果与期望相符，对此有兴趣的读者，可以构造出一些其他访问序列，使得最终结果与LRU算法预期不符。这是正常现象，毕竟PLRU算法是Pseudo的。

根据以上说明，我们讨论与Tree-Based PLRU算法的相关的基本原则。由上文的描述可以发现当Cache收到一个存储器访问序列后，Cache Set的替换状态将根据PLRU算法进行状态迁移，我们假设这些存储器访问序列都是针对一个Set，而且存储器访问使用的地址两两不同。这是因为连续地址的访问不会影响到Cache Set的替换状态，二是因为如果访问序列是完全随机的，几乎没有办法讨论Cache的替换算法。满足这一要求，而且最容易构造的序列是，忽略一个地址的Offset字段，Index保持不变，其上地址顺序变化的存储器访问序列。

为了进一步描述Cache Block的替换算法，我们引入Evict(k)和Fill(k)这两个参数，其中参数k指Way Number。Evict指经过多少次存储器访问后才会将Cache Set中未知的数据完全清除，在一个指定的时间，Cache Set中包含的数据是无法确定的，但是经过Evict(k)次存储器访问可以将这些未知数据全部清除。而在经过Fill(k)次存储器访问后，可以确定在Cache Set中存在那些访问数据，Evict和Fill参数的关系如图2‑17所示。

Fill(k)和Evict(k)参数的计算需要分多种情况分别进行讨论。我们首先讨论参数Evict(k)。如果在一个Cache Set内的所有Way的状态都为Invalid，这种情况几乎不用讨论，那么连续K次存储器访问，一定可以将该Set内的所有Way Evict。如果所有Way的状态都是Valid，这种情况也较为容易，同样需要K次存储器访问Evict所有Way。

而如果在一个Cache Set内，有些Way为Invalid而有些不是，这种情况略微复杂一些。而且一次存储器访问可以在Cache中Hit也可能Miss，此时Evict和Fill参数的计算方法更为复杂一些。我们使用Evict_m和Fill_m表示存储器访问在Cache中Miss的情况，而使用Evict_hm和Fill_hm表示其他情况。

我们首先讨论每一次存储器访问都出现Cache Miss的情况，此时如果在Cache Set内具有Invalid的Cache Block，并不会使用PLRU标准替换流程，而直接使用状态为Invalid的Cache Block。此时将一个Set内所有Way Evict所需要的存储器访问次数如公式2‑1所示。

当k等于8时，Evict_m为12。这也是在PowerPC E500手册中，Evict大小为32KB的L1 Dcache需要操作48KB内存区域的原因。使用这一方法时需要注意两个实现细节，一个是Interrupts must be disabled，另一个是The 48-Kbyte region chosen is not being used by the system—that is, that snoops do not occur to this region.[43]。

如果进一步考虑在一个存储器访问序列中，在Cache Set中，不但具有Invalid的Cache Block，而且不是每一次存储器访问都会出现Miss操作而引发Replacement操作，因为可能某次访问了出现Cache Hit时，公式2‑1进一步演化为公式2‑2。

在这种情况下，对于8-Way Set Associative的Cache，将一个Set所有Way Evict所需要的存储器访问次数为13。在Cache Block替换算法中，MLS(Minimum Life-Span)参数也值得关注，该参数表示在一个Way在Cache Set中的最小生命周期。如果一次存储器操作命中了一个Way，这个Way至少需要MLS次Cache替换操作后，才能够从当前Set中替换出去。对于Tree-Based PLRU算法，MLS的计算如公式 2‑3所示。

由以上公式，可以发现对于一个8-Ways Set Associative的Cache，一个最近访问的Block，其生命周期至少为4，即一个刚刚Hit，或者因为Miss而Refill的Cache Block，至少需要4次Cache Block替换操作后才能被Evict。

MLS参数可以帮助分析Cache的Hit Rate，对于一个已知算法的Cache，总可以利用某些规则，极大提高Hit Rate，只是在进行这些优化时，需要注意更高层次的细节。与Cache Block替换算法相关的Fill_m和Fill_hm参数的计算如公式 2‑4所示。

除了PLRU算法之外，文章[37]对FIFO，MRU和LRU进行了详细的理论推导，这些证明过程并不复杂，也谈不上数学意义上的完美，但是通过这篇文章提出的Fill和Evict算法和相关参数，依然可以从Qualitative Research的角度上论证一个替换算法自身的Beautiful，特别是对于一个纯粹的Cache替换算法，在没有考虑多级Cache间的耦合，和较为复杂的多处理器间的Cache一致性等因素时的分析。

如何选用Cache Block的Replacement算法是一个Trade-Off过程，没有什么算法一定是最优的。在Niagara和MIPS微架构的实现中甚至使用了Rand算法，这个算法实现过程非常简单，最自然的想法是使用LFSR近似出一组随机序列，与Cache Set中设置替换状态相比，LFSR使用的资源较少，而且确定需要Replacement的Cache Block的过程非常快速。

 虽然很多评测结果都可以证明Random算法不如PLRU，但是这个算法使用了较小系统资源，而且系统开销较小。利用这些节省下来的资源，微架构可以做其他的优化。因而从更高层次的Trade-Off看，Random算法并不很差。

在体系结构领域很少有放之四海而皆准的真理。PLRU算法之后，也有许多针对其不足的改进和增强，这些想法可能依然是Trade Off。但是不要轻易否定这些结果，在没有较为准确的量化分析结果之前，不能去想当然。想当然与直觉并不等同。人类历史上，许多伟大的革新源自某个人的直觉。这些革新在出现的瞬间甚至会与当时的常识相悖。

在一个技术进入到稳定发展阶段，很难有质的提高。更多时候，在等待着变化，也许是使用习惯的改变，也许是新技术的横空出世。在许多情况下，CS和EE学科的发展进步并不完全依靠自身的螺旋上升发生的质变，更多的时候也许在耐心等待着其他各个领域的水涨船高。Cache替换算法如此，体系结构如此，人类更高层面的进步亦如此。

近期随着MLP的崭露头角，更多的人重新开始关注Cache Block的替换算法，出现了一系列MLP-Aware的替换算法，如LIN(Linear) Policy[44]，LIP(LRU Insertion Policy)，BIP(Bimodal Insertion Policy)和DIP(Dynamic Insertion Policy)[45]。

其中LIN算法根据将Cache Miss分为Multiple Cache Miss和Isolated Miss。其中Isolated Miss出现的主要场景是Pointer-Chasing Load操作，而Multiple Cache Miss发生在对一个Array的操作中。Multiple Cache Miss可以并行操作，Amortize所有开销，对性能的影响相对较小；而Isolated Miss是一个独立操作对性能影响较大，传统Cache Block的替换算法并没有过多考虑这些因素，从而影响了性能。LIN算法即是为了解决这些问题而引入[44]。

LIP，BIP和DIP针对Memory-Intensive的应用。在某些Memory-Intensive应用中，可能存在某段超出Cache容量的数据区域，而且会按照一定的周期循环使用。如果采用传统的LRU算法，最新访问的Cache Block将为MRU，在超过MLS个Cycle后才可能被替换，而将不应该替换的Cache Block淘汰，从而造成了某种程度的Cache Trashing。

采用LIP算法时，则将这样的Incoming Cache Block设置为LRU，以避免Cache Trashing，这种思想谈不上新颖，重要的是简洁快速的实现。BIP是LIP的改进。DIP是对BIP和传统的LRU算法进行加权处理，以实现Adaptive Insertion Policies[45]。

除了在Memory-Intensive的应用层面之外，相对在不断提高的DDR延时，也改变着Cache Block Replacement算法的设计。现代处理器的设计对不断提高的DDR延时在本质上束手无策，只有引入更多的Cache层次，采用容量更大的LLC，在满足访问延时的同时获得更高的Coverage与不断增长的DDR容量和访问延时匹配。与此对应，产生了一些用于多级Cache结构的Cache Block替换算法，如Bypass and Insertion Algorithms for Exclusive LLC[46]。

这些算法的出现与日益增加的主存储器容量与访问延时相关，也是当前Cache Block替换算法的研究热点。这为Cache Hierarchy的设计提出了新的挑战，使得原本已经非常难以构思，难以设计难以验证的Cache层次结构，愈加复杂。