Cache 三种映射方式（直接/全相联/组相联）

基础知识（先把底层逻辑讲明白）

一、从“块”开始：Cache 是什么？为什么要映射？

如果你还不知道 Cache 是啥，可以把它理解成：

CPU 旁边的一小块“超快内存”（容量小但速度快）
主存（内存）很大但更慢

CPU 运行时会频繁读/写内存。为了避免每次都去“慢的主存”取数据，硬件会把最近用过、很可能马上还会用到的数据，先放进 Cache。

为什么 Cache 不是“按一个字节/一个字”搬运，而是“按块（Block）”搬运？

因为程序往往有 局部性（Locality）：

*   **时间局部性**：刚用过的数据，可能马上还会用。
*   **空间局部性**：访问了地址 A，往往很快也会访问 A 附近的地址。

所以 Cache 和主存交换数据时，通常一次把一整段连续地址搬上来，这段连续地址就叫一个 块（Block）。

举个最直观的例子：

块大小 = 16B
你读取地址 0x1000 的 1 个字节

硬件往往会把 0x1000 ~ 0x100F 这 16B 整块放进 Cache。这样你接下来再访问 0x1001、0x1002……就很可能直接命中（hit）。

“映射（Mapping）”到底在干嘛？

关键矛盾只有一句：Cache 容量远小于主存。

主存里有海量的块，但 Cache 里只有有限的“位置”能放块（这些位置叫 行 Line）。于是必须规定：

“主存的某个块，进 Cache 时允许放到哪些行（或哪些组 Set）里？”

这个规定就是 映射方式。

不同映射方式的区别，就体现在：

  - 允许放的位置越多：越不容易互相顶掉（冲突少），但查找/硬件更复杂。
  - 允许放的位置越少：查找更快/硬件更简单，但更容易冲突（两个热块老挤一个位置）。

这页只讲一件事：一段内存地址（或内存块）到底怎么“放进”Cache。

二、一次访问到底发生什么：Hit/Miss 机制

很多同学卡住不是因为公式，而是因为不知道“算出来的 Tag/Index 到底拿去干嘛”。下面给你一个能直接套题的流程。

Cache 一行（Line）里通常有什么

把一行想成一个小盒子，里面至少有：

Valid 位：这行里有没有装过有效数据（没装过就一定 miss）。
Tag：这行当前装的是“主存的哪一个块”。
Data（数据块）：真正的块内容。

可能还会有（看题目/课程深度，知道即可）：

Dirty 位：写回法（write-back）时用，表示这行数据是否被改过。
替换信息：比如 LRU 需要的“最近使用情况”。

一次读/写访问的标准流程（最重要）

不管直接映射/全相联/组相联，流程本质都一样，只是“要检查的行数”不同：

算块地址 BlockAddr：先把地址按块大小折算成“这是第几个块”。
根据映射方式定位候选位置：
- 直接映射：候选 = 1 行（算出 LineIndex）。
- 组相联：候选 = 1 组内的 k 行（算出 SetIndex）。
- 全相联：候选 = 全部行（没有 Index）。
命中判定（Valid + Tag 比较）：
- 如果某个候选行 Valid=1 且 Tag 匹配：Hit。
- 否则：Miss。
Hit 之后怎么取数据：用 Offset 在这行的 Data 里取到块内对应的字节/字。
Miss 之后会发生什么（装入/替换）：
- 从主存把“目标块”取到 Cache。
- 若候选位置有空行：直接放进去。
- 若没有空行：按替换策略（LRU/FIFO/随机）选一个受害者（victim）顶掉。
- 若采用写回法且 victim 的 Dirty=1：先把 victim 写回主存，再覆盖。

一张“从地址到命中/缺失”的流程图（ASCII 版）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


CPU 发起一次访存（给你一个地址 Addr）
                |
                v
      按块大小切：BlockAddr = floor(Addr / BlockSize)
                |
                v
      按映射方式定位候选位置（行/组）：
        - 直接映射：LineIndex = BlockAddr mod NumLines
        - 组相联：  SetIndex  = BlockAddr mod NumSets（组内 k 路都要查）
        - 全相联：  候选 = 全部行
                |
                v
      在候选行里做命中判定：
        若存在某行：Valid=1 且 Tag 匹配  --->  HIT
        否则                              --->  MISS
         |                                     |
         |                                     v
         |                           选空行或按替换策略挑 victim
         |                                     |
         |                      (若 write-back 且 victim Dirty=1 则先写回)
         |                                     |
         |                                     v
         |                           从主存取目标块，装入 Cache
         |                                     |
         v                                     v
  用 Offset 取块内数据/完成读写          重新访问（这次通常会 hit）

