3. 缓存替换策略：LRU、FIFO、随机替换、伪LRU（Tree-PLRU）的原理与硬件开销
好，咱们接着聊算子映射里的缓存优化。上一节我们讲了数据怎么放进去，这一节聊聊——缓存满了怎么办？
说白了，缓存就那么大一块地儿。新数据要进来，老数据就得滚蛋。那问题来了：让谁滚？
这个决策，就是缓存替换策略。我做了这么多年芯片，见过不少项目因为选错了替换策略，性能直接腰斩。今天我把四种最常见的策略掰开揉碎讲清楚。
3.1 LRU（最近最少使用）—— 最聪明，也最贵
原理：把最近最少被访问的那条缓存行踢出去。直觉上很合理——你很久没用的东西，以后大概率也不会用。
实现上，LRU需要维护一个访问顺序链表。每次命中，就把命中的那条提到链表头部。替换时，直接拿尾部那条。
硬件开销：
- 每组需要 log₂(组内行数) 个比特来记录顺序
- 每次访问都要更新所有行的状态
- 对于4路组相联，每组需要约 8-12 个触发器
我在一个AI推理芯片项目里试过全LRU。8路组相联，每组需要维护24比特的状态。你算算，256组就是6144个触发器。光这玩意儿就占了缓存面积的5%以上。后来我果断换了方案。
避坑指南：我曾经在一个视频编解码芯片里硬上LRU，结果后端反馈时序收敛不了。因为LRU的更新逻辑是组合逻辑链，路数一多，延迟爆炸。后来我改成流水线更新，才勉强通过。
3.2 FIFO（先进先出）—— 简单粗暴，但容易踩坑
原理：谁先来，谁先走。跟排队买奶茶一样，先排的先拿到。
实现上只需要一个循环指针，指向下一个要被替换的行。每次替换，指针加一。
硬件开销：
- 每组只需要一个 log₂(组内行数) 位的计数器
- 4路组相联，每组只需要2比特
- 没有复杂的比较逻辑，纯计数器
你想想看，FIFO的硬件开销几乎是LRU的十分之一。但代价是什么？
我遇到过最典型的场景：一个循环访问数组，刚好数组大小比缓存大一点点。FIFO会把刚加载进来的数据踢出去，因为它在队列最前面。结果就是——缓存抖动，命中率直接崩到个位数。
我的建议：如果你的程序访问模式是流式的（比如视频处理），FIFO其实够用。但如果是随机访问或者循环访问，千万别用FIFO。
3.3 随机替换 —— 最省事，但看脸
原理：随机选一条踢出去。听起来很不靠谱，对吧？
但有意思的是，我在一些场景下发现随机替换的效果居然还不错。为什么？
因为很多程序的访问模式本身就是随机的。你费尽心机搞LRU，结果跟随机差不多。那何必呢？
硬件开销：
- 只需要一个伪随机数发生器
- 或者直接用系统时钟的低几位
- 几乎为零的额外存储
嗯，这里要注意：随机替换有个致命问题——不可复现。同样的程序跑两次，性能可能不一样。这在调试阶段简直是噩梦。我有个同事debug了三天，最后发现是随机替换在作怪。
3.4 伪LRU（Tree-PLRU）—— 性价比之王
我个人最喜欢这个方案。它用一棵二叉树来近似LRU的行为，但硬件开销小得多。
原理：
- 对于N路组相联，维护一棵有N-1个节点的二叉树
- 每个节点是一个比特，表示「上次访问在左子树还是右子树」
- 替换时，沿着树往下走，每次都选「没被访问过」的那一侧
举个例子，4路组相联的Tree-PLRU：
根节点 (bit0)
/ \
左子树(bit1) 右子树(bit2)
/ \ / \
way0 way1 way2 way3每次访问way0，就把bit0设为0（表示左子树刚被访问），bit1设为0（表示左子树的左路刚被访问）。替换时，看bit0，如果是0就去右子树，如果是1就去左子树。以此类推。
硬件开销：
- 只需要 N-1 个比特（N为路数）
- 4路只需要3比特，8路只需要7比特
- 更新逻辑简单，只需要更新路径上的节点
我在一个边缘AI芯片项目里用了Tree-PLRU。8路组相联，每组7比特。相比全LRU的24比特，面积节省了70%以上。而且实测命中率只差了不到2%。
我的经验：如果你在做芯片设计，路数在4路以上，我强烈建议用Tree-PLRU。它几乎是LRU的完美替代品。只有在一些极端场景下（比如频繁的循环访问），Tree-PLRU才会比LRU差一点。
3.5 四种策略对比
| 策略 | 硬件开销 | 命中率 | 实现复杂度 | 适用场景 |
|---|---|---|---|---|
| LRU | 高（N×log₂N比特） | 最高 | 高 | 通用，对性能要求极高 |
| FIFO | 低（log₂N比特） | 中等 | 低 | 流式访问 |
| 随机替换 | 极低 | 中等偏低 | 极低 | 访问模式随机 |
| Tree-PLRU | 低（N-1比特） | 接近LRU | 中 | 大多数场景 |
3.6 核心逻辑流程图
下面这张图展示了四种策略在替换决策时的核心逻辑。我特意用SVG画出来，方便你理解每种策略的决策路径。
从这张图可以清楚看到，四种策略的决策路径完全不同。LRU最复杂，需要维护全局顺序；FIFO和随机替换最简单；Tree-PLRU则是在复杂度和性能之间取了巧。
3.7 实际项目中的选择建议
说了这么多，到底怎么选？我根据多年经验给个参考：
- L1缓存：用Tree-PLRU。L1对延迟敏感，Tree-PLRU的硬件开销小，延迟低。
- L2缓存：可以用LRU或者Tree-PLRU。L2的容量大，路数多，LRU的硬件开销会很大。
- LLC（最后一级缓存）：我建议用Tree-PLRU或者随机替换。LLC的访问频率低，没必要用昂贵的LRU。
- 专用加速器：如果访问模式已知，直接用FIFO或者定制策略。
重要提醒：不要盲目追求理论上的最优命中率。我曾经见过一个团队，为了把命中率从95%提升到96%，用了全LRU，结果芯片面积增加了8%，功耗增加了5%。最后算下来，性价比极低。
好了，缓存替换策略就讲到这里。记住一句话：没有最好的策略，只有最合适的策略。下一节我们聊聊写策略——写直达和写回，那个坑更多。