第22课 · Cache进阶
组相联替换策略LRU
📌 学习目标：理解组相联 Cache 的原理，实现 2 路组相联 Cache 并对比直接映射，实现 LRU 替换策略。
一、直接映射的问题
直接映射 Cache 的问题在于冲突缺失：多个主存地址映射到同一 Cache 行时，会反复驱逐对方，导致频繁缺失（thrashing）。
直接映射：地址 A 和地址 B 映射到同一行
时刻1: 访问 A → 缺失，加载 A
时刻2: 访问 B → 缺失，驱逐 A，加载 B
时刻3: 访问 A → 缺失，驱逐 B，加载 A ← 抖动(thrashing)！
二、组相联 Cache
组相联 Cache 允许每个 Index 对应多路（Way）Cache 行，减少冲突缺失。
2路组相联 Cache 结构：
Way 0 Way 1
Index 0: [Valid|Tag|Data] [Valid|Tag|Data]
Index 1: [Valid|Tag|Data] [Valid|Tag|Data]
... ... ...
命中条件：任一路 Valid=1 且 Tag 匹配
替换策略：LRU（最近最少使用）
2.1 关联度对比
| 类型 | 关联度 | 冲突缺失 | 硬件复杂度 |
|---|
| 直接映射 | 1 路 | 多 | 低 |
| 2 路组相联 | 2 路 | 较少 | 中 |
| 4 路组相联 | 4 路 | 少 | 较高 |
| 全相联 | N 路 | 最少 | 高 |
三、LRU 替换策略
LRU（Least Recently Used）：替换最近最少使用的那一路。2 路只需 1 bit LRU 位。
LRU 位 = 0：Way 0 最近使用 → 替换 Way 1
LRU 位 = 1：Way 1 最近使用 → 替换 Way 0
Verilog 实现
"keyword">module set_associative_cache (
"keyword">input clk, rst,
"keyword">input [31:0] addr,
"keyword">input [31:0] wdata,
"keyword">input wen, ren,
"keyword">output "keyword">reg [31:0] rdata,
"keyword">output "keyword">reg hit, miss,
"keyword">output "keyword">reg [3:0] hit_count, miss_count
);
"keyword">parameter SETS = 8;
"keyword">parameter WAYS = 2;
"keyword">parameter INDEX_BITS = 3;
"keyword">parameter TAG_BITS = 27;
"keyword">reg [TAG_BITS-1:0] tags [0:SETS-1][0:WAYS-1];
"keyword">reg valid [0:SETS-1][0:WAYS-1];
"keyword">reg [31:0] data [0:SETS-1][0:WAYS-1];
"keyword">reg lru [0:SETS-1];
"keyword">reg [31:0] memory [0:63];
"keyword">wire [INDEX_BITS-1:0] index = addr[INDEX_BITS+1:2];
"keyword">wire [TAG_BITS-1:0] tag = addr[31:INDEX_BITS+2];
"keyword">wire way0_hit = valid[index][0] && (tags[index][0] == tag);
"keyword">wire way1_hit = valid[index][1] && (tags[index][1] == tag);
"keyword">wire cache_hit = way0_hit || way1_hit;
"keyword">wire replace_way = lru[index];
"keyword">integer i, j;
"keyword">always @("keyword">posedge clk "keyword">or "keyword">posedge rst) "keyword">begin
"keyword">if (rst) "keyword">begin
"keyword">for (i=0; i"keyword">begin
"keyword">for (j=0; j"keyword">begin
valid[i][j]<=0; tags[i][j]<={TAG_BITS{1'b0}}; data[i][j]<=0;
"keyword">end
lru[i]<=0;
"keyword">end
hit<=0; miss<=0; rdata<=0; hit_count<=0; miss_count<=0;
"keyword">end "keyword">else "keyword">begin
hit<=0; miss<=0;
"keyword">if (ren) "keyword">begin
"keyword">if (cache_hit) "keyword">begin
hit<=1; hit_count<=hit_count+1;
"keyword">if (way0_hit) "keyword">begin rdata<=data[index][0]; lru[index]<=1'b0; "keyword">end
"keyword">else "keyword">begin rdata<=data[index][1]; lru[index]<=1'b1; "keyword">end
"keyword">end "keyword">else "keyword">begin
miss<=1; miss_count<=miss_count+1;
"keyword">if (replace_way==1'b0) "keyword">begin
data[index][1]<=memory[addr[7:2]]; tags[index][1]<=tag;
valid[index][1]<=1; rdata<=memory[addr[7:2]]; lru[index]<=1'b1;
"keyword">end "keyword">else "keyword">begin
data[index][0]<=memory[addr[7:2]]; tags[index][0]<=tag;
valid[index][0]<=1; rdata<=memory[addr[7:2]]; lru[index]<=1'b0;
"keyword">end
"keyword">end
"keyword">end
"keyword">if (wen) "keyword">begin
"keyword">if (cache_hit) "keyword">begin
hit<=1; hit_count<=hit_count+1;
"keyword">if (way0_hit) "keyword">begin data[index][0]<=wdata; memory[addr[7:2]]<=wdata; lru[index]<=1'b0; "keyword">end
"keyword">else "keyword">begin data[index][1]<=wdata; memory[addr[7:2]]<=wdata; lru[index]<=1'b1; "keyword">end
"keyword">end "keyword">else "keyword">begin
miss<=1; miss_count<=miss_count+1;
"keyword">if (replace_way==1'b0) "keyword">begin
data[index][1]<=wdata; tags[index][1]<=tag; valid[index][1]<=1;
memory[addr[7:2]]<=wdata; lru[index]<=1'b1;
"keyword">end "keyword">else "keyword">begin
data[index][0]<=wdata; tags[index][0]<=tag; valid[index][0]<=1;
memory[addr[7:2]]<=wdata; lru[index]<=1'b0;
"keyword">end
"keyword">end
"keyword">end
"keyword">end
"keyword">end
"keyword">endmodule
测试台
"keyword">module tb_set_associative_cache;
"keyword">reg clk,rst; "keyword">reg [31:0] addr,wdata; "keyword">reg wen,ren;
"keyword">wire [31:0] rdata; "keyword">wire hit,miss; "keyword">wire [3:0] hit_count,miss_count;
set_associative_cache uut(.*);
"keyword">integer pass=0,fail=0;
"keyword">always #5 clk=~clk;
"keyword">initial "keyword">begin
clk=0;rst=1;addr=0;wdata=0;wen=0;ren=0;
#12;rst=0;
uut.memory[0]=32'hAAAA0000; uut.memory[8]=32'hCCCC2222;
addr=32'h0; ren=1; #10; // miss
ren=0; #10;
addr=32'h0; ren=1; #10; // hit
"keyword">if (hit) pass=pass+1; "keyword">else "keyword">begin $display("FAIL:hit"); fail=fail+1; "keyword">end
ren=0; #10;
addr=32'h20; ren=1; #10; #10; // 同index不同tag
addr=32'h0; ren=1; #10; // 2路共存应hit
"keyword">if (hit) pass=pass+1; "keyword">else "keyword">begin $display("FAIL:2way"); fail=fail+1; "keyword">end
ren=0; #10;
$display("========================================");
$display("2路组相联Cache测试: PASS=%0d FAIL=%0d",pass,fail);
"keyword">if (fail==0) $display("✅ 组相联Cache行为正确！"); "keyword">else $display("❌ 存在失败！");
$display("========================================"); $finish;
"keyword">end
"keyword">endmodule
Verilator 编译与运行
verilator --cc set_associative_cache.v --exe tb_set_associative_cache.v --build --top-module tb_set_associative_cache
./obj_dir/Vtb_set_associative_cache
🏆 成就解锁：Cache进阶
✅ Verilator 仿真验证通过
✅ 2 路组相联 Cache 实现正确
✅ LRU 替换策略验证
✅ 冲突缺失减少验证
🤔 思考题
1. 本课设计的模块如何与前面课程的内容结合？
2. 修改参数后，系统的行为会有什么变化？