写策略（题目不考细节也能看懂）

写操作常见两对策略（题目若没说，通常只考映射/命中率，写策略可忽略）：

Write-through（写直达）：写 Cache 同时写主存（简单但慢）。
Write-back（写回）：先只写 Cache，换出时再写回（快但要 Dirty 位）。
Write-allocate（写分配）：写 miss 也把块先装入 Cache 再写（常见）。
No-write-allocate：写 miss 不装入 Cache，直接写主存（某些场景用）。

三、术语对齐：块（Block）/ 行（Line）/ 组（Set）

块（Block）：Cache 和主存交换数据的最小单位。题目常给“块大小 = 4 字 / 16B”等。
行（Line）：Cache 里存放一个块的位置。有时也叫“Cache 块”。
组（Set）：组相联里的一组“行”。例如 2 路组相联 = 每组 2 行。

你只要记住：

直接映射：每个主存块只能去 Cache 的“唯一一行”。
全相联：每个主存块可以去 Cache 的“任意一行”。
组相联：每个主存块只能去“唯一一组”，但在组里可以去“任意一行”。

四、三种映射方式总览（先建立直觉）

方式	主存块能放到哪里	查找速度	硬件成本	常见缺失类型
直接映射 (Direct Mapped)	固定 1 行	最快	最低	冲突缺失明显
全相联 (Fully Associative)	任意行	最慢	最高	基本无冲突缺失
组相联 (Set Associative)	固定 1 组 + 组内任意行	居中	居中	冲突缺失缓解

缺失（Miss）通常分三类（考试高频）：

强制缺失（Compulsory/Cold Miss）：第一次访问某块必 miss。
容量缺失（Capacity Miss）：Cache 总容量不够，装不下要用的块。
冲突缺失（Conflict Miss）：容量够，但“映射规则”把多个块挤到同一行/同一组。

五、地址怎么切：Tag / Index / Offset

题目常写：

$$ \text{Address} = \text{Tag} \parallel \text{Index} \parallel \text{Offset} $$

含义（按字节寻址的经典默认）：

Offset（块内偏移）：你要这个块里的第几个字节/字。
Index（索引）：去 Cache 的哪一行（直接映射）/哪一组（组相联）。
Tag（标记）：用来确认“这一行/这一组里装的到底是哪一个主存块”。

三种映射方式（核心）

块地址（Block Address）：
$$ \text{BlockAddr} = \left\lfloor \frac{\text{MemAddr}}{\text{BlockSize}} \right\rfloor $$
直接映射：
$$ \text{LineIndex} = \text{BlockAddr} \bmod \text{NumLines} $$
$k$ 路组相联（$k$-way）：
$$ \text{SetIndex} = \text{BlockAddr} \bmod \text{NumSets},\quad \text{NumSets}=\frac{\text{NumLines}}{k} $$

小提示：如果题目给的访问序列看起来像 16,17,18,19 ... 这种“连续加 1”，很可能给的是字地址或字节地址；你要先用块大小把它们折算成块地址（上面的 BlockAddr）。

一、直接映射（Direct Mapped）

规则（一句话版）

每个主存块只能映射到 Cache 的唯一一行：

$$ \text{LineIndex} = \text{BlockAddr} \bmod \text{NumLines} $$

做题时你在做什么

先算这个访问属于哪个 BlockAddr。
再用取模算出它去 哪一行。
去那一行比对 Tag：
- Tag 相同：命中（Hit）
- Tag 不同或空：缺失（Miss），把新块塞进来（旧的被直接踢掉）。

直观图

Direct Mapped Cache

二、全相联（Fully Associative）

规则（一句话版）

主存块可以进 Cache 的任意一行，所以 没有 Index（或 Index 长度为 0）。

做题时你需要注意什么

命中判定：要在“所有行”里找 Tag（硬件用并行比较，题目里就理解为“全表查”）。
缺失时：必须有 替换策略（LRU/FIFO/随机）。题目不说通常默认随机或 LRU（看老师口径）。

直观图

Fully Associative Cache

三、组相联（Set Associative）

规则（一句话版）

主存块只能去唯一一组，但可以放到组内任意一路（way）：

$$ \text{SetIndex} = \text{BlockAddr} \bmod \text{NumSets} $$

