三种映射结构 —— 一个地址能放在缓存的哪些位置
本篇是缓存组织拆分的映射结构篇：讲透直接映射 / 全相联 / N 路组相联三种结构的原理与取舍。核心问题只有一句：一个物理地址，被允许放进缓存的哪些位置——位置越自由，冲突越少，但要并行比的 tag 越多、硬件越贵。配套"同一串访问、三种结构"的对比 demo，以及替换策略（组满了踢谁）。前提：物理地址三段拆分与命中判定的硬件电路，见寻址与命中篇。
一、先搞清三个词：line、组(set)、way
这三个词贯穿全篇，先一次讲清它们的关系——缓存是个二维网格：
- cache line（缓存行）：缓存的最小存储/管理单位，一条固定 64 字节，是网格里的一个"格子"。
- 组 (set)：网格的一行。整个缓存被切成 S 个组；一个物理地址只能落进其中某一个组（由 Index 决定）。
- way（路）：网格的一列，也就是"每个组里有几条 line"。N 路(N-way) = 每组有 N 条 line。
关键关系与记忆：
| 词 | 是什么 | 决定它的 |
|---|---|---|
| line | 一个格子（64B 数据 + tag + 状态位） | —— |
| 组 set | 一行（S 个组） | 地址的 Index 唯一选中一个组 |
| way | 一列（每组 N 条 line） | 芯片设计固定；也叫"相联度 N" |
- 总容量 = 组数 S × way 数 N × line 大小(64B)。比如 32KB = 64 组 × 8 way × 64B。
- 地址 → 组：算出来的、唯一（Index 译码）；组 → 具体 way：比出来的、不唯一（组内并行比 N 个 tag，因为数据可能在这组的任意一 way）。
- "几路(N-way)"就是"每组几条 line"：1 路=每组1条=直接映射；N 路=每组 N 条；组数=1(全部 line 挤一组)=全相联。下面就把同样 8 条 line 按不同的"组×way"切法排列。
二、三种结构：一个地址能放在哪些位置
三种结构的唯一区别是：一个物理地址，允许被放进缓存的哪些位置。用停车场类比最直观（一个车位 = 一条 cache line，一个区 = 一个组，车牌尾号 = 地址的 Index）：
| 结构 | 停车规则 | 找车（判断在不在） |
|---|---|---|
| 直接映射 | 每辆车只能停自己车牌对应的那一个固定车位（尾号 3 就只能停 3 号位） | 只看那 1 个车位 |
| 全相联 | 车随便停任意空位 | 得把整个停车场每个位都看一遍 |
| N 路组相联 | 车牌尾号决定停哪个区(组)，区内有 N 个位(way)随便停 | 只看那个区的 N 个位 |
直接映射找得最快但最容易"车位被占只能赶走别人"；全相联最灵活但找车最慢；组相联折中——先按尾号缩小到一个区(组)，再在区内 N 个位(way)里找。
换个视角：这其实是一个"会冲突的硬件哈希表"
用 Index 定位到组，本质就是一次哈希：h(addr) = (addr >> Offset位) & (组数-1)——取地址中间几位做哈希值，硬件用它直接索引到桶（组），O(1)。所以"根据物理地址查缓存"确实可以理解为硬件实现的哈希查找。
但关键：这个哈希绝不保证不冲突，恰恰相反，冲突是必然且频繁的。地址空间（2⁴⁸）远大于组数（几十~几千），无数不同地址会哈希到同一组（Index 相同）——这就是冲突失效。缓存不消除冲突，而是用两层机制管理冲突：
| 哈希表概念 | 缓存里对应什么 | 作用 |
|---|---|---|
| 哈希函数 | Index = 取地址中间位 | 直接定位到桶（组），会冲突 |
| 哈希桶 | 一个 set（组） | 冲突的地址落进同一个桶 |
| 桶的固定深度 | 每组 N 个 way | 允许 N 个冲突地址共存（桶满就得踢一个） |
| 桶内精确比对 | Tag 比对 | 区分"哈希撞桶但其实不是同一地址"的不同 key |
所以准确说：Index 是会冲突的哈希、way 是每个桶的固定槽数（容纳冲突）、Tag 是桶内精确判定（区分撞桶的不同地址）。它是一个"桶深固定为 N、用开放定址而非链表"的哈希表——桶满(N 个 way 都占了)不能无限加链，只能按替换策略踢一个出去。这正是"提高相联度 = 加深桶 = 少冲突"的由来。
三种结构是"物理焊死"的，差异 = 地址允许落脚的位置数
再强调一点：一颗 CPU 的 L1/L2/L3 各是几路组相联，是芯片设计时用晶体管布线定死的——比较器数量、译码器、way 的槽位都是实打实的电路，运行时不可改（少数服务器芯片支持 way-partitioning 把 way 划给不同核，改的是分配、不是结构本身）。三种结构的差异，归根到底就是**"一个物理地址允许落脚的位置数"**：
| 结构 | 地址 X 能放的位置 | 位置自由度 |
|---|---|---|
| 直接映射 | 只能去 Index(X) 那一个位置 | 1 |
| N 路组相联 | 只能去 Index(X) 那一组，组内 N 个 way 任选 | N |
| 全相联 | 任意位置 | 全部 |
位置越自由 → 冲突越少 → 但要并行比的 tag 越多、硬件越贵。下面用同一地址在三种结构里走一遍，把"位置自由度"看具体。
为了能横向对比，统一用同一设定：缓存共 8 条 line、line 大小 4B（Offset=2 位）、物理地址 8 位。只改"这 8 条 line 怎么编组"，看同一个地址 0x6C 落在哪、要比几个 tag。核心一句话：way = 一组里有几条 line；改相联度，本质是改"组数 × 每组 way 数"的分配，8 条 line 总量不变。
三、直接映射（Direct-Mapped）= 每组 1 条 line（8 组 × 1 way）
8 条 line 各自成组 → 8 组，每组 1 条。Index 需 3 位（2³=8 选 1），一个地址只有唯一一个能去的位置。
- 地址拆分：
Tag(3) | Index(3) | Offset(2)——Index 占 3 位（8 组）。 - 查找：Index 直接选中唯一一组，只比 1 个 tag，最快最省电。
- 致命伤——冲突失效：所有
Index=011的地址（0x6C、0x2C、0xAC…）都抢组3 这一个位，来一个踢一个，哪怕别的组全空。循环里交替访问两个同 Index 地址 → 反复互踢（thrashing），命中率归零。
四、全相联（Fully-Associative）= 1 组，8 条随便放
8 条 line 全在同一组，地址可放进任意一条 → 无 Index 段（不必选组），地址只拆成 Tag | Offset。
- 地址拆分：
Tag(6) | Offset(2)——没有 Index，本该给 Index 的位全并进 Tag，故 tag 更长（存储开销更大）。 - 查找：数据可能在任意一条，必须同时比全部 8 个 tag（8 个比较器）。
- 优点：无冲突失效——只要还有空位就能放，空间利用率最高。
- 缺点：比较器数量 = line 总数，面积/功耗随容量爆炸。只用于条目极少的结构——最典型是 TLB（几十~几百项）。L1/L2/L3 上千条 line，用不起。
五、N 路组相联（N-Way）= 折中（这里 4 组 × 2 way）
8 条 line 分成 4 组、每组 2 条(2-way)。Index 选组（4 组 → 2 位），组内 2 条随便放、并行比 2 个 tag。这是 L1/L2/L3 的实际做法。
- 地址拆分：
Tag(4) | Index(2) | Offset(2)——Index 只需 2 位（4 组），介于直接映射(3位)和全相联(0位)之间。 - 查找：Index 先缩到一组，只比 2 个 tag（不是全部 8 个）——比较器数量可控。
- 缓解冲突：同
Index=11的地址现在有 2 个位可共存（w0/w1），不像直接映射来一个踢一个。 - N 越大越接近全相联：冲突越少，但比较器越多、越慢越耗电。L1 常用 8-way，是甜点。
六、三种结构其实是一条连续谱
同样 8 条 line，只是"怎么编组"不同——直接映射和全相联就是组相联的两个极端：
| 相联度 | 组数 | Index 位 | 比几个 tag | 冲突失效 | 成本 |
|---|---|---|---|---|---|
| 直接映射(1-way) | 8 | 3 | 1 | 最多 | 最低 |
| 2-way | 4 | 2 | 2 | 中 | 低 |
| 4-way | 2 | 1 | 4 | 少 | 中 |
| 全相联(8-way) | 1 | 0 | 8 | 无 | 最高 |
一句话：相联度 = 一组里的 way 数。way 越多 → 同 Index 的地址有越多共存位、冲突越少；但要并行比的 tag 越多、Index 位被挤短而 Tag 变长 → 越贵越耗电。真实 CPU 选 8~16 way，是"够低冲突 + 成本可接受"的平衡点。
两个极端其实是组相联的特例：直接映射 = 1-way；全相联 = 1 组、W = 全部行。
七、同一串访问，三种结构的 demo 对比
最能看清区别的方式：拿同一串地址访问序列，在只有 4 条 line 的缓存上，分别用三种结构跑一遍，看谁 miss 多。
设 line=1（简化，忽略 Offset），访问地址序列反复交替：0, 4, 0, 4, 0, 4。缓存共 4 条 line。
① 直接映射（4 组，每组 1 条）：Index = 地址 % 4。
地址 0 → Index 0；地址 4 → Index 0 ← 两个地址撞同一组！
访问 0 : Set0 空 → miss，装入 0
访问 4 : Set0 里是 0，tag 不符 → miss，踢掉 0 装入 4
访问 0 : Set0 里是 4 → miss，踢掉 4 装入 0
访问 4 : miss …… 每次都互相踢
结果：6 次访问 6 次 miss（0% 命中）—— 典型 cache thrashing
哪怕 Set1/2/3 全空着也没用，因为 0 和 4 只能放 Set0② 全相联（1 组，4 条 line 任意放）：
访问 0 : miss，装入 line0
访问 4 : miss，装入 line1（还有空位，不踢）
访问 0 : line0 命中 ✅
访问 4 : line1 命中 ✅
访问 0 : ✅ 访问 4 : ✅
结果：6 次访问 2 次 miss（前两次冷启动）—— 0 和 4 和平共处③ 2 路组相联（2 组，每组 2 way）：Index = 地址 % 2。
地址 0 → Index 0；地址 4 → Index 0 ← 又撞同一组，但这组有 2 个 way！
访问 0 : Set0.way0 空 → miss，装入 0
访问 4 : Set0.way1 空 → miss，装入 4（同组第二个位）
访问 0 : Set0.way0 命中 ✅
访问 4 : Set0.way1 命中 ✅ ……
结果：6 次访问 2 次 miss —— 组内 2 个位让 0、4 共存，冲突消失对比结论：同样的访问序列、同样 4 条 line 的容量——
| 结构 | miss 次数 | 为什么 |
|---|---|---|
| 直接映射 | 6/6 | 0 和 4 争抢唯一的 Set0，反复互踢 |
| 2 路组相联 | 2/6 | Set0 有 2 个 way，0、4 各占一个 |
| 全相联 | 2/6 | 随便放，只有冷启动 miss |
这就是冲突失效(conflict miss) 的本质：直接映射不是没空间，是"0 和 4 的 Index 相同、只准放同一个位"。提高相联度（更多 way）就是给同 Index 的地址更多共存位置——代价是要多比几个 tag。真实 CPU 选 8~16 way 正是这个折中。
八、三种结构对比总表
| 直接映射 | N 路组相联 | 全相联 | |
|---|---|---|---|
| 每组 line 数 | 1 | N | 全部 |
| 地址拆分 | Tag+Index+Offset | Tag+Index+Offset | Tag+Offset（无 Index） |
| 一个地址能放 | 唯一位置 | 一组内 N 选 1 | 任意位置 |
| 比 tag 次数 | 1 | N | 全部 |
| 冲突失效 | 多（严重） | 少 | 无 |
| 硬件成本/功耗 | 最低 | 中 | 最高 |
| 典型用途 | 早期/简单缓存 | L1/L2/L3（主流） | TLB、victim cache 等小结构 |
九、替换策略（组满了踢谁）
组相联/全相联下，一组满了要踢一条腾位置，常见策略：
| 策略 | 说明 |
|---|---|
| LRU（least-recently-used） | 踢最久没用的。效果好但精确 LRU 硬件贵，实际多用近似 LRU（如 tree-PLRU） |
| 随机/伪随机 | 简单，效果尚可，高相联度时常用 |
| FIFO | 踢最早进来的 |
被踢的行若是脏的（MSI 的 M 态），要先写回下层——这是"写回策略"和"替换"的交汇点（write-back 详见访问流程篇）。
十、对性能的实践含义
映射结构不只是教科书概念，它直接决定了三种现实中的缓存失效：
- 容量失效 (capacity miss)：工作集 > 缓存总容量，装不下——再高的相联度也救不了，只能换更大的缓存或减少工作集。
- 冲突失效 (conflict miss)：工作集装得下，但同 Index 的地址挤爆了某几个组的 way 数——提高相联度能缓解，代价见上文。
- 强制失效 (compulsory miss)：第一次访问，冷启动，任何结构都免不了。
高性能代码里最实用的推论是：当缓存命中率异常低而工作集明明不大时，先怀疑"跨距(stride)撞组"——比如数组大小恰好是 2 的幂、步长又正好让热点元素落到同一组，等于人造了一个直接映射缓存。此时改 stride、padding 或用哈希化访问顺序，往往比换结构更现实（毕竟结构是"焊死"的）。
跨距与伪共享的地址级根源、如何用 cache line 对齐规避，见总纲的一致性联系。把缓存机制落成具体编码习惯（顺序访问、SoA、避免指针追逐），见 cache-friendly-code。