缓存层次
CPU 通常先访问小而快的缓存，再访问 DRAM。常见层次有 L1、较大的 L2、共享 L3 与主存。同一条 load 的成本取决于哪层持有数据，以及缓存如何查找和重叠请求。本课按逐层相加的简化模型计费。
缓存按缓存行搬运相邻数据，不是只搬当前请求的一个字。常见 x86 与许多 ARM 核心的行是 64 字节，Apple silicon 常见 128 字节，具体以芯片为准。一次取回整行，后面访问同行数据就能复用这次传输；每行只用一个字则利用率低。
行优先存储的二维数组按行遍历，会连续使用同一缓存行。按列遍历相同元素，可能每行只取一个字，回访前已被替换。加法数量相同，内存流量与耗时却可能不同，差异取决于数组、容量和访问顺序。
缓存层次如何工作
模型有 64 个字，每行 4 字，共 16 行。L1 容纳 4 行、L2 容纳 8 行、L3 容纳全部 16 行，后面是 DRAM。默认 L1 直接映射。
字地址 w9 属于行 9//4=2，行内偏移 9%4=1。对默认 L1，地址最低两位是 offset，接着两位是 index，剩余高位是 tag。对这种 2 的幂布局，切字段对应布线，//、% 是描述，不需要通用除法器。
index 决定行能进 L1 哪个槽。行 #2 只能进二进制索引 10 的槽。槽内存有效位与 tag，用来区分映射到同槽的四个内存行。有效且 tag 相同就是命中，否则查 L2，再 L3，再 DRAM，在首次命中的层结束。
返回的是整行，并填入缺失的上层；从 DRAM 返回时依次安装到 L3、L2、L1。L1 的指定位置已有其他行时会替换它。
各层即使未命中也收费，因为完成了检查。本课 L1=4、L2=12、L3=40、DRAM=200 周期，因此总成本为：
| 命中位置 | 总周期 |
|---|---|
| L1 | 4 |
| L2 | 4+12=16 |
| L3 | 4+12+40=56 |
| DRAM | 4+12+40+200=256 |
这些数字属于串行检查模型，不是任意硬件的实测延迟。
逐步演示
默认依次读取十二个字 w0–w11，L1 为直接映射。
- 读 w0：行 #0、offset=0、index=00、tag=00。L1 槽为空，L2、L3 也没有，属于首次访问的强制缺失，花
4+12+40+200=256周期。从 DRAM 一起返回 w0、w1、w2、w3，安装到三级缓存，L1 槽原来为空，无需替换。 - 读 w1：仍是行 #0，只是 offset=1。index、tag 不变，L1 有效且匹配，花 4 周期，不再取下层。
- 读 w2、w3：各 4 周期，首个请求带回的四个字全部被用到。
- 读 w4：行 #1，index=01，进入不同槽；首次缺失花 256 周期，带回 w4–w7。
- 读 w5–w7：各命中，4 周期。
- 读 w8：行 #2 首次缺失，256 周期；w9–w11 各命中，4 周期。
十二次读取分布在三行，共三次缺失、九次命中，缺失率 25%。总计 3×256+9×4=804 周期。
末帧的参照条比较 stride 4。切到该模式，读取 w0、w4、w8、…、w44，仍十二次，但来自十二个不同的行，每行只用一个字。全部是首次缺失，12×256=3072 周期，约为顺序模式的 3.8 倍。
这与二维列遍历有关，但实验不完全相同。真实行列遍历是相同地址的不同顺序；本模型 L3 能容纳全部内存，相同地址集合无论何种顺序，首次 DRAM 取行次数相同，所以此处改变了地址集合。它展示的是读取覆盖多少不同的行、每行用了多少数据以及复用前需要保留多少行。
缺失不是同一种价格
conflict 模式交替读 w0、w16，共十次。行 #0 与 #4 都映射到 L1 的槽 00（4%4=0）。只用两行，L1 还有三个空槽，却每次互相替换，L1 命中率 0/10。
前两次从 DRAM 取行，之后的八次 L1 缺失都在 L2 命中，成本是 16，不是 256。数据离开 L1 不等于离开整个缓存系统。单看 L1 缺失率看不出下层命中的收益。
账本把 L1 缺失分成三类：
- 强制缺失：缓存行首次被需求访问，且没有预先取回。
- 冲突缺失：实际映射发生替换，但同容量的全相联缓存本来能保留该行。
- 容量缺失：同容量全相联缓存也会缺失。
模拟器同时维护全相联 L1 参照，按它的结果分类，不仅凭访问形状猜测。
切成 2-way，总容量仍为四行，变成两个组、每组两路。index 从两位减为一位，tag 增为三位。每行在所属组里有两个可用位置，原冲突模式变成前两次缺失、后八次命中，8/10。容量没有增加，只改变放置选择。
相联度、行大小、级数由硬件决定；程序通常能调整数据布局与访问顺序。扩容可能改变索引映射并消除某个冲突，但已有空槽不等于冲突行有权使用它们，不能只看总空闲容量。
working set 模式让十行循环两遍，超过 L1 四行和 L2 八行。第二遍每次都在 L1、L2 缺失，L3 命中，花 56 周期。LRU 的循环替换使即将回访的行已经被淘汰，增加两路不能消除容量不足。真实缓存还会采用其他或近似替换策略。
边界情况
- 首次访问一个字不一定是首次访问它的行。先读 w0 可让第一次读 w1 命中，预取也能提前带来该行。基准测试需区分冷启动与稳态。
- 连读 w5 八次，只需一次 256，之后七次各 4。复用节省下层读取，L1 访问本身仍有成本。
- 一个组可满而大部分缓存空闲。默认冲突模式中三个槽一直空着，另一个仍反复替换。
- 十行循环穿过八行 LRU 缓存，会让每次回访都缺失；略超容量也可能破坏全部复用。
- 本模型 L3 覆盖全部 64 字，所以每行首次载入后不再访问 DRAM。真实系统只有在数据仍驻留、未被其他工作或失效驱逐时才有这种保证。
常见错误
- 只用容量解释冲突。更大的缓存可能改变映射，但本例不增容量也能用两路解决；需要看组与映射。
- 把缺失价格当 DRAM 的 200。本课走到 DRAM 要付前面全部检查，共 256。真实硬件可能重叠请求或采用不同计时边界，不能机械相加。
- 只数 load，不数缓存行和复用。同样迭代次数可能覆盖不同数量的行。
- 在默认布局中拿最高位直接做索引。中间位让相邻行分散到不同组；若以高位索引，#0–#3 可能挤到同组。本课规则不排除真实硬件的哈希等索引设计。
- 把整行搬运当无关细节。若相同数据容量只取单字，默认十二个不同字会各自首次缺失，不能只花三次。
- 以为读取结构体一个字段只搬一个字段。传输单位是整行，聚集热点字段、按场景隔离锁与其他共享数据可能改变局部性和一致性流量，应测量收益。
模型范围
真实缓存行通常以字节计，tag 位数随地址宽度和结构变化。标签与数据可并行查，未完成缺失状态结构可重叠请求，硬件预取能减少顺序访问的需求缺失。本课完全不模拟写入：没有脏位、写回/直写或写分配；也没有虚拟地址、TLB、多核一致性。L2、L3 使用全相联 LRU，是教学设定。
可在同一行优先数组上分别测行遍历与列遍历。例如在支持这些事件的 Linux perf 环境：
perf stat -e cycles,L1-dcache-loads,L1-dcache-load-misses ./walk row
perf stat -e cycles,L1-dcache-loads,L1-dcache-load-misses ./walk col
对比周期、load 和缺失计数，实际差异受编译结果和机器影响。macOS 可使用 xctrace record --template 'CPU Counters'，具体模板和事件取决于平台；valgrind --tool=cachegrind --cache-sim=yes 在支持的平台上无需硬件计数器即可做模拟分析，但执行开销较大。工具可用性不能跨平台一概而论。