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