3
十二 · 6月28日

一文了解tree-based Pseudo LRU

SpinalHDL

✎ 编 者 按 

前文了解了LRU，对于LRU矩阵实现，由于矩阵的存在导致其所需要的资源会随着entry的增加而膨胀，今天来看下PLRU(tree-based Pseudo LRU)

tree based pseudo LRU

前文提到过，实现一个LRU所需要的标识资源为平方数(实现一个四路组相连则需要16bit的空间用于存储矩阵信息，8路就需要64bit信息了)。对于一个具有n个entry空间，tree-based Pseudo LRU使用n-1位来表示近似访问历史顺序的二叉树。这里仍以四entry为例：

image.png

PLRU采用一个完全二叉树，叶子节点用于表示Entry空间，对于其非叶子节点，我们定义如下：

  • 1=>表示当前节点下左子树是最近访问的路径
  • 0=>表示当前节点下右子树是最近访问的路径

通过从根节点进行遍历，就可以遍历寻找到最久没有被使用的元素。

在初始化后，所有的非叶子节点均赋值为0。按照上面的规则，上图中最久没有被使用的节点就是Entry0。

那么就来看下基于PLRU策略下的更新过程：

image.png

当某个节点被使用时，则将更新从根节点到该叶子节点之间的节点按照上面的方式进行更新。在寻找最久没有被使用的节点时，则从根节点开始，根据节点的值进行寻找，直到找到对应的叶子节点。  

PLRU称为Pseudo，那么我们来对比下和LRU相同的更新策略对应的值：

image.png

而采用LRU方式：

image.png

相比之下，自然LRU是最准确的，能够找到真正的最久没有被使用的节点。 

SpinalHDL的实现优势

对于一个具有n个entry的PLRU实现，先看看如何实现寻找最久没有被使用的节点。如果只是从看图肉眼识别，那自然很简单，然而如果要实现参数化设计，那么就要费点儿功夫了。

由于PLRU采用的是完全二叉树的形式实现。对于一个entry，如果其为最久未被使用，那么我们只需要寻找到从根节点到该叶子节点所需要的所有节点即可。我们对节点进行编号：

image.png

对于n个entry，设定entry编号从0～n-1，对于任何一个entry ID，通过下面的代码可以寻找到从根节点到该entry的节点编号：

/**
   * 根据节点编号返回其从根节点到该节点的编号
   *
   * @param entryId
   * @return
   */
  def getParentNodeList(entryId: Int): Array[Int] = {
    var nodeId = entryId + entryNum - 1
    var currentNodeDpeth = treeDepth
    val nodeList = Array[Int]().toBuffer
    while (currentNodeDpeth > 0) {
      nodeList.append(getParentNode(currentNodeDpeth, nodeId))
      nodeId = nodeList.last
      currentNodeDpeth -= 1
    }
    nodeList.toArray
  }

  def getParentNode(currentNodeDepth: Int, NodeId: Int): Int = {
    val parentTreeStartNode = (1 << (currentNodeDepth - 1)) - 1
    val currentTreeStartNode = (1 << currentNodeDepth) - 1
    return (NodeId - currentTreeStartNode) / 2 + parentTreeStartNode
  }

找到了节点编号，那接着就需要确定每个节点是在其父节点的左子树还是右子树上并决定该节点值应当是0还是1了：

def generateCaseMask(entryId: Int): MaskedLiteral = {
    val parentNodeList = getParentNodeList(entryId)
    val defaultValue = Array.fill(entryNum - 1)("-")
    val childNodeList = Array(entryId + (entryNum - 1)) ++ parentNodeList.take(parentNodeList.length - 1)
    val treeDepthId = (for (index <- 0 until treeDepth) yield index).reverse.toList
    (childNodeList, parentNodeList, treeDepthId).zipped.foreach((child, parent, parentDepth: Int) => {
      //计算父节点的左节点
      val childStartId = (1 << (parentDepth + 1)) - 1
      val parentStartId = (1 << (parentDepth)) - 1
      val leftChildId = childStartId + (parent - parentStartId) * 2
      if (leftChildId == child) { //为左节点，填0
        defaultValue(parent) = "0"
      } else {
        defaultValue(parent) = "1"
      }
    })
    return MaskedLiteral(defaultValue.reduce(_ + _).reverse)
  }

