十二 · 6月11日

一文看懂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空间为例:

image.png

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

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

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

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

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

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

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

image.png

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
微信公众号:
 title=

推荐阅读

更多SpinalHDL技术干货请关注[Spinal FPGA]欢迎添加极术小姐姐微信(id:aijishu20)加入技术交流群,请备注研究方向。
推荐阅读
关注数
1580
内容数
132
用SpinalHDL提升生产力
目录
极术微信服务号
关注极术微信号
实时接收点赞提醒和评论通知
安谋科技学堂公众号
关注安谋科技学堂
实时获取安谋科技及 Arm 教学资源
安谋科技招聘公众号
关注安谋科技招聘
实时获取安谋科技中国职位信息