3. Cache 基础概念：直接映射、组相联、全相联 Cache 结构与替换策略
好，咱们今天聊聊 Cache 的三种基本结构。说实话，这部分是存储层次设计的基石。我在刚入行时，总觉得 Cache 就是个“大缓存”，后来被 mentor 带着调了一次性能，才发现里面的门道深着呢。
你想想看，CPU 跑得飞快，内存却慢吞吞的。Cache 就是中间的“缓冲带”。但怎么把内存数据放到 Cache 里？放哪里？满了怎么办？这就是映射方式和替换策略要解决的问题。
3.1 直接映射 Cache
直接映射，说白了就是“一个萝卜一个坑”。每个内存地址只能映射到 Cache 中唯一的一个位置。
怎么算这个位置？很简单：
Cache 行号 = (内存块地址) % (Cache 总行数)举个例子。假设 Cache 有 8 行，内存块地址 0、8、16……都映射到第 0 行。地址 1、9、17……都映射到第 1 行。
核心特点：
- 硬件实现最简单——只需要一个比较器
- 查找速度最快——直接算索引，不用遍历
- 冲突率最高——多个地址抢同一行
我在项目中遇到过一个问题：一个循环访问两个数组，恰好它们的地址映射到同一个 Cache 行。结果每次访问都 miss，性能直接崩了。这就是典型的“Cache 抖动”。
避坑指南：我曾经调试过一个视频编解码模块，帧率死活上不去。最后发现是输入缓冲和输出缓冲在直接映射 Cache 中冲突了。解决办法很简单——把其中一个数组的起始地址偏移一下，避开冲突。
3.2 全相联 Cache
全相联是另一个极端。任何内存块可以放在 Cache 的任何位置。没有“固定坑位”这一说。
听起来很灵活对吧？但代价也大：
- 每次查找都要比较所有 Cache 行——硬件开销巨大
- 需要 n 个比较器并行工作——n 是 Cache 行数
- 功耗高、延迟大——不适合大容量 Cache
实际应用：全相联通常只用在 TLB（快表）这种小容量结构中。我见过最大的全相联 Cache 也就几十行。再大，芯片面积和功耗就扛不住了。
3.3 组相联 Cache
组相联是前两者的折中方案。它把 Cache 分成若干组，每组内有若干行。内存块先映射到某个组，然后在组内可以自由放置。
用公式表示：
组号 = (内存块地址) % (组数)
组内查找：遍历组内所有行比如 4 路组相联，就是每组有 4 行。内存块先算组号，然后在这 4 行里找。
| 参数 | 直接映射 | 组相联 | 全相联 |
|---|---|---|---|
| 冲突率 | 高 | 中 | 低 |
| 硬件复杂度 | 低 | 中 | 高 |
| 查找延迟 | 低 | 中 | 高 |
| 典型路数 | 1 路 | 2~16 路 | 全部 |
| 实际应用 | 早期 CPU | 现代 CPU L1/L2 | TLB、小容量缓冲 |
我个人习惯在 L1 Cache 用 4~8 路组相联。为什么？因为 2 路冲突还是有点高，16 路以上延迟增加明显，性价比最好的就是 4 路和 8 路。
3.4 替换策略
Cache 满了怎么办？得把某一行踢出去，让新数据进来。这就是替换策略。
3.4.1 LRU（最近最少使用）
LRU 是业界最常用的策略。它替换掉最长时间没有被访问的那一行。
实现方式：
- 每行维护一个“年龄”计数器
- 每次访问，被访问行的计数器清零，其他行加 1
- 替换时，选计数器最大的行
优点：性能好，能很好地利用时间局部性。
缺点：硬件开销大——每组需要维护 n 个计数器，还要做比较。
我记得有一次做 RISC-V 处理器设计，L2 Cache 用了精确 LRU。综合后一看面积，好家伙，替换逻辑占了 Cache 控制器的 40%。后来改成了近似 LRU。
3.4.2 伪 LRU（近似 LRU）
伪 LRU 用二叉树来近似 LRU 的行为。每组维护一棵二叉树，每个节点指示“左右子树哪边更久没被访问”。
举个例子，4 路组相联的伪 LRU：
- 树有 3 个节点（4-1=3）
- 每个节点 1 bit，共 3 bit
- 替换时沿着树走，选“更久未访问”的那一侧
经验之谈：伪 LRU 的性能和精确 LRU 非常接近，但硬件开销小得多。我做的几个项目都用伪 LRU，没出过问题。
3.4.3 随机替换
随机替换就是随便选一行踢出去。实现最简单——一个随机数生成器就行。
你可能会问：“随机能行吗？”
嗯，在某些场景下还真行。比如一些流式处理应用，数据只访问一次，LRU 和随机效果差不多。但通用场景下，随机比 LRU 差 10%~20%。
3.4.4 FIFO（先进先出）
FIFO 替换最早进入 Cache 的那一行。实现简单，用环形队列就行。
但有个问题：经常访问的“热数据”可能被 FIFO 踢出去，而“冷数据”却留在里面。这种现象叫“颠簸”。
注意：我曾经在一个网络处理器项目中用了 FIFO，结果热点数据频繁被踢，Cache miss 率飙升到 40%。换成 LRU 后，直接降到 5%。从那以后，我再也没在通用处理器中用 FIFO。
3.5 三种结构与替换策略的搭配
不同的 Cache 结构适合不同的替换策略：
| Cache 结构 | 推荐替换策略 | 原因 |
|---|---|---|
| 直接映射 | 无（不需要） | 每个地址只有唯一位置，没得选 |
| 组相联（2~4 路） | 伪 LRU | 硬件开销小，性能接近 LRU |
| 组相联（8 路以上） | LRU 或 伪 LRU | 路数多，LRU 开销可接受 |
| 全相联 | LRU | 行数少，精确 LRU 可行 |
3.6 知识结构图
下面这张图总结了三种映射结构和替换策略的关系：
3.7 实际设计中的选择
说了这么多，到底怎么选？我总结几条经验：
- L1 Cache：用 4~8 路组相联 + 伪 LRU。延迟要低，面积要小。
- L2 Cache：用 8~16 路组相联 + LRU。容量大，可以接受稍高的延迟。
- TLB：用全相联 + LRU。行数少，精确 LRU 可行。
- 专用加速器：如果数据访问模式固定，直接映射 + 无替换策略反而更简单高效。
一个小技巧：在做架构探索时，先用模拟器跑一下不同配置的 miss 率。我习惯用 gem5 做这个事。等找到最优配置，再动手写 RTL。这样能省很多迭代时间。