如此，通过casez来实现寻找最久没有被使用的节点：

switch(io.plru_state) {
    for (entryId <- 0 until (entryNum - 1)) {
      is(generateCaseMask(entryId))(io.plru_entry := entryId)
    }
    default(io.plru_entry := entryNum - 1)
  }

这里就是SpinalHDL的优势了，对于case，Verilog中似乎没有什么特别好的描述方式。

当一个节点被使用需要更新状态时，则需要更新从根节点到该entry的所有节点了。这里我们可以将使用的节点id转换为独热码：

val plru_update_entry_oh = UIntToOh(io.plru_update_req.plru_update_entry) //转换成独热码h(io.plru_update_req.plru_update_entry) //转换成独热码

对于任何一个节点更新，其所有的父节点进行更新。对于每一层中的任何一个节点，需要找到其左子树对应的entryID和右子树ID，通过按位或的方式来判断是更新为0还是1:

for (depthIndex <- 0 until treeDepth) {
    val currentDepthNodeNum = 1 << depthIndex
    val startNodeId = (1 << depthIndex) - 1
    val leafNum = entryNum / currentDepthNodeNum //当前层每个节点具备的叶子节点个数
    for (nodeIdOffset <- 0 until currentDepthNodeNum) {
      val nodeId = nodeIdOffset + startNodeId
      val startLeafLeftId = 0 + leafNum * nodeIdOffset
      val startLeafRightId = startLeafLeftId + leafNum / 2
      val leafNumHalf = leafNum / 2
      when(plru_update_entry_oh(startLeafLeftId, leafNumHalf bits).orR) { //左子树更新
        io.plru_update_result(nodeId).set()
      } elsewhen (plru_update_entry_oh(startLeafRightId, leafNumHalf bits).orR) { //右子树更新
        io.plru_update_result(nodeId).clear()
      } otherwise {
        io.plru_update_result(nodeId) := io.plru_update_req.plru_state(nodeId)
      }
    }
  }

对于n过大时，二叉树的上层节点所需要消耗的资源可能过多，对于上层节点，也可以考虑直接进行entryId是否在制定范围内比较判断来实现。         

附上完整设计代码与仿真代码：

package LRU

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

case class PLRUUpdateRequest(entryNum: Int) extends Bundle {
  val plru_state = Bits((entryNum - 1) bits) //LRU State entryNum row,entryNum col
  val plru_update_entry = UInt(log2Up(entryNum) bits)
}

