数字IC前端学习笔记：近期最少使用(LRU)算法
相关文章
数字IC前端专栏https://blog.csdn.net/weixin_45791458/category_12173698.html?spm=1001.2014.3001.5482
目录
1.LRU简介
2.LRU的矩阵实现
3.采用矩阵法实现LRU的Verilog代码
1.LRU简介
LRU算法用于cache管理或任何其他需要对访问权进行周期更新的场合。基于时间和空间考虑，cache中存储着近期将会用到的数据项。当cache被用满后，如果有新的数据项到来，需要将某个现有的数据项从cache中清除，为新进入者提供空间。此时通常使用的算法被称为LRU(Least Recently Used，近期最少使用)，通过LRU算法可以找到最久未被使用过的数据项，cache将该数据项清除，并将新的数据项写入此处。
另一个会用到LRU算法的地方是网络设备中的路由表管理电路。路由表的地址空间非常大，而在网络设备中用于存储路由表的存储器相对小得多，因此只有一部分路由表表项可以存储在CAM(Content Addressable Memory)存储器中，那么需要采用LRU算法找到当前CAM中最久未用过的表项，将其清楚后把新的表项写入，新的表项成为最新表项。
2.LRU的矩阵实现
在RTL级实现LRU算法的方法有多种。一种采用硬件实现LRU的方法是矩阵法。例如，有一个表，可存储4个表项，当前表项为A,B,C和D。我们的目标是确定哪一个是最久没有被访问过的，具体步骤如下：
- 构建一个4×4的存储单元矩阵（每个存储单元是一个触发器）。
- 将所有触发器初始化为零。
- 无论何时，只要有一个表项被访问，则将其对应的一行全部置1，然后将其对应列全部置0。
- 只要某个表项被访问，重复上一步操作。
- 全零的一行对应的表项是近期最少使用者，是要被新的表项代替的对象。
假定访问顺序为A，D，C，A，B，在此情形下，D是最近使用最少的表项，它应该被替换掉。下面用4×4矩阵解释上述算法。
初始条件
| A | B | C | D | |
| A | 0 | 0 | 0 | 0 |
| B | 0 | 0 | 0 | 0 |
| C | 0 | 0 | 0 | 0 |
| D | 0 | 0 | 0 | 0 |
参考序列：A
| A | B | C | D | |
| A | 0 | 1 | 1 | 1 |
| B | 0 | 0 | 0 | 0 |
| C | 0 | 0 | 0 | 0 |
| D | 0 | 0 | 0 | 0 |
参考序列：A、D
| A | B | C | D | |
| A | 0 | 1 | 1 | 0 |
| B | 0 | 0 | 0 | 0 |
| C | 0 | 0 | 0 | 0 |
| D | 1 | 1 | 1 | 0 |
参考序列：A、D、C
| A | B | C | D | |
| A | 0 | 1 | 0 | 0 |
| B | 0 | 0 | 0 | 0 |
| C | 1 | 1 | 0 | 1 |
| D | 1 | 1 | 0 | 0 |
参考序列：A、D、C、A
| A | B | C | D | |
| A | 0 | 1 | 1 | 1 |
| B | 0 | 0 | 0 | 0 |
| C | 0 | 1 | 0 | 1 |
| D | 0 | 1 | 0 | 0 |
参考序列：A、D、C、A、B
| A | B | C | D | |
| A | 0 | 0 | 1 | 1 |
| B | 1 | 0 | 1 | 1 |
| C | 0 | 0 | 0 | 1 |
| D | 0 | 0 | 0 | 0 |
D行为全零，是近期最少使用者。B行的1最多，是近期最多使用者。
3.采用矩阵法实现LRU的Verilog代码
module matrix_lru #(parameter SIZE = 8) (clk, rstb, update_the_entry, update_index, lru_index); input clk; input rstb; input update_the_entry; input [2:0] update_index; output [2:0] lru_index; reg [(SIZE - 1):0] matrix [0:(SIZE - 1)]; reg [(SIZE - 1):0] matrix_nxt [0:(SIZE - 1)]; reg [2:0] lru_index; reg [2:0] lru_index_nxt; generate genvar i; for(i = 0; i < SIZE; i = i + 1) begin always@(posedge clk or negedge rstb) begin if(!rstb) matrix[i] <= 0; else matrix[i] <= matrix_nxt[i]; end end endgenerate 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_the_entry && (j == update_index) && (k != update_index)) matrix_nxt[j][k] = 1'b1; else if(update_the_entry && (k == update_index)) matrix_nxt[j][k] = 1'b0; end end end endgenerate always@(*) begin lru_index_nxt = lru_index; if(matrix[0] == 8'b0) lru_index_nxt = 0; else if(matrix[1] == 8'b0) lru_index_nxt = 1; else if(matrix[2] == 8'b0) lru_index_nxt = 2; else if(matrix[3] == 8'b0) lru_index_nxt = 3; else if(matrix[4] == 8'b0) lru_index_nxt = 4; else if(matrix[5] == 8'b0) lru_index_nxt = 5; else if(matrix[6] == 8'b0) lru_index_nxt = 6; else if(matrix[7] == 8'b0) lru_index_nxt = 7; end always@(*) begin if(!rstb) lru_index <= 0; else lru_index <= !lru_index_nxt; end endmodule仿真截图如下所示。
以上内容来源于《Verilog高级数字系统设计技术和实例分析》