一文看懂LRU(Least Recently Used)实现

✎ 编者按
凑巧看到一个有关LRU(Least Recently Used)的逻辑实现，其采用矩阵方式进行实现，看起来颇有意思，但文章中只写方法不说原理，遂来研究下。

LRU

LRU（Least Recently Used）算法是一种常用的缓存淘汰策略，其核心思想是：如果一个数据在最近一段时间内没有被访问到，那么在未来它被访问的可能性也很小。因此，当缓存满了的时候，最久未使用的数据会被淘汰。

LRU在Cache替换策略里还是有较大的用途的。对于一个N路组相连，当对应的entry满了之后，当有新的访问请求到来后需从N个entry中挑选出一个替换entry。通过LRU可以挑选出最久没有被使用的元素。

LRU矩阵实现原理

对于一个具有N个Entry空间，LRU实现可以采用矩阵方式实现。这里以四个Entry空间为例：

对于矩阵中的元素Valuei,j，定义如下：

1: 为1时表示元素i在j访问之后被访问过。
0:为0时表示元素i在j被访问之后没有被访问过。

搞清楚了这两个元素定义，那么我们自然可以定义规则。当entry i被访问时，执行如下操作：

将第i行所有元素全部设置为1.
将第i列所有元素全部设置为0.

这里有一个点就是Value[i,i]将会被设置为0，也没有毛病，毕竟元素i在元素i被访问之后没有被访问过也是对的。

那么基于此，很明显一定存在某一行存在所有元素全为0的情况，从而也表示了其是Least Recently Used。

下图给出了基于矩阵的LRU检测过程：

Demo

基于上面的原理，下面的代码基于SpinalHDL写了一个简单的Demo，包含仿真代码：

package LRU

import spinal.core._
import spinal.lib._

case class LRUUpdateRequest(entryNum: Int) extends Bundle {
  val lru_state = Bits(entryNum * entryNum bits) //LRU State entryNum row,entryNum col
  val lru_update_entry = UInt(log2Up(entryNum) bits)
}

case class LruControl(entryNum: Int) extends Component {
  val io = new Bundle {
    val lru_state = in Bits (entryNum * entryNum bits) //LRU状态
    val lru_entry = out UInt (log2Up(entryNum) bits) //最近最少被使用

    val lru_update_req = in(LRUUpdateRequest(entryNum))
    val lru_update_result = out(Bits(entryNum * entryNum bits))
  }
  noIoPrefix()
  /** *****************************************************************************************
   * 计算最近最少被使用者
   * 寻找矩阵中为0的行，只需找到一个即可，找最低位
   * 实现机制:每一行做按位或，随后取反，转换为寻找最低位为1的位置
   * ***************************************************************************************** */
  val lru_row_state = io.lru_state.subdivideIn(entryNum bits).map(~_.orR).asBits()
  val lru_row_state_oh = OHMasking.first(lru_row_state) //先转换成独热码
  io.lru_entry := OHToUInt(lru_row_state_oh) //再转换成二进制
  /** *****************************************************************************************
   * lru更新
   * 更新规则，当更新entry i时，矩阵中第i行全部填1，矩阵中第i列全部填0
   * ***************************************************************************************** */
  val lru_update_entry_oh = UIntToOh(io.lru_update_req.lru_update_entry) //转换成独热码
  for {
    rowIndex <- 0 until entryNum;
    colIndex <- 0 until entryNum
  } {
    io.lru_update_result(rowIndex * entryNum + colIndex) := Mux(
      sel = lru_update_entry_oh(colIndex),
      whenTrue = False,
      whenFalse = Mux(
        sel = lru_update_entry_oh(rowIndex),
        whenTrue = True,
        whenFalse = io.lru_update_req.lru_state(rowIndex * entryNum + colIndex))
    )
  }
}

import spinal.core.sim._
import spinal.lib.tools.BigIntToListBoolean

object LruControlApp extends App {
  SimConfig.withFstWave.compile(LruControl(4)).doSim(dut => {
    var lruState = BigInt(0)

    def showLruState() = {
      val lru_state_boolean = BigIntToListBoolean(lruState, 16 bits)
      for (rowIndex <- 0 until 4) {
        println(s"${lru_state_boolean.slice(rowIndex * 4, rowIndex * 4 + 4).map(_.toInt)}")
      }
    }

    def updateRequest(entry: Int) = {
      println(s"Update Entry:${entry}")
      dut.io.lru_update_req.lru_update_entry #= entry
      dut.io.lru_update_req.lru_state #= lruState
      sleep(1)
      lruState = dut.io.lru_update_result.toBigInt
      //show 矩阵
      showLruState()

      dut.io.lru_state #= lruState
      sleep(1)
      val lruEntry = dut.io.lru_entry.toInt
      println(s"The Lru Entry is $lruEntry")
      sleep(1)
    }

    showLruState()
    dut.io.lru_state #= lruState
    sleep(1)
    val lruEntry = dut.io.lru_entry.toInt
    println(s"The Lru Entry is $lruEntry")
    sleep(1)
    for (entry <- Array(0, 1, 2, 3, 2, 3, 0, 1, 2, 0, 3)) {
      updateRequest(entry)
    }
  })
}

对于LRU矩阵实现，由于矩阵的存在导致其所需要的资源会随着entry的增加而膨胀。实现一个四路组相连则需要16bit的空间用于存储矩阵信息，8路就需要64bit信息了。

☆ END ☆

作者：玉骐
原文链接：Spinal FPGA
微信公众号：

推荐阅读

更多SpinalHDL技术干货请关注[Spinal FPGA]欢迎添加极术小姐姐微信（id:aijishu20)加入技术交流群，请备注研究方向。

LRU

LRU矩阵实现原理

Demo

推荐阅读

目录