湊巧看到一個有關LRU(Least Recently Used)的邏輯實現，其采用矩陣方式進行實現，看起來頗有意思，但文章中只寫方法不說原理，遂來研究下。

LRU

LRU（Least Recently Used）算法是一種常用的緩存淘汰策略，其核心思想是：如果一個數據在最近一段時間內沒有被訪問到，那么在未來它被訪問的可能性也很小。因此，當緩存滿了的時候，最久未使用的數據會被淘汰。

LRU在Cache替換策略里還是有較大的用途的。對于一個N路組相連，當對應的entry滿了之后，當有新的訪問請求到來后需從N個entry中挑選出一個替換entry。通過LRU可以挑選出最久沒有被使用的元素。

LRU矩陣實現原理

對于一個具有N個Entry空間，LRU實現可以采用矩陣方式實現。這里以四個Entry空間為例：

對于矩陣中的元素Value[i,j](第i行第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，包含仿真代碼：

packageLRU

importspinal.core._
importspinal.lib._

caseclass 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)
}

caseclass LruControl(entryNum: Int)extends Component {
val io = newBundle {
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, 16bits)
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信息了。