LRU缓存算法

Question

我需要一个 LRU 算法用于 4 路关联缓存，每组有额外的 5 位来指示应该逐出哪一行。

       -------------------------------------
Set x: | line_0 | line_1 | line_2 | line_3 |
       -------------------------------------

      -----------------------------------------
      | bit_4 | bit_3 | bit_2 | bit_1 | bit_0 |
      -----------------------------------------

起初，我试图将我的问题分成更小的问题。 只有两条线，我会触发与当前使用的线相对应的位，同时将另一条线设置为 0。

受害者将是位设置为 0 的行（前提是设置已满）。

我想我可以在一个 4 路高速缓存中使用它，其位 bit_4、bit_3、bit_1、bit_0 对应于 line_0， line_1、line_2、line_3 和中间位表示最近使用了哪一侧。很快我意识到它不够精确。 IE。在序列 line_0、line_2、line_3、line_1 之后，这些位将是：10101，这表明最近引用了左侧（这是真的）但是这并不一定意味着最近没有提到该面。

如有任何提示，我将不胜感激。

Answer 1

为了始终如一地找到最近最少使用的项目，您需要跟踪最近使用 4 个缓存行的顺序。

有4个！可能的顺序。 4！是 24 种可能性，额外的 5 位有 32 种可能的配置，所以你有足够的位（耶！）。但是，您没有很多额外的位，因此您不能真正期望订单的编码非常容易使用。

在我的脑海中，我想我会这样做：

• 最近最少使用项目的 2 位：0-3。如果需要，这就是驱逐的对象。
• 第二个最近最少使用的项目的 2 位：0-3
• 1 位用于第 3 个最近最少使用的项目。只有两种可能，因为另外两种已经被使用了。 0 表示剩余缓存行中编号较小的。
• 最近使用的 0 位（最近最少使用的第 4 位）。只剩下一个，所以你不需要存储任何东西就知道它是哪一个。