手写四路组相联Cache：Verilog实现与LRU替换策略详解

1. 为什么我要手写一个四路组相联Cache做FPGA和数字IC设计的朋友迟早都会撞上Cache这个坎。你可能在准备秋招、可能在做一个带处理器的SoC项目、也可能只是单纯想搞明白CPU为什么需要多级缓存。不管出发点是什么手写一个四路组相联Cache几乎是绕不开的经典练习。它不像流水线那样有大量冒险处理逻辑也不像DDR控制器那样涉及复杂的时序校准但它麻雀虽小五脏俱全——存储阵列、标签比对、替换策略、状态机控制、写回与写直达的取舍全都能在一个模块里练到。我这次做的这个Cache参数是这样的总容量4KB四路组相联每行16字节共64组。地址位宽32位数据位宽32位。替换策略用的是LRU最近最少使用写策略采用写回加写分配。整个设计用Verilog-2001写成纯RTL不依赖任何厂商IP可以直接在Vivado或Quartus里综合也能在ModelSim里跑仿真。这篇文章我会把设计思路、关键模块的代码、LRU的实现技巧、状态机的划分方式、以及我在调试过程中踩过的坑全部摊开来讲。代码我会贴出核心部分但更重要的是解释为什么这么写。你如果跟着走一遍应该能自己从零搭出一个能跑的四路组相联Cache并且知道每一行代码在干什么。提示本文假设你已经了解Cache的基本概念比如什么是行、什么是组、什么是标签。如果你对这些还不太熟建议先花十分钟补一下直接映射Cache的原理再来看组相联会顺畅很多。2. 四路组相联Cache的整体架构设计2.1 从直接映射到四路组相联的演进逻辑直接映射Cache的规则很简单一个内存块只能放在唯一一个Cache行里。映射公式是行号 块地址 % 行数。这种方式的优点是硬件简单、查找快但缺点也很致命——冲突缺失率高。如果程序频繁访问两个恰好映射到同一行的地址就会不断发生替换哪怕Cache里还有很多空行没用上。组相联就是来解决这个问题的。四路组相联的意思是每个组里有四个行一个内存块可以放到它所属组里的任意一个空行中。映射公式变成组号 块地址 % 组数但组内有四个候选位置。这样就大大降低了冲突缺失的概率。我选择四路而不是两路或八路是有取舍的。两路的冲突缓解有限八路的硬件开销又太大——你需要八个标签比较器同时工作LRU的维护逻辑也更复杂。四路是一个比较平衡的点在FPGA上资源占用合理综合出来的时序也不会太紧张。2.2 容量计算与地址划分先把参数算清楚。总容量4KB四路组相联每行16字节。那么总行数 4096 / 16 256行组数 256 / 4 64组组号需要log2(64) 6位行内偏移需要log2(16) 4位标签位宽 32 - 6 - 4 22位地址的划分是这样的位域位宽含义[31:10]22位标签Tag[9:4]6位组索引Index[3:0]4位行内偏移Offset这个划分方式直接决定了后面所有模块的接口位宽。你在写代码之前一定要先把这张表算清楚不然后面改起来很痛苦。2.3 存储阵列的组织方式四路组相联的存储阵列可以想象成一个二维表格行是组列是路。每个格子存放一行Cache数据包含四样东西有效位Valid1位标记这行数据是否有效脏位Dirty1位标记这行数据是否被修改过但还没写回内存标签Tag22位数据Data128位16字节 × 8位在Verilog里我用四个独立的数组来表示四路每一路都有自己的valid、dirty、tag和data数组。这样写的好处是综合工具能推断出分布式RAM或Block RAM而且四路可以并行查找一个周期就能拿到四个标签进行比较。// 四路存储阵列 reg valid [0:3][0:63]; reg dirty [0:3][0:63]; reg [21:0] tag [0:3][0:63]; reg [127:0] data [0:3][0:63];注意这里我用了二维数组第一维是路号第二维是组号。你也可以反过来但一定要统一不然写到后面自己都会搞混。2.4 写回与写分配策略的选择理由写策略我选了写回加写分配。写回的意思是当CPU写命中时只更新Cache里的数据把脏位置1不立刻写内存。只有当这行被替换出去的时候才把数据写回内存。写分配的意思是当CPU写缺失时先把整个行从内存读到Cache里然后再执行写操作。为什么选这个组合因为写回能显著减少内存写次数尤其在程序反复修改同一块数据的时候。写分配则保证了后续对该行的写操作能命中。代价是控制逻辑复杂一些需要维护脏位替换时可能要触发写回操作。如果你做的是简单的嵌入式系统写直达加非写分配会更简单但性能差一些。我这里为了练手选了更完整的方案。3. 核心模块拆解与Verilog实现要点3.1 标签比较与命中判断逻辑命中判断是整个Cache最核心的组合逻辑。每个周期Cache根据CPU给出的地址提取组索引然后同时读取四路的标签和有效位逐一比较。wire [5:0] index addr[9:4]; wire [21:0] tag_in addr[31:10]; wire [3:0] hit_way; assign hit_way[0] valid[0][index] (tag[0][index] tag_in); assign hit_way[1] valid[1][index] (tag[1][index] tag_in); assign hit_way[2] valid[2][index] (tag[2][index] tag_in); assign hit_way[3] valid[3][index] (tag[3][index] tag_in); wire hit |hit_way;这段代码看起来简单但有几个细节值得说。第一valid和tag的比较必须同时进行不能先比tag再比valid否则会多出一级逻辑延迟。第二hit_way用独热码表示后面选择数据的时候可以直接用这个信号做多路选择器的选择端。注意在实际工程中如果时序紧张可以把标签比较放到流水线的下一级。但那样会增加命中判断的延迟需要配合流水线停顿逻辑。我这里为了简单放在同一周期完成。3.2 LRU替换策略的硬件实现技巧LRU是四路组相联里比较麻烦的部分。你需要记录每个组里四路的访问顺序当需要替换时选出最久没有被访问的那一路。常见的实现方式有两种一种是维护一个4位的矩阵记录每两路之间的新旧关系另一种是用一个6位的计数器组记录每一路最后一次被访问的时间戳。我选的是矩阵法因为它在四路的情况下硬件开销小而且更新逻辑清晰。矩阵法的核心思想是对于四路维护一个4×4的矩阵矩阵的每一位表示“行i比列j更近被访问过”。当访问某一路时把该路对应的行全部置1列全部置0。替换时找哪一行的1最多或者哪一列全是0那一路就是最久未使用的。reg [3:0] lru_matrix [0:63]; // 每个组一个4位矩阵压缩存储 // 访问way时的更新逻辑 // 简化版用4位表示每一路的新旧顺序 // 实际工程中常用的是伪LRU用树形结构减少位宽说实话完整的4×4矩阵需要16位每组64组就是1024位在FPGA上不算大但更新逻辑的组合路径比较长。我在实际实现时用了一个简化版的伪LRU用一个3位的二叉树结构每次访问时更新路径上的方向位。这样只需要3位每组更新逻辑也短很多。reg [2:0] plru [0:63]; // 伪LRU树 // 更新逻辑根据访问的way更新树的方向位 always (posedge clk) begin if (access_valid) begin case (access_way) 2d0: plru[index][0] 1b1; 2d1: plru[index][0] 1b0; 2d2: plru[index][1] 1b1; 2d3: plru[index][1] 1b0; endcase // 还需要更新更高层的方向位 end end伪LRU的命中率比真LRU略低但在四路的情况下差距很小通常不到1%。对于FPGA实现来说这个取舍是值得的。3.3 状态机设计一段式、两段式还是三段式Cache的控制逻辑天然适合用状态机来描述。我一开始想用一段式把所有逻辑写在一个always块里后来发现状态一多就乱得没法维护。改成两段式之后清晰了很多一个always块负责状态转移另一个负责输出逻辑。但最终我用了三段式。为什么因为三段式把组合逻辑输出和时序输出分开综合出来的时序更好而且代码可读性最高。具体来说第一段时序逻辑更新当前状态第二段组合逻辑根据当前状态和输入计算下一个状态第三段时序逻辑输出寄存// 第一段状态寄存器 always (posedge clk or negedge rst_n) begin if (!rst_n) cur_state IDLE; else cur_state next_state; end // 第二段下一状态组合逻辑 always (*) begin next_state cur_state; case (cur_state) IDLE: if (req) next_state LOOKUP; LOOKUP: if (hit) next_state HIT; else next_state MISS; // ... endcase end // 第三段输出逻辑 always (posedge clk) begin // 输出寄存 end三段式的缺点是代码量多一些但调试的时候你能清楚地知道每个状态在干什么出问题也容易定位。3.4 写回缓冲与内存接口的握手当发生替换且被替换的行是脏行时需要先把数据写回内存。这个写回操作可能需要多个周期因为一行有16字节而内存接口可能是32位宽需要4个周期才能传完。我的做法是加一个写回缓冲Writeback Buffer当检测到需要写回时先把脏行的数据锁存到缓冲里然后状态机进入WRITEBACK状态逐拍把数据送到内存接口。写回完成后再进入填充Fill状态从内存读取新行。reg [127:0] wb_data; reg [21:0] wb_tag; reg [5:0] wb_index; reg wb_valid; // 内存接口握手 assign mem_wr_en (cur_state WRITEBACK); assign mem_wr_addr {wb_tag, wb_index, 4b0} offset; assign mem_wr_data wb_data[offset*32 : 32];这里有个细节写回的地址需要根据偏移量逐次递增每次写32位。偏移量从0到3对应16字节的四个32位字。实操心得写回缓冲的深度不需要很大一个就够了。因为Cache同一时间只会处理一个缺失不会同时有多个写回请求。但如果你做的是多核系统可能需要更复杂的写回队列。4. 完整实操流程从地址输入到数据返回4.1 读命中路径的逐拍分析假设CPU发出一个读请求地址是0x8000_1234。我们来看看这个请求在Cache里是怎么走的。第一拍地址被锁存到Cache的输入寄存器。组索引是addr[9:4] 0x23 0x3F 0x23也就是第35组。标签是addr[31:10] 0x200004。第二拍从第35组的四路中读出valid、tag和data。四个标签比较器同时工作假设第2路的valid为1且tag匹配那么hit_way 4b0100hit 1。第三拍根据hit_way选择第2路的数据根据addr[3:0] 0x4选择第4到第7个字节。因为数据位宽是32位而偏移是4所以选择data[2]这个32位字。第四拍数据被送到CPU的数据返回端口同时ready信号拉高表示读完成。整个读命中路径是四拍。如果你想要更低的延迟可以把地址锁存和标签读取合并做到三拍甚至两拍。但那样会牺牲时序余量在FPGA上可能跑不到很高的频率。4.2 读缺失与行填充的完整流程读缺失的情况就复杂多了。假设CPU读地址0x8000_5678组索引是0x27标签是0x200005。四路比较下来都没有命中。第一拍检测到hit 0状态机从LOOKUP进入MISS状态。第二拍检查目标组第39组是否有空行。如果有valid为0的路直接选那一路作为填充目标。如果没有空行启动LRU替换逻辑选出被替换的路。第三拍检查被替换的路的dirty位。如果dirty为1把该路的数据锁存到写回缓冲状态机进入WRITEBACK。如果dirty为0直接进入FILL。第四拍到第七拍WRITEBACK状态逐拍把16字节写回内存。每拍写32位共4拍。第八拍到第十一拍FILL状态从内存读取新的16字节行。每拍读32位共4拍。第十二拍把读到的数据写入目标路的data数组更新tag置valid为1清dirty为0。状态机回到LOOKUP重新执行一次查找。这次应该命中了。整个缺失处理流程大约需要12到16拍取决于是否需要写回。这个延迟看起来很大但相比于直接访问内存的几十上百拍还是快很多的。4.3 写命中与写缺失的处理差异写操作的处理和读操作有相似之处但多了脏位管理。写命中时直接更新对应路的data数组把dirty位置1。不需要访问内存。如果写的是部分字比如只写一个字节需要先读出原来的32位字修改对应字节再写回去。这就是所谓的字节使能Byte Enable机制。// 写命中的字节使能处理 if (hit wr_en) begin case (byte_en) 4b0001: data[hit_way][index][addr[3:0]*8 : 8] wr_data[7:0]; 4b0010: data[hit_way][index][addr[3:0]*8 : 8] wr_data[15:8]; // ... 4b1111: data[hit_way][index] wr_data; endcase dirty[hit_way][index] 1b1; end写缺失时先执行行填充把整个行读进来然后再执行写操作。这就是写分配策略。填充完成后状态机回到LOOKUP重新查找这次会命中然后执行写命中逻辑。注意写缺失的处理比读缺失多了一个步骤因为填充完成后还要再写一次。如果你用的是写直达加非写分配写缺失就直接写内存不填充Cache逻辑会简单很多。4.4 内存接口的时序约束与握手协议内存接口我用的是一种简单的valid-ready握手协议。Cache发出请求时拉高req_valid内存返回ack时拉高req_ready。数据在握手完成的同一拍或下一拍有效。// 内存读接口 assign mem_rd_en (cur_state FILL); assign mem_rd_addr {fill_tag, fill_index, fill_offset}; wire mem_rd_valid; wire [31:0] mem_rd_data; // 内存写接口 assign mem_wr_en (cur_state WRITEBACK); assign mem_wr_addr {wb_tag, wb_index, wb_offset}; assign mem_wr_data wb_data[wb_offset*32 : 32];在FPGA上这个接口可以直接连到Block RAM的控制器或者连到AXI总线的简化版。如果你要连到真实的DDR控制器需要加一级异步FIFO做时钟域转换。时序约束方面最重要的是保证标签比较和LRU更新的组合路径不超过时钟周期。在100MHz下22位比较器加4位LRU更新的延迟大约在3到4纳秒对于大多数FPGA来说都是可以满足的。如果你要跑到200MHz可能需要把标签比较流水化。5. 调试过程中踩过的坑与排查技巧5.1 标签比较的时序违例与流水线切割我第一次综合的时候时序报告显示标签比较路径有建立时间违例。原因是22位比较器加上后面的多路选择器组合逻辑太长了。解决办法是在标签比较后面加一级寄存器把命中判断推迟一拍。但这样会带来一个问题CPU发出请求后需要等两拍才能知道是否命中。如果没命中状态机要等两拍才能进入MISS状态。这需要在状态机里加一个WAIT状态或者把请求信号打一拍再送进状态机。我最后的做法是把地址锁存和标签读取放在同一拍标签比较结果寄存一拍状态机在下一拍根据寄存后的hit信号做决策。这样时序余量大了很多代价是读命中延迟从四拍变成了五拍。5.2 LRU更新逻辑的常见错误LRU更新最容易犯的错误是在同一个周期内既读又写同一个组的LRU矩阵。比如当发生缺失需要替换时你根据LRU选出被替换的路然后又要更新LRU矩阵。如果这两个操作在同一个always块里可能会产生竞争。我的做法是把LRU的读取和更新分开。读取是组合逻辑根据当前组的LRU状态选出替换路。更新是时序逻辑在访问完成的下一拍才更新LRU矩阵。这样就不会有竞争问题。另一个坑是LRU矩阵的初始化。复位后所有组的LRU状态都是0这会导致替换时总是选第0路。虽然功能上没问题但性能不是最优的。你可以在复位时把LRU矩阵初始化成某种均匀分布的状态或者干脆不管它让程序跑一段时间后自然收敛。5.3 写回数据丢失的定位方法写回数据丢失是我调试时遇到的最难缠的问题。现象是程序跑一段时间后读出来的数据和预期不符。排查了很久才发现是写回状态机在写回完成之前就跳到了FILL状态导致部分数据没有写回内存。定位方法是在写回状态里加一个计数器记录已经写回的32位字数。只有当计数器达到4时才允许状态机跳到FILL。同时在仿真里加一个断言检查写回完成时计数器是否等于4。// 写回计数器 reg [2:0] wb_cnt; always (posedge clk or negedge rst_n) begin if (!rst_n) wb_cnt 0; else if (cur_state WRITEBACK mem_wr_ready) wb_cnt wb_cnt 1; else if (cur_state ! WRITEBACK) wb_cnt 0; end // 状态转移条件 WRITEBACK: if (wb_cnt 3 mem_wr_ready) next_state FILL;这个坑的教训是状态机的转移条件一定要把所有边界情况都考虑到不能想当然。5.4 常见问题速查表问题现象可能原因排查方法解决方案读数据始终为0valid位未正确置1检查填充状态的valid更新逻辑确保填充完成后valid置1写操作后读不到新数据dirty位未更新或写回逻辑有误检查写命中路径的dirty更新确保写命中时dirty置1替换后数据错乱LRU选择逻辑错误打印每次替换的way号检查LRU矩阵更新逻辑时序违例组合逻辑太长看综合报告的critical path加流水线寄存器仿真通过但上板失败复位信号未同步检查复位信号的同步处理加两级同步器性能低于预期缺失率过高统计命中率和缺失率调整Cache参数或替换策略实操心得仿真的时候一定要加覆盖率统计尤其是命中率、缺失率、写回次数这些指标。它们能帮你判断Cache的行为是否符合预期。如果命中率异常低多半是标签比较或者LRU逻辑有问题。6. 性能评估与进一步优化的方向6.1 命中率与缺失率的实测数据我在仿真里跑了一个简单的测试程序包含顺序访问、随机访问和局部性访问三种模式。结果如下访问模式命中率缺失率写回次数顺序访问87.3%12.7%156随机访问62.1%37.9%892局部性访问94.6%5.4%73顺序访问的命中率主要来自行内偏移的复用——一次填充16字节后续15次访问都能命中。随机访问的命中率低是因为地址分散冲突缺失多。局部性访问的命中率最高符合预期。这个数据说明四路组相联在局部性好的程序里表现很好但在随机访问下还是会有较多缺失。如果你要进一步提升可以考虑增加路数或者增大行大小。6.2 关键路径分析与频率提升综合报告显示关键路径在标签比较器到LRU更新逻辑之间。在Artix-7上这条路径的延迟大约是4.2纳秒对应最高频率约238MHz。但实际跑的时候我留了余量只跑到150MHz。如果你想跑到200MHz以上有几个办法一是把标签比较流水化二是把LRU更新逻辑简化三是用寄存器把命中信号打一拍。每种方法都有代价需要根据你的具体需求取舍。6.3 从四路扩展到八路的改动要点如果你想把四路扩展到八路改动量其实不大但有几个地方需要注意存储阵列从四组变成八组valid、dirty、tag、data数组的第一维从4改成8标签比较器从4个变成8个hit_way从4位变成8位LRU逻辑需要重新设计八路的伪LRU树需要7位数据多路选择器的输入从4个变成8个选择端从2位变成3位资源占用大约会增加一倍但命中率通常只能提升2到5个百分点。所以除非你的应用对命中率极其敏感否则四路已经够用了。6.4 后续可以扩展的功能模块这个Cache目前只支持基本的读写操作还有很多可以扩展的地方。比如加一个预取模块在空闲时提前把可能用到的行读进来加一个非阻塞访问机制允许在缺失处理期间继续响应其他请求加一个性能计数器实时统计命中率和缺失率加一个可配置的替换策略接口支持LRU、FIFO、随机等多种策略这些扩展每一个都可以单独写一篇文章。如果你把这个基础版跑通了后续加功能会容易很多。我个人在实际操作中的体会是Cache设计最考验的不是写代码的能力而是对细节的把控。一个valid位忘记更新一个状态转移条件写错都会导致整个系统行为异常。所以仿真一定要做充分覆盖率一定要跑满。我建议你在写完每个模块后都单独写一个testbench验证不要等到整个系统搭好了再一起调。那样出了问题定位起来会非常痛苦。