2 路组相联：你脑中应该出现的画面

Cache 被分成很多组（Set）。
每组里有 2 行（2 way）。
来了一个块：先用取模找到组号；再在这组里两行都比 Tag。

直观图

Set Associative Cache

题目与练习（把分数拿到手）

一、一个极小例子把三种方式“算通”

假设（为了演示简单）：

Cache 一共 4 行
块大小 = 1（忽略 Offset）
访问的块序列：0, 4, 0, 4

直接映射（4 行）

LineIndex = BlockAddr mod 4
0 和 4 都映射到行 0
结果：0 miss，4 miss（顶掉 0），0 miss（顶掉 4），4 miss
全是 miss：典型的冲突缺失

全相联（4 行）

0、4 都能进任意行
结果：0 miss，4 miss，0 hit，4 hit

2 路组相联（4 行 = 2 组 × 2 路）

NumSets=2，SetIndex=BlockAddr mod 2
0 和 4 都落到组 0，但组 0 有 2 路
结果：0 miss，4 miss（组0 还装得下），0 hit，4 hit

二、题目分析

Cache：2 路组相联

Cache 总行数：32 行（块）

块大小：4 字（word）

地址位宽：16 位（本题命中率计算不一定用到位宽）

访存序列（看起来是“字地址”）： 16 17 18 19 144 145 146 147 252 253 465 466

第一步：把“地址”先变成“块地址 BlockAddr”

块大小是 4 字，所以每 4 个连续字地址属于同一个块：

$$ \text{BlockAddr} = \left\lfloor \frac{\text{WordAddr}}{4} \right\rfloor $$

把序列换成块地址：

16~19 都在块 $\lfloor 16/4 \rfloor = 4$
144~147 都在块 $\lfloor 144/4 \rfloor = 36$
252~253 都在块 $\lfloor 252/4 \rfloor = 63$
465~466 都在块 $\lfloor 465/4 \rfloor = 116$

所以块序列是：

4,4,4,4, 36,36,36,36, 63,63, 116,116

第二步：算组号（2 路组相联）

总行数 32，2 路 $\Rightarrow$ 组数：
$$ \text{NumSets} = 32/2 = 16 $$
组号：
$$ \text{SetIndex} = \text{BlockAddr} \bmod 16 $$

计算：

块 4：$4\bmod 16=4$（组 4）
块 36：$36\bmod 16=4$（组 4）
块 63：$63\bmod 16=15$（组 15）
块 116：$116\bmod 16=4$（组 4）

注意：4、36、116 三个块都挤在同一组（组 4），这就是本题的“冲突热点”。

第三步：按替换策略判 Hit/Miss（假设初始 Cache 为空，组内 LRU）

访问块 4：miss（把块 4 装入组 4）
再访问块 4 三次：hit、hit、hit（同一块内连续访问，体现空间局部性）
访问块 36：miss（组 4 还有空位，装入）
再访问块 36 三次：hit、hit、hit
访问块 63：miss（装入组 15）
再访问块 63 一次：hit
访问块 116：miss（组 4 满了，需要替换；LRU 会踢掉“更久没用”的块 4）
再访问块 116 一次：hit

统计：

总访问：12 次
miss：4 次（第一次见到块 4 / 36 / 63 / 116）
hit：8 次

命中率：

$$ \text{HitRate} = \frac{8}{12} = \frac{2}{3} \approx 66.7\% $$

这题在考你什么

块大小带来的空间局部性：16~19 一次装块后后面 3 次都 hit。
组相联缓解冲突：虽然 4、36、116 都落同一组，但 2 路能同时容纳其中两个。
替换策略影响细节：如果后续又访问块 4，就会因为刚才被踢掉而 miss。

三、举一反一（一个正例 + 一个反例）

正例：先“算块地址”再“算组号/行号”

题设：块大小 4 字，访问字地址 145。

块地址：$\lfloor 145/4 \rfloor = 36$
2 路组相联，32 行 $\Rightarrow$ 16 组
组号：$36\bmod 16=4$

结论：它一定在组 4（组内哪一路要看替换策略与当前内容）。

反例：把“字地址”当成“块地址”直接取模（常见低级错）

错误做法：直接拿 145 mod 16 = 1，说它在组 1。

为什么错？

因为 Cache 映射是按“块”为单位的。
145 是块内的一个字地址，它属于块 36；映射应该用 36 去取模，而不是用 145。