case class PlruControl(entryNum: Int) extends Component {
  val treeDepth = log2Up(entryNum)
  val io = new Bundle {
    val plru_state = in Bits ((entryNum - 1) bits) //PLRU状态,完全二叉树,root节点位于比特0
    val plru_entry = out UInt (log2Up(entryNum) bits) //最近最少被使用

    val plru_update_req = in(PLRUUpdateRequest(entryNum))
    val plru_update_result = out(Bits(entryNum - 1 bits))
  }
  noIoPrefix()

  /** *****************************************************************************************
   * PLRU Entry检测。完全二叉树
   * 1=>左侧比右侧更新使用
   * 0=>右侧比左侧更新使用
   * ***************************************************************************************** */

  /**
   * 根据节点编号返回其从根节点到该节点的编号
   *
   * @param entryId
   * @return
   */
  def getParentNodeList(entryId: Int): Array[Int] = {
    var nodeId = entryId + entryNum - 1
    var currentNodeDpeth = treeDepth
    val nodeList = Array[Int]().toBuffer
    while (currentNodeDpeth > 0) {
      nodeList.append(getParentNode(currentNodeDpeth, nodeId))
      nodeId = nodeList.last
      currentNodeDpeth -= 1
    }
    nodeList.toArray
  }

  def getParentNode(currentNodeDepth: Int, NodeId: Int): Int = {
    val parentTreeStartNode = (1 << (currentNodeDepth - 1)) - 1
    val currentTreeStartNode = (1 << currentNodeDepth) - 1
    return (NodeId - currentTreeStartNode) / 2 + parentTreeStartNode
  }

  def generateCaseMask(entryId: Int): MaskedLiteral = {
    val parentNodeList = getParentNodeList(entryId)
    val defaultValue = Array.fill(entryNum - 1)("-")
    val childNodeList = Array(entryId + (entryNum - 1)) ++ parentNodeList.take(parentNodeList.length - 1)
    val treeDepthId = (for (index <- 0 until treeDepth) yield index).reverse.toList
    (childNodeList, parentNodeList, treeDepthId).zipped.foreach((child, parent, parentDepth: Int) => {
      //计算父节点的左节点
      val childStartId = (1 << (parentDepth + 1)) - 1
      val parentStartId = (1 << (parentDepth)) - 1
      val leftChildId = childStartId + (parent - parentStartId) * 2
      if (leftChildId == child) { //为左节点，填0
        defaultValue(parent) = "0"
      } else {
        defaultValue(parent) = "1"
      }
    })
    return MaskedLiteral(defaultValue.reduce(_ + _).reverse)
  }

  switch(io.plru_state) {
    for (entryId <- 0 until (entryNum - 1)) {
      is(generateCaseMask(entryId))(io.plru_entry := entryId)
    }
    default(io.plru_entry := entryNum - 1)
  }
  /** *****************************************************************************************
   * PLRU状态更新
   * ***************************************************************************************** */

  val plru_update_entry_oh = UIntToOh(io.plru_update_req.plru_update_entry) //转换成独热码
  for (depthIndex <- 0 until treeDepth) {
    val currentDepthNodeNum = 1 << depthIndex
    val startNodeId = (1 << depthIndex) - 1
    val leafNum = entryNum / currentDepthNodeNum //当前层每个节点具备的叶子节点个数
    for (nodeIdOffset <- 0 until currentDepthNodeNum) {
      val nodeId = nodeIdOffset + startNodeId
      val startLeafLeftId = 0 + leafNum * nodeIdOffset
      val startLeafRightId = startLeafLeftId + leafNum / 2
      val leafNumHalf = leafNum / 2
      when(plru_update_entry_oh(startLeafLeftId, leafNumHalf bits).orR) { //左子树更新
        io.plru_update_result(nodeId).set()
      } elsewhen (plru_update_entry_oh(startLeafRightId, leafNumHalf bits).orR) { //右子树更新
        io.plru_update_result(nodeId).clear()
      } otherwise {
        io.plru_update_result(nodeId) := io.plru_update_req.plru_state(nodeId)
      }
    }
  }
}

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

object PlruControlApp extends App {
  SpinalConfig(nameWhenByFile = false).generateSystemVerilog(PlruControl(32))
  SimConfig.withFstWave.compile(PlruControl(4)).doSim { dut => {
    var lruState = BigInt(0)


    def showLruState() = {
      val lru_state_boolean = BigIntToListBoolean(lruState, dut.entryNum - 1 bits)
      for (depth <- 0 until dut.treeDepth) {
        val startId = (1 << depth) - 1
        val entryNum = 1 << depth
        println(s"${lru_state_boolean.slice(startId, startId + entryNum).map(_.toInt)}")
      }
    }

    def updateRequest(entry: Int) = {
      println(s"Update Entry:${entry}")
      dut.io.plru_update_req.plru_update_entry #= entry
      dut.io.plru_update_req.plru_state #= lruState
      sleep(1)
      lruState = dut.io.plru_update_result.toBigInt
      //show Tree
      showLruState()

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

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

  }
  }
}

END

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

推荐阅读

更多SpinalHDL技术干货请关注[Spinal FPGA]欢迎添加极术小姐姐微信（id:aijishu20)加入技术交流群，请备注研究方向。
3 阅读 1.2k
推荐阅读
SpinalHDL—Area SpinalHDL—Function SpinalHDL—仿真环境 SpinalHDL资料汇总 SpinalHDL——switch 从Verilog到SpinalHDL
Spinal FPGA
关注数
1581
内容数
133
用SpinalHDL提升生产力
关注专栏 专栏主页
目录
极术微信服务号
关注极术微信号
实时接收点赞提醒和评论通知
安谋科技学堂公众号
关注安谋科技学堂
实时获取安谋科技及 Arm 教学资源
安谋科技招聘公众号
关注安谋科技招聘
实时获取安谋科技中国职位信息