1、LRU（Least Recently Used）简介
LRU算法用于cache管理或任何其他需要对访问权进行周期更新的场合。
- 基于时间和空间考虑，cache中存储着近期将会用到的数据项。当cache被用满后，如果有新的数据项到来，需要将某个现有的数据项从cache中清除，为新进入者提供空间。此时通常使用的算法被称为LRU(Least Recently Used,近期最少使用)，通过LRU算法可以找到最久未被使用过的数据项，cache将该数据项清除，并将新的数据项写入此处。
- 另一个会用到LRU算法的地方是网络设备中的路由表管理电路。路由表的地址空间非常大，而在网络设备中用于存储路由表的存储器相对小得多，因此只有一部分路由表表项可以存储在CAM(Content Addressable Memory)存储器中。当CAM被用满后，如果有新的路由表表项到来，那么需要采用LRU算法找到当前CAM中最久未用过的表项，将其清除后把新的表项写人，新的表项成为最新表项。
2、LRU的矩阵实现
在RTL级实现LRU算法的方法有多种。一种采用硬件实现LRU的方法是矩阵法。文章来源：https://www.toymoban.com/news/detail-720614.html
- 例如，有一个表，可存储4个表项，当前表项为A、B、C和D。我们的目标是确定哪一个是最久没有被访问过的，具体步骤如下：
- 构建一个4×4的存储单元矩阵（每个存储单元是一个触发器）。
- 将所有触发器初始化为零。
- 无论何时，只要有一个表项被访问，其对应的一行全部置为1，其对应列全部置为0。
- 只要某个表项被访问，重复上一步操作。
- 全零的一行对应的表项是近期最少使用者，是要被新的表项替代的对象。
假定访问顺序为A、D、C、A、B,在此情形下，D是最近使用最少的表项，它应该被替换掉。下面用4×4矩阵解释上述算法。
可见，D行全为零，是近期最少使用者。B行的1最多，是近期最多使用者。文章来源地址https://www.toymoban.com/news/detail-720614.html
3、RTL design
/*----------------------------------------------------------
Filename : LRU
Author : deilt
Description : Least Recently Used, matrix 矩阵法
Called by :
Revision History : 11/1/2022
Revison 1.0
Email : cjdeilt@qq.com
Company:Deilt Technology.INC
Copyright(c) 1999, Deilt Technology Inc, All right reserved
--------------------------------------------------------------*/
module LRU
#(
parameter SIZE = 8
)
(
input clk ,
input rstn ,
input update_entry ,
input [2:0] update_index ,
output[2:0] lru_index
);
reg [SIZE-1:0] matrix[SIZE-1:0] ;
reg [SIZE-1:0] matrix_nxt[SIZE-1:0] ;
reg [2:0] lru_index ;
reg [2:0] lru_index_nxt ;
//resetn all unit of matrix to zero
generate
genvar i;
for(i=0;i<SIZE;i=i+1)
begin
always@(posedge clk or negedge rstn)begin
if(!rstn)
matrix[i] <= 'd0 ;
else
matrix[i] <= matrix_nxt[i] ;
end
end
endgenerate
//when update_index put in as i, then matrix[i] = 8'b1, matrix[i][i] = 1'b0
generate
genvar j,k;
for(j=0;j<SIZE;j=j+1)begin
for(k=0;k<SIZE;k=k+1)
begin
always@(*)begin
matrix_nxt[j][k] = matrix[j][k] ;
if(update_entry && j == update_index && k != update_index)
matrix_nxt[j][k] = 1'b1 ;
else if(update_entry && j == update_index && k == update_index)
matrix_nxt[j][k] = 1'b0 ;
end
end
end
endgenerate
//output the lru_index
always @(*) begin
lru_index_nxt = lru_index ;
if(matrix[0]=='d0)
lru_index_nxt = 0 ;
else if(matrix[1] == 'd0)
lru_index_nxt = 1 ;
else if(matrix[2] == 'd0)
lru_index_nxt = 2 ;
else if(matrix[3] == 'd0)
lru_index_nxt = 3 ;
else if(matrix[4] == 'd0)
lru_index_nxt = 4 ;
else if(matrix[5] == 'd0)
lru_index_nxt = 5 ;
else if(matrix[6] == 'd0)
lru_index_nxt = 6 ;
else if(matrix[7] == 'd0)
lru_index_nxt = 7 ;
end
always @(posedge clk or negedge rstn)begin
if(!rstn)
lru_index <= 'd0;
else
lru_index <= lru_index_nxt;
end
endmodule
到了这里，关于verilog实例-近期最少使用算法（LRU）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
