Bin*_*eee 4 cpu-architecture tlb cpu-cache
我有一本书的声明：
在全关联 TLB 中实现 LRU 非常昂贵，所以一般的方法是使用随机替换。
我不明白为什么在完整的关联缓存下它很昂贵。这不就是增加了一个额外的参考位......？
LRU 需要在缓存集中的所有有效缓存行之间维护一个全序关系。例如，考虑一个 3 路高速缓存集，其中 A、B 和 C 行按照从最近访问到最近最少访问的顺序（表示为 ABC）进行排序。如果接下来访问 C，则顺序变为 CAB。如果需要在同一个缓存集中填充新行 D，由于没有无效行，LRU 替换策略将选择 B 被驱逐并由新行替换。然后订单变成DCA。
对于 3 路高速缓存，每组中的行最多有 3*2 = 6 个可能的顺序。一般来说，对于一个 N-way 缓存，最多有 N！（N阶乘）可能的顺序。理论上，每个缓存集至少需要 log2(N!) 位（四舍五入到最接近的整数）才能准确地维护 LRU 属性。请注意，log2(N!) 是 ?(Nlog(N))，因此它相对于方式的数量呈超线性增长。没有一个正常人喜欢任何成本超线性增长的东西。
一种特别便宜的情况是 2 路缓存，其中 LRU 状态仅需要 log2(2!) = 1 位，即单个位。但是，对于任何其他数量的方式来说，它的成本要高得多。
然而，在实践中，没有简单的方法来维护表示集合的 LRU 状态的单个数字。如果当前 LRU 状态是 X，然后发生了对某条线路的某些访问，那么如何确定下一个 LRU 状态？没有可以在硬件中实现的简单数学关系。因此，不是使用单个数字，而是实际实现将使用多个数字，每个缓存行一个。在这种情况下，这些数字称为年龄。这种设计甚至需要比理论上的最小 log2(N!) 多（许多）位来维持 LRU 状态。
除了硬件开销之外，LRU 替换策略不一定是性能最佳的。这取决于目标市场领域和缓存层次结构的其余部分中应用程序的内存访问模式。
LRU 已经在许多实际处理器中使用。2 路关联的缓存通常使用 LRU。例如，AMD SledgeHammer 将 LRU 用于 L1I 和 L1D 缓存。Itanium 2 处理器的 L1 指令缓存使用 LRU 并且它是 4 路关联的。通常，当路数大于 2 时，缓存不使用 LRU。