缓存基础

同一个求和循环里，处理器不断访问相邻数组元素，也会反复取循环体那几条指令。若每一次都从更慢的下层存储取数据，流水线前几篇讨论的前递、停顿和分支恢复很快就被访存等待淹没。缓存的基本承诺很小：把最近用过或附近可能要用的一块数据放在更靠近处理器的位置，下一次地址命中时少走一段路。

本篇的核心问题是：给定一串地址，怎样判断每一次访问落在哪个 set、比较哪个 tag、替换哪一行，以及一次 miss 是冷缺失、容量缺失还是冲突缺失？核心案例使用 16B block、4 个 cache line 的有限模型，对同一地址序列分别跑直接映射和两路组相联。证据等级为功能执行，所有数字来自可复跑 Python 模型；它不是 gem5 仿真，也不是本机硬件计数器。

实验目录为 examples/computer-architecture/cache/。本文附件包括 mapping.json.txt、cache_model.py.txt 和 run_cases.py.txt。附件扩展名使用 .txt，便于博客直接下载查看。

从地址到 block、set 和 tag

缓存不按单个字节管理数据，而按 block 管理。本文固定 block size 为 16B，地址 A 所在 block 为 A // 16。若有 S 个 set，则 set index 为 block % S，tag 为 block // S。查找时只在对应 set 内比较 tag。

以地址 64 为例，64 // 16 = 4，在 4-set 直接映射 cache 中 index 为 4 % 4 = 0，tag 为 4 // 4 = 1。地址 0 的 block 为 0，也映射到 index 0，但 tag 为 0。两者不能同时存在于这个 set 的唯一 way 中；后来的 64 会替换 0。

这种拆分解释了“相邻地址为什么容易命中”和“相隔很远的地址为什么也可能冲突”。地址 0 和 8 属于同一 block；地址 0 和 64 属于不同 block，却落入同一个 set。空间局部性靠 block 捕获，冲突则由 set 数和映射函数暴露。

地址查找先定位候选位置，再比较 tag。本文使用的拆分规则是 block=addr//block_size; set=block%sets; tag=block//sets。当工作集不大但命中率很低时，候选位置过少常常比总容量更早暴露问题。

直接映射的手算轨迹

地址序列固定为：

1	`0, 16, 32, 0, 64, 16, 80, 0`

直接映射 cache 的参数是 4 sets × 1 way × 16B block，总容量 64B。逐次访问得到：

次序	地址	block	set	tag	结果	原因
1	0	0	0	0	miss	第一次见到 block 0，冷缺失
2	16	1	1	0	miss	第一次见到 block 1，冷缺失
3	32	2	2	0	miss	第一次见到 block 2，冷缺失
4	0	0	0	0	hit	set 0 仍保存 block 0
5	64	4	0	1	miss	第一次见到 block 4，替换 set 0
6	16	1	1	0	hit	block 1 未被替换
7	80	5	1	1	miss	第一次见到 block 5，替换 set 1
8	0	0	0	0	miss	block 0 曾见过，但被 block 4 挤出

第 8 次不是冷缺失，因为 block 0 已经出现过。它也不是容量缺失：同样 4 个 line 的全相联 cache 可以同时保留访问过且仍有用的候选。它是冲突缺失，原因是 block 0 和 block 4 被强制放在同一个 set。

模型输出中 direct 的 miss kind 正是 cold,cold,cold,hit,cold,hit,cold,conflict。这条序列不是为了代表真实程序，而是为了把三类 miss 拆开：第一次出现是冷缺失；容量不足时全相联也保不住；容量够但映射位置打架时才叫冲突缺失。

组相联把“唯一位置”放宽成“候选集合”

两路组相联版本改成 2 sets × 2 ways × 16B block，总容量仍是 64B。容量没有变，但每个 block 可以在对应 set 的两个 way 里任选一行。地址 0 和 64 仍映射到同一个 set；区别是 set 里有两个位置，二者可以同时存在。

模型结果显示，同一序列下直接映射命中 2 次，两路组相联命中 3 次。多出来的一次来自最后的地址 0：在这条 trace 中，两路 cache 没有在第 5 次访问 64 时立刻挤掉 block 0。容量没增加，候选位置增加，冲突少了一次。

这种收益有边界。若一个 set 里轮流访问 3 个活跃 block，而它只有 2 个 way，LRU 仍要替换；若整个工作集超过总容量，全相联也会 miss。相联度解决的是候选位置太少，不解决所有数据太多。

保持总容量不变，只改变候选位置数量，可以把“容量不够”和“位置冲突”分开。本 trace 中，提高相联度减少了一次冲突缺失；这个结论只适用于当前访问序列，LRU 状态、访问顺序和 set 数都会改变结果。

替换策略只在候选都满时决定 victim

空行存在时，替换策略不应抢先赶走有效数据。gem5 的替换策略文档也把 invalid block 优先作为默认行为。本模型遵循同样口径：先找 invalid line；没有 invalid line 时，才按 LRU 的 touched_at 选择最久未访问的 line。

这里的 LRU 是教学实现，不等同于商品 CPU 的实际策略。真实硬件可能用近似 LRU、随机化或更复杂的重引用预测，因为精确维护所有 way 的最近使用顺序有面积和时序成本。本篇只要求读者能手算有限序列，不把 LRU 当作普遍硬件事实。

替换策略还不能和写策略混在一起。读 miss 装入 block，写 hit 是否立刻写下层，写 miss 是否分配 line，都属于下一篇的问题。第 16 篇只关心：地址能去哪、tag 怎么比、候选满时谁被替换。

缺失分类的正确用法

冷缺失由“第一次访问这个 block”定义。容量缺失需要和同容量全相联 cache 对照：若全相联也保不住，才是容量问题。冲突缺失则是组相联或直接映射比全相联更差造成的 miss。

分类的价值在于给优化指方向。冷缺失常靠预取、初始化顺序或更大 block 缓解；容量缺失需要减小工作集或增加有效容量；冲突缺失可能通过 padding、改变数组布局、改变 stride 或提高相联度缓解。只喊“cache miss 多”没有动作信息。

本文案例里第 8 次访问地址 0 是冲突缺失。若把地址 64 改成 48，它映射到 set 3，不会替换 set 0，最后一次 0 就会命中。这个小改动说明：有些 miss 不需要更多容量，只需要避开同一个 set。

复跑与验收

在仓库根目录执行：

1	`bash examples/computer-architecture/cache/scripts/run_all.sh`

本篇关注 outputs/mapping.json。验收应检查：direct 的 miss kind 为 cold,cold,cold,hit,cold,hit,cold,conflict；direct 命中数为 2；two-way LRU 命中数为 3；最后一次地址 0 在 direct 中是冲突缺失。

这些结果证明的是有限 Python 模型符合题设。它没有验证某台机器的 cache size、line size、替换策略或硬件事件计数。后续正式实验若要写“真机 L1 miss”，必须给出机器、计数器、编译命令、重复测量和测量区间。

两道练习

练习一： 仍使用 4 sets × 1 way × 16B 的直接映射 cache，访问地址 0, 64, 128, 0。最后一次 0 是哪类 miss？

解答：这些地址的 block 分别为 0、4、8、0，全部映射到 set 0。最后一次 0 不是第一次出现，因此不是冷缺失；同容量全相联 cache 有 4 行，可以同时容纳 0、4、8，因此不是容量缺失。它是冲突缺失。

练习二： 把本文序列放到 1 set × 4 way 的全相联 cache 中，最后一次地址 0 会不会 miss？

解答：不会。到第 7 次为止，活跃 block 为 0、1、2、4、5，共出现过 5 个不同 block；但在第 7 次插入 block 5 时，LRU 会淘汰最久未用的 block 2，而 block 0 在第 4 次刚被访问过，仍会留下。因此第 8 次地址 0 命中。

参考资料

gem5：Indexing Policies。2026-09-22 核查；支持 set-associative、direct-mapped 是 1-way、full-associative 是 N-way 的定位口径。
gem5：Replacement Policies。2026-09-22 核查；支持 invalid block 优先、LRU 依据 last touch timestamp 选择 victim。
CS61C：Fully Associative Cache。2026-09-22 核查；用于 tag/offset/valid bit、LRU、write-through/write-back/dirty bit 的教学表述。
本系列 cache 教学模型。本文实际附件来自本地工作区当前输出，不声称 GitHub 链接已经包含本轮未提交文件。