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

LRU

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

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

LRU矩陣實(shí)現(xiàn)原理

對(duì)于一個(gè)具有N個(gè)Entry空間，LRU實(shí)現(xiàn)可以采用矩陣方式實(shí)現(xiàn)。這里以四個(gè)Entry空間為例：

對(duì)于矩陣中的元素Value[i,j](第i行第j個(gè)元素)，定義如下：

1: 為1時(shí)表示元素i在j訪問之后被訪問過。

0:為0時(shí)表示元素i在j被訪問之后沒有被訪問過。

搞清楚了這兩個(gè)元素定義，那么我們自然可以定義規(guī)則。當(dāng)entry i被訪問時(shí)，執(zhí)行如下操作：

將第i行所有元素全部設(shè)置為1.

將第i列所有元素全部設(shè)置為0.

這里有一個(gè)點(diǎn)就是Value[i,i]將會(huì)被設(shè)置為0，也沒有毛病，畢竟元素i在元素i被訪問之后沒有被訪問過也是對(duì)的。

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

下圖給出了基于矩陣的LRU檢測過程：

Demo

基于上面的原理，下面的代碼基于SpinalHDL寫了一個(gè)簡單的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狀態(tài)
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()
/** *****************************************************************************************
* 計(jì)算最近最少被使用者
* 尋找矩陣中為0的行，只需找到一個(gè)即可，找最低位
* 實(shí)現(xiàn)機(jī)制:每一行做按位或，隨后取反，轉(zhuǎn)換為尋找最低位為1的位置
* ***************************************************************************************** */
val lru_row_state = io.lru_state.subdivideIn(entryNum bits).map(~_.orR).asBits()
val lru_row_state_oh = OHMasking.first(lru_row_state) //先轉(zhuǎn)換成獨(dú)熱碼
io.lru_entry := OHToUInt(lru_row_state_oh) //再轉(zhuǎn)換成二進(jìn)制
/** *****************************************************************************************
* lru更新
* 更新規(guī)則，當(dāng)更新entry i時(shí)，矩陣中第i行全部填1，矩陣中第i列全部填0
* ***************************************************************************************** */
val lru_update_entry_oh = UIntToOh(io.lru_update_req.lru_update_entry) //轉(zhuǎn)換成獨(dú)熱碼
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)
????}
??})
}

對(duì)于LRU矩陣實(shí)現(xiàn)，由于矩陣的存在導(dǎo)致其所需要的資源會(huì)隨著entry的增加而膨脹。實(shí)現(xiàn)一個(gè)四路組相連則需要16bit的空間用于存儲(chǔ)矩陣信息，8路就需要64bit信息了。