Verilog手写四路组相联Cache：从地址切分到LRU与写回

1. 为什么四路组相联Cache值得用Verilog手写一遍做FPGA或者数字IC设计的同学迟早会碰到一个绕不开的题目Cache。不管是秋招面试被问到你了解Cache的映射方式吗还是实际项目里要给一个处理器核配一块指令缓存四路组相联4-Way Set Associative几乎是出现频率最高的结构。原因很直接——直接映射冲突率太高全相联的Tag比较和替换逻辑又太贵四路组相联在命中率和硬件开销之间找到了一个甜点。但真正动手用Verilog写一个能跑、能综合、时序收敛的四路组相联Cache和面试时画个框图完全是两回事。我见过太多人能把LRU算法讲得头头是道一写代码就卡在四个Way的valid位怎么并行更新写回时dirty位什么时候清Tag比较和Way选择怎么在一个周期内完成这些具体问题上。这篇内容就是把我自己从零实现一个四路组相联Cache的完整过程拆开来讲。核心关键词包括Verilog、四路组相联Cache、LRU、FPGA、写回。我会给出完整的模块划分、关键代码段、参数计算方法以及我在实际综合和仿真中踩过的坑。适合已经学过Verilog基础语法、想通过一个完整项目把时序逻辑和状态机练扎实的读者。代码风格偏向可综合、可移植不依赖特定厂商IP。先明确一下我们要做的东西的规格Cache总容量4KB块大小Block Size16字节四路组相联采用写回Write-Back加写分配Write-Allocate策略替换算法用LRU。地址位宽32位。这些参数后面会逐一解释为什么这么选。2. 四路组相联的地址切分与容量计算2.1 从地址到Tag、Index、Offset的完整推导Cache的本质是一个查找表给一个内存地址判断它对应的数据是否已经在Cache里。四路组相联的意思是Cache被分成若干个组Set每个组里有四个可以存放数据的位置Way。一个地址只能映射到唯一的一个组但可以放在这个组的任意一个Way里。地址切分是第一步也是最容易算错的一步。我们按顺序从低位往高位切Offset块内偏移块大小16字节需要log2(16) 4位。这4位不参与Tag比较直接用来在块内选字节。Index组索引用来选组。组数 Cache总容量 / (块大小 × 路数) 4096 / (16 × 4) 64组。所以Index需要log2(64) 6位。Tag标签剩下的高位。32 - 6 - 4 22位。所以地址格式是[31:10] Tag | [9:4] Index | [3:0] Offset。这里有个新手常犯的错误把Index和Offset的顺序搞反。记住一个原则——Offset永远是最低位因为它要在最小的粒度上寻址Index在中间Tag在最高位。你可以用一句话记忆越靠近数据的位越低。2.2 为什么是64组而不是其他数字有人会问为什么不做成128组、每路2KB组数变了Index位宽就变了Tag位宽也跟着变。组数越多Index位越多Tag位越少意味着不同地址更容易映射到不同组冲突概率降低但每个组能容纳的Way数量不变时总的Tag存储开销会变化。具体到我们的参数每组4个Way每个Way需要一个22位的Tag、一个valid位、一个dirty位再加上16字节的数据。单组存储开销 4 × (22 1 1) 4 × 16 × 8 4 × 24 512 96 512 608位。64组总共约38K位加上LRU状态位大概5KB左右的存储资源。这个规模在主流FPGA上是完全放得下的用Block RAM实现数据阵列用分布式RAM或寄存器实现Tag和状态位是比较常见的做法。如果组数翻倍到128组Index变成7位Tag变成21位单组存储略降但组数翻倍后总存储基本持平。选择64组主要是为了让Index位宽和Offset位宽加起来刚好10位地址切分比较整齐调试时看十六进制地址也方便。2.3 参数化设计的接口定义我习惯把参数写在模块头部方便后续改配置。核心参数如下parameter DATA_WIDTH 128; // 一个Block的数据位宽16字节 parameter TAG_WIDTH 22; parameter INDEX_WIDTH 6; parameter OFFSET_WIDTH 4; parameter WAY_NUM 4; parameter SET_NUM 64;注意这里DATA_WIDTH我直接定义成128位也就是一个Block一次性读进来而不是按字节存。这样做的好处是数据阵列的位宽整齐和Block RAM的位宽对齐综合时更容易推断出BRAM。代价是每次读写都是整块操作对于字节粒度的写需要额外的字节使能逻辑。在写回策略下我们本来就要整块换入换出所以这个代价可以接受。3. 四个Way的并行Tag比较与命中判断3.1 命中逻辑的流水线设计Cache最核心的组合逻辑就是命中判断。给定一个地址我们要同时比较四个Way的Tag并且检查valid位。只有Tag匹配且valid为1才算命中。wire [WAY_NUM-1:0] way_hit; genvar i; generate for (i 0; i WAY_NUM; i i 1) begin : hit_gen assign way_hit[i] valid_array[index][i] (tag_array[index][i] req_tag); end endgenerate assign cache_hit |way_hit;这段代码看起来简单但实际综合时要注意tag_array[index][i]是一个二维数组的索引访问如果tag_array用寄存器实现综合出来就是一大堆多路选择器延迟可能不小。我的做法是把Tag阵列用分布式RAM实现读出的四个Tag在一个周期内并行比较比较器用LUT实现整体延迟控制在2ns以内在100MHz时钟下没问题。命中信号cache_hit是一个组合信号它决定了后续是走读命中路径还是缺失处理路径。这里有个时序上的坑如果你把命中判断和Way选择放在同一个周期然后直接用选中的Way数据输出那么从地址输入到数据输出的组合路径会很长。我的建议是把Tag比较和Way选择做成一级流水地址打一拍下一拍出数据和命中信号。这样虽然多了一个周期延迟但时序容易收敛特别是在FPGA上跑高频时。3.2 Way选择与数据输出命中之后要从四个Way里选出命中的那个Way的数据。这里有两种写法一种是用优先级编码器另一种是用one-hot选择。因为四个way_hit中最多只有一个为1正常情况下所以可以直接用或门合并reg [DATA_WIDTH-1:0] hit_data; integer j; always (*) begin hit_data {DATA_WIDTH{1b0}}; for (j 0; j WAY_NUM; j j 1) begin if (way_hit[j]) hit_data data_array[index][j]; end end这种写法综合出来是一个四选一的多路器面积不大。但要注意如果way_hit出现多个1比如Tag阵列初始化异常这里会选出最后一个Way的数据属于未定义行为。所以在复位时一定要把所有valid位清零避免上电后出现多个Way同时命中的情况。3.3 一个容易忽略的细节Tag比较的位宽对齐Tag是22位但有些同学在写比较逻辑时会把地址的高位直接截断或者拼接错误。比如地址是32位Index是[9:4]那么Tag应该是[31:10]。如果你写成addr[31:10]没问题但如果写成addr[31:4]再和22位的Tag比较位宽不匹配Verilog会自动补零或截断导致永远不命中。我的习惯是在模块内部先定义好切分后的信号wire [TAG_WIDTH-1:0] req_tag addr[31:10]; wire [INDEX_WIDTH-1:0] req_index addr[9:4]; wire [OFFSET_WIDTH-1:0] req_offset addr[3:0];这样一目了然也方便后续改参数时统一调整。4. LRU替换算法的硬件实现4.1 LRU的本质用状态位记录访问顺序LRULeast Recently Used的思想是当需要替换时踢掉最久没有被访问的那个Way。在四路组相联里每个组需要记录四个Way的访问顺序。最直观的做法是给每个Way一个计数器但那样面积太大。工程上常用的是矩阵法或者树形法。我用的是矩阵法每个组维护一个4×4的矩阵矩阵元素m[i][j]表示Way i是否比Way j更近被访问过。当访问Way i时把第i行全部置1第i列全部置0。替换时找哪一行的所有元素都是0除了对角线那一行对应的Way就是最久未使用的。reg [WAY_NUM-1:0] lru_matrix [SET_NUM-1:0][WAY_NUM-1:0];这个矩阵在Verilog里可以用二维寄存器数组实现。每次访问时更新integer k; always (posedge clk) begin if (cache_access cache_hit) begin for (k 0; k WAY_NUM; k k 1) begin lru_matrix[req_index][hit_way][k] 1b1; lru_matrix[req_index][k][hit_way] 1b0; end end end替换时找最久未使用的Wayreg [WAY_NUM-1:0] lru_way_onehot; integer m, n; always (*) begin lru_way_onehot {WAY_NUM{1b0}}; for (m 0; m WAY_NUM; m m 1) begin if (~|lru_matrix[req_index][m]) lru_way_onehot[m] 1b1; end end这里~|lru_matrix[req_index][m]表示第m行的所有位都是0。正常情况下应该只有一行满足条件。如果有多个说明矩阵状态异常可以用优先级编码器兜底。4.2 LRU更新的时序陷阱矩阵法的更新逻辑有一个时序上的坑当命中发生时我们要更新矩阵但更新后的矩阵在同一个周期内不能立即用于替换判断因为替换判断是组合逻辑而矩阵更新是时序逻辑。所以正确的顺序是命中判断 → 更新LRU矩阵下一拍生效→ 如果缺失用当前矩阵状态选替换Way。这意味着LRU矩阵的更新和替换Way的选择之间有一拍延迟。对于连续缺失的情况这一拍延迟可能导致替换的不是真正最久未使用的Way但影响很小因为连续缺失本身就不常见。如果你追求精确可以在缺失处理状态机里多等一拍让矩阵更新完成后再选替换Way。4.3 树形法对比面积与精度的权衡矩阵法每个组需要16个状态位64组就是1024位。树形法也叫伪LRU每个组只需要3位对于4路64组只要192位面积小很多。但树形法只能近似LRU不能保证每次替换的都是最久未使用的。在FPGA上1024位的寄存器资源并不算多所以我优先选了矩阵法行为更精确调试时也更容易理解。如果你做的是面积敏感的设计比如给一个小型处理器核配Cache树形法更合适。两种方法的替换逻辑接口是一样的只是内部状态更新不同可以做成可配置的。5. 写回策略与脏位管理5.1 写回和写直达的选择依据写回Write-Back的意思是写操作只写到Cache不立即写回主存直到这个Cache块被替换出去时才写回。写直达Write-Through则是每次写都同时更新Cache和主存。写回的优势是减少主存写带宽特别适合写操作频繁且局部性好的场景。代价是需要维护dirty位替换时要判断是否写回。在FPGA项目里如果主存是片外DDR写回能显著降低DDR带宽压力所以我选了写回。写分配Write-Allocate的意思是写缺失时先把块从主存读进来再在Cache里修改。与之相对的是非写分配No-Write-Allocate写缺失时直接写主存不读块。写回策略通常搭配写分配因为如果写缺失时不把块读进来后续对这个块的写操作还是会缺失写回的优势就没了。5.2 dirty位的置位与清除时机dirty位在每个Way里占1位。置位时机是写命中时always (posedge clk) begin if (write_en cache_hit) begin dirty_array[req_index][hit_way] 1b1; end end清除时机是替换时如果被替换的Way是dirty的先把它的数据写回主存然后清除dirty位再填入新数据。这里的状态机要小心写回主存可能需要多个周期取决于主存接口在写回完成之前不能覆盖这个Way的数据。我的做法是在缺失处理状态机里加一个WRITE_BACK状态typedef enum logic [2:0] { IDLE, COMPARE_TAG, WRITE_BACK, ALLOCATE, UPDATE } state_t;当缺失且选中替换的Way是dirty时进入WRITE_BACK状态发出写请求等写完成信号后进入ALLOCATE状态从主存读新块最后进入UPDATE状态更新Tag和valid位。5.3 写回缓冲区的必要性如果主存接口比较慢写回操作会阻塞后续的Cache访问。一个常见的优化是加一个写回缓冲区Write-Back Buffer把要写回的数据先存起来Cache立即继续服务后台慢慢写回主存。这个缓冲区通常是一个FIFO深度4到8就够。在FPGA上实现这个FIFO很简单用Block RAM或者分布式RAM都行。但要注意如果写回缓冲区的数据还没写到主存而Cache又发生了对这个地址的读缺失就需要检查写回缓冲区里是否有更新的数据。这个检查逻辑会增加复杂度对于初学者项目可以先不做写回缓冲区等基本功能跑通后再加。6. 缺失处理状态机的完整设计6.1 状态划分与跳转条件缺失处理是Cache里最复杂的部分因为它涉及多个周期的操作判断是否写回、从主存读块、更新Tag和状态位。我用一个五状态的状态机来管理状态功能跳转条件IDLE等待访问请求有请求则跳到COMPARE_TAGCOMPARE_TAG判断命中/缺失命中回IDLE缺失跳WRITE_BACK或ALLOCATEWRITE_BACK写回dirty块写完成跳ALLOCATEALLOCATE从主存读新块读完成跳UPDATEUPDATE更新Tag、valid、dirty、LRU无条件回IDLE这个状态机的关键点是COMPARE_TAG状态里要同时判断命中、缺失、以及缺失时选中的替换Way是否dirty。如果dirty走WRITE_BACK如果不dirty直接走ALLOCATE。6.2 主存接口的握手协议主存接口我用的是简单的valid-ready握手。读请求发出时拉高mem_req_valid带上地址主存返回mem_req_ready表示接受。数据返回时主存拉高mem_data_validCache在mem_data_valid为高时采样数据。// 读请求 assign mem_req_valid (state ALLOCATE); assign mem_req_addr {req_tag, req_index, {OFFSET_WIDTH{1b0}}}; // 数据接收 always (posedge clk) begin if (state ALLOCATE mem_data_valid) begin data_array[req_index][replace_way] mem_data; state UPDATE; end end这里有个细节读请求的地址要把Offset清零因为我们要读整个块。如果主存支持突发传输Burst可以一次读16字节如果不支持就要读16次单字节状态机里还要加一个计数器。为了简化我假设主存支持块读一次返回128位数据。6.3 替换Way的选择与LRU矩阵的交互在COMPARE_TAG状态判断缺失后要用LRU矩阵选出替换Way。但前面提到LRU矩阵的更新有一拍延迟所以这里选出的替换Way可能不是最新的LRU结果。我的处理方式是在COMPARE_TAG状态用当前矩阵状态选替换Way同时把选中的Way记录下来在UPDATE状态更新矩阵时把这个Way标记为最近使用。always (posedge clk) begin if (state COMPARE_TAG !cache_hit) begin replace_way lru_way_onehot; end endreplace_way是一个one-hot信号在后续状态里用来索引具体的Way。用one-hot而不是二进制编码的好处是更新data_array和tag_array时可以直接用位选不需要额外的译码器。7. 仿真验证与常见Bug排查7.1 测试平台的搭建思路验证Cache最直接的方法是写一个行为级的主存模型然后用一系列读写操作去刺激Cache最后检查读出的数据是否和预期一致。我的测试平台包含三个部分激励生成器、主存模型、以及一个参考模型Reference Model。参考模型就是一个简单的数组模拟理想的内存行为。每次Cache读参考模型也读同样的地址每次Cache写参考模型也写同样的地址。最后比较Cache读出的数据和参考模型的数据是否一致。// 参考模型 reg [7:0] ref_mem [0:65535]; // 比较逻辑 always (posedge clk) begin if (cache_read_valid ref_read_valid) begin if (cache_read_data ! ref_read_data) begin $display(Mismatch at time %0t: addr%h, cache%h, ref%h, $time, read_addr, cache_read_data, ref_read_data); end end end7.2 我踩过的三个典型BugBug 1valid位复位不彻底。第一次仿真时Cache读出的数据全是X。排查后发现valid_array在复位时没有全部清零导致上电后valid位是随机的命中判断出现多个Way同时命中。修复方法是在复位时用for循环把所有组的valid位清零。Bug 2LRU矩阵更新时索引越界。在更新LRU矩阵时我用了hit_way作为索引但hit_way是one-hot信号直接当索引用会出错。正确的做法是先把one-hot转成二进制索引或者直接用for循环遍历四个Way判断哪一位是1。Bug 3写回时地址拼接错误。写回主存时地址应该是{tag, index, 4b0}但我一开始写成了{tag, index}导致写回地址少了4位数据写到了错误的位置。这个Bug很隐蔽因为仿真时主存模型不会报错只是数据对不上。后来在写回路径上加了断言检查地址位宽才定位到问题。7.3 覆盖率驱动的验证基本的读写测试跑通后要有针对性地构造一些边界场景连续缺失连续访问四个映射到同一组的不同Tag地址触发四次替换检查LRU是否按预期工作。写回触发先写一个地址使其dirty然后访问同组的其他地址触发替换检查是否发生了写回。读写交替在同一地址上交替读写检查dirty位和数据的正确性。复位后立即访问检查复位后Cache是否处于干净状态。这些场景用随机测试很难覆盖到最好手写定向测试。我的做法是写一个任务task来封装单次访问然后在initial块里按顺序调用。8. FPGA综合与时序收敛的实操经验8.1 存储资源的映射策略在FPGA上data_array有64组×4路×128位 32768位正好是4KB。这个规模用Block RAM实现最合适。Xilinx的BRAM一个36Kb的块可以存32Kb数据所以理论上一个BRAM就够。但BRAM是双口的而我们的Cache需要同时读四个Way的Tag数据阵列也需要支持并行读写。我的做法是data_array用四个独立的BRAM实现每个Way一个BRAM这样四个Way可以并行访问。Tag阵列和valid/dirty阵列用分布式RAM或寄存器实现因为它们位宽小但需要并行比较。在Vivado里要确保综合器能正确推断出BRAM代码风格很重要。data_array的读写要遵循同步读写的模式always (posedge clk) begin if (wr_en) data_array[index][way] wr_data; rd_data data_array[index][way]; end注意读数据要打一拍这是BRAM的固有延迟。如果你希望读数据在同一个周期返回综合器会推断出分布式RAM面积会大很多。8.2 关键路径分析与优化综合后看时序报告最长的路径通常是地址输入 → Tag比较 → Way选择 → 数据输出。这条路径穿过了Tag阵列的读、比较器、多路选择器延迟可能超过5ns。优化的方法有两个一是把Tag比较和Way选择做成流水线地址打一拍后再比较二是把Tag阵列的读也打一拍用BRAM的同步读特性。这样地址输入后两个周期才能出数据但时钟频率可以跑到200MHz以上。我最终的设计在100MHz下时序余量很大在150MHz下也能收敛。对于大多数FPGA项目100MHz已经够用了。8.3 复位策略的选择Cache的复位策略有两种同步复位和异步复位。我推荐同步复位因为FPGA的BRAM不支持异步复位如果data_array用BRAM实现异步复位会导致综合器推断不出BRAM。同步复位的写法always (posedge clk) begin if (rst_n 1b0) begin // 复位逻辑 end else begin // 正常逻辑 end end注意rst_n是低电平有效的同步复位信号。在FPGA里同步复位会增加复位路径的延迟但可以通过全局复位网络来缓解。9. 从四路组相联延伸出去的可扩展方向把基本功能跑通之后这个Cache还有很多可以打磨的地方。比如把块大小从16字节改成32字节Offset变成5位Index变成5位Tag变成22位整体结构不变只是参数调整。或者把路数从4改成8LRU矩阵变成8×8面积增加但命中率更高。另一个实用的扩展是加预取Prefetch。在缺失处理时除了读当前块还可以顺便读下一个块利用空间局部性。预取逻辑可以很简单在UPDATE状态额外发一个读请求地址是当前块地址加块大小。预取的数据放在一个单独的缓冲区里下次缺失时先检查预取缓冲区。如果要做多核系统Cache的一致性Coherence就是下一个要啃的硬骨头。不过那是另一个话题了先把单核的Cache写扎实后面扩展起来才有底气。我在实际项目里最大的体会是Cache的代码量不大但细节极多每一个状态位、每一个握手信号都可能成为Bug的来源。最好的办法是先把状态机画清楚把每个状态的输入输出列成表格然后再写代码。仿真时不要怕麻烦定向测试用例写得越细后期调试越省事。