5.1 缓存、局部性与映射
处理器执行指令的节奏远快于访问主存。多级缓存用层次结构缩小这个速度缺口；典型层级越靠近 CPU 核心，容量越小、访问延迟越低。程序的访问模式将决定这套层级能否真正发挥作用。
单周期数据通路把 instruction memory 和 data memory 画成固定延迟方块。真实处理器面对的是分层存储系统。本篇先理解局部性、cache line、组相联和写策略；多核共享进入缓存一致性与伪共享。
处理器等的不是“内存”这一种东西
ALU 很快算出地址，数据却不一定立刻返回。寄存器、L1、L2、last-level cache、DRAM 与持久存储的容量、延迟、带宽和成本各不相同。普通 load 访问地址 X 时，可能命中某级 cache 或到达 DRAM；寄存器操作数由指令直接指定，寄存器不是 load 自动搜索的一层 cache。SSD 上的数据通常经 I/O 或缺页处理进入内存，不是 cache miss 后由 CPU 无缝继续查询的下一层。
一个典型而非强制的层次是：
寄存器
↓
每核 L1 instruction / data cache
↓
每核或共享的中级 cache
↓
共享 last-level cache
↓
DRAM
↓
SSD / 其他持久存储越靠近执行单元，存储通常越小、访问延迟越低、单位容量成本越高。具体层数、大小、关联度、包含关系和延迟随处理器型号变化，不能把一张产品参数表当作通用定律。
也不是越向外的 cache 就一定包含内层的全部缓存块。inclusive 通常指外层包含受其覆盖的内层块；exclusive 尽量避免这些层重复持有块，non-inclusive/non-exclusive 不保证这两种关系。替换策略还可能考虑一致性目录和服务质量。软件优化前应先确认目标平台。
缓存押注程序具有局部性
缓存以近期访问预测未来访问：
- 时间局部性：刚访问的数据很快再次使用；
- 空间局部性：刚访问地址附近的数据很快被使用。
循环计数器常留在寄存器而不一定反复访问 L1，所以不能用它简单证明 cache 的时间局部性。更合适的例子是反复查询一个能装入 cache 的表，或在一个小工作集上执行多轮计算。
C 的二维数组按行连续存储。下面是函数片段，要求支持可变长度数组参数的 C17 实现、rows/columns 均为正、matrix 指向完整数组，且两种遍历顺序的每个中间和都能由 int64_t 表示。矩阵很大时，行优先与列优先形成不同地址序列：
#include <stddef.h>
#include <stdint.h>
static int64_t sum_row_major(size_t rows, size_t columns,
const int matrix[rows][columns]) {
int64_t sum = 0;
for (size_t row = 0; row < rows; row++) {
for (size_t column = 0; column < columns; column++) {
sum += matrix[row][column];
}
}
return sum;
}
static int64_t sum_column_major(size_t rows, size_t columns,
const int matrix[rows][columns]) {
int64_t sum = 0;
for (size_t column = 0; column < columns; column++) {
for (size_t row = 0; row < rows; row++) {
sum += matrix[row][column];
}
}
return sum;
}行优先通常更好利用相邻元素已被带入的 line，也更容易被硬件预取器识别。但速度差不是固定的“10 倍”：矩阵大小、列数形成的步长、cache/TLB 容量、编译器向量化和硬件预取都会改变结果。小矩阵全部驻留 cache 时，两者甚至可能接近。
局部性是地址访问序列的性质，不是数据结构名字的判决。数组通常连续，链表节点可能分散；arena 分配的紧凑链表可能优于装着巨大冷字段的数组。选布局前应观察真正的热字段和访问方式。
cache line 是传输与一致性的颗粒
cache 通常不按单个 byte 填充，而按固定大小的 block/cache line 传送。许多当代 x86-64 与 AArch64 处理器使用 64-byte line，但这不是所有架构的语言级保证。代码若依赖 line size，应通过目标文档、系统查询接口或部署配置获得，而不是把 64 写成宇宙常量。
假设 line size 为 64 byte，读取 0x1001 发生 miss 时，cache 可能取得对齐范围：
0x1000 ... 0x103F随后读取 0x103F 有机会命中同一 line，0x1040 属于下一 line。这里只说“有机会”，因为该 line 也可能被替换、失效，或访问使用特殊 cache policy。
对象跨 line 时，一次逻辑访问可能需要两次 line 查找。对齐可以控制起始位置，却不自动保证对象大小、数组 stride 或字段分组符合预期。C 中还要区分语言允许的 alignment 与硬件 cache 几何。
地址怎样找到候选位置
在简单的物理地址、模运算索引模型中，可把地址拆为：
| tag | set index | line offset |若 line size 是 B byte、cache 有 S 个 set：
block_number = address / B
set_index = block_number mod S
tag = block_number / S
offset = address mod B这里的除法取整数商。当 B 与 S 是 2 的幂时，这些操作对应固定 bit 字段。实际处理器可能使用虚拟索引、物理 tag 或哈希选择 cache slice/set，下面的简单模运算不能直接证明任意硬件地址冲突。
以 32 KiB、64-byte line、8-way cache 为例：
line 数 = 32768 / 64 = 512
set 数 = 512 / 8 = 64
offset = 6 bit
index = 6 bit相差 64 sets × 64 bytes = 4096 bytes 的 block 会映射到同一 set。一个 set 只有 8 个 way；若工作集反复访问 9 个映射到同一 set 的 line，替换策略可能造成严重冲突。这里的 4096 只适用于这组示例参数。
tag 用来确认候选 way 中保存的是不是目标 block。valid bit 区分有效副本与从未填充或已失效的槽位，write-back cache 还需要 dirty 状态。
直接映射、组相联与全相联
| 组织 | 每个 block 的候选位置 | 优点 | 代价 |
|---|---|---|---|
| 直接映射 | 一个 set 中唯一 way | 查找简单 | 容易冲突 |
| N-way 组相联 | 指定 set 的 N 个 way | 冲突与查找成本折中 | 并行比较多个 tag |
| 全相联 | 任意 line | 没有 set 冲突 | 比较/替换成本随容量增大 |
全相联减少的是 conflict miss，不会消除 compulsory miss 或 capacity miss。某些小型 TLB、victim cache 等结构可高度相联，但不能笼统说“TLB 都是全相联”。
N-way cache 需要在 set 内选择 victim。真正 LRU 随 way 数增长会变复杂，硬件常采用 pseudo-LRU、random、RRIP 或自适应策略。仅凭“最近最少使用”不能精确预测一颗现代 CPU 的替换结果。
四类 miss 帮助定位原因
先忽略预取和一致性失效，经典 3C 模型包括：
- compulsory/cold miss：第一次访问某个 block；
- capacity miss：工作集超过 cache 可用容量；
- conflict miss：关联度有限，多个活跃 block 竞争同一 set。
多核系统还会出现 coherence miss：另一个 agent 的写入使本核副本失效。预取也会改变观察结果：它可能提前把 line 带入，也可能污染 cache、抢占带宽。
分类的价值在于选择方案。扩大容量不能直接解决纯粹的 coherence bouncing，提高关联度也不消除首次填充的需要；预取则可能提前完成填充，让第一次需求访问命中。
一个可执行的组相联模拟器
下面的 Python 模型采用精确 LRU，输入是整数几何参数和非负整数 byte 地址；每次 access 只查询地址所在的一条 line，不模拟跨 line 操作、预取、写回或一致性。它不是某颗 CPU 的周期精确模拟器。
from collections import OrderedDict
class SetAssociativeCache:
def __init__(self, size_bytes: int, line_bytes: int, ways: int):
if any(not isinstance(v, int) or isinstance(v, bool)
for v in (size_bytes, line_bytes, ways)):
raise TypeError("cache geometry must use integers")
if min(size_bytes, line_bytes, ways) <= 0:
raise ValueError("cache geometry must be positive")
denominator = line_bytes * ways
if size_bytes % denominator != 0:
raise ValueError("size must contain a whole number of sets")
self.line_bytes = line_bytes
self.sets = size_bytes // denominator
self.ways = ways
self.contents = [OrderedDict() for _ in range(self.sets)]
def access(self, address: int) -> bool:
if not isinstance(address, int) or isinstance(address, bool):
raise TypeError("address must be an integer")
if address < 0:
raise ValueError("address must be non-negative")
block = address // self.line_bytes
set_index = block % self.sets
tag = block // self.sets
entries = self.contents[set_index]
hit = tag in entries
if hit:
entries.move_to_end(tag)
else:
if len(entries) == self.ways:
entries.popitem(last=False)
entries[tag] = None
return hit
cache = SetAssociativeCache(32 * 1024, 64, 8)
same_set = [index * 4096 for index in range(9)]
assert not cache.access(same_set[0])
assert cache.access(same_set[0])
for address in same_set[1:]:
assert not cache.access(address)
assert not cache.access(same_set[0]) # 第九个同组 block 淘汰了最旧项这个结论依赖模型的精确 LRU。换成真实硬件的 pseudo-LRU，具体 victim 可能不同，但“超过 way 数会制造同组压力”仍成立。
写回时机与分配策略是两组问题
CPU store 命中 cache 时，常见更新策略是：
- write-through：更新 cache 的同时把写传播到下一层；
- write-back：只更新当前 cache 并标记 dirty，替换或一致性要求时再向下传播。
write-through 不等于每条指令都同步等待 DRAM。store buffer、写合并和下层 cache 可以吸收延迟；多核仍然需要 coherence，其他核也不能绕过协议“直接看内存”。
write-back 减少对下层的重复写，但 dirty line 的替换更昂贵，并增加状态管理。断电时 dirty cache 并不会靠一个通用“主板电容承诺”可靠刷到 DRAM；普通 DRAM 本身也易失。持久性需要存储系统、flush/fence、控制器和硬件平台共同提供明确保证。
发生 write miss 时还有一条正交选择：
- write allocate：在当前 cache 分配目标 line，并取得所需数据/写权限后修改；整条覆盖等优化可能省去旧数据读取；
- no-write-allocate/write-around：让写向下层传播，不把 line 分配进当前 cache。
write-back 常与 write allocate 搭配，write-through 常与 no-write-allocate 搭配，但这不是逻辑必然。non-temporal store 是另一类提示/指令语义，可能使用 write-combining 路径并减少 cache 污染，不应简单叫作“write-through”或“直接写 DRAM”。
AMAT 把命中率换算成代价
单层简化模型的 average memory access time 是：
AMAT = hit_time + miss_rate × miss_penalty若 L1 hit time 为 1 ns、miss rate 为 5%、L1 miss 后的平均额外代价为 12 ns：
AMAT = 1 + 0.05 × 12 = 1.6 ns多层层次可递归展开：
AMAT_L1 = hit_L1 + miss_L1 × AMAT_L2_miss_path实际性能还受 memory-level parallelism、乱序隐藏延迟、带宽饱和、预取准确率和队列拥塞影响。AMAT 是定位量级的模型，不是直接预测程序运行时间的完整方程。
数据布局需要与访问集合一起看
AoS（array of structures）把一个对象的字段放在一起，适合经常消费完整对象；SoA（structure of arrays）把同类字段连续排列，适合只扫描少数字段、向量化或分列压缩。
struct Particle {
float x, y, z;
float vx, vy, vz;
float mass;
int type;
};
struct ParticlesSoA {
float *x, *y, *z;
float *vx, *vy, *vz;
float *mass;
int *type;
};SoA 不是无条件更快：它增加指针和分配管理，多字段联合访问可能要同时维持更多流。AoSoA（按 SIMD/cache 友好块组织结构数组）常是中间方案。先列出热循环实际读取的字段，再决定布局。
矩阵乘法的 tiling 也是同一思想：让 A/B 的子块在被替换前重复使用。block size 不能固定照抄 32；元素大小、cache 容量、关联度、SIMD kernel 和多线程共享都会影响合适值。
如何做可信的 cache 实验
“重复读取同一个地址”的基准只能测到编译器、load forwarding 或 L1 热数据，不能靠另一个远地址就强制产生 DRAM 访问。可靠实验至少要考虑：
- 测更外层的访问延迟时，构造超出目标内层容量的工作集，并用依赖链限制并行隐藏延迟；测带宽则应有足够独立访问，两类实验不能共用这一要求；
- 预热、重复多轮，报告分布而非一次数字；
- 防止编译器消除工作，但不要让计时与循环开销支配结果；
- 固定 CPU affinity，记录频率、NUMA 节点和系统负载；
- 区分 latency 与 bandwidth；
- 使用目标平台的性能计数器验证 cache miss，而不是只看墙钟时间。
perf 事件名称和含义随 CPU/内核变化。先用 perf list 查看支持项，再解释 multiplexing、权限和采样误差。
动手分析地址序列
- 对 32 KiB、64-byte、8-way cache，拆解地址
0x12345678的 offset、set 与 tag。 - 修改 Python 模型，对同一 trace 比较 1-way、2-way 与 8-way miss 数。
- 构造 compulsory、capacity、conflict 三类 trace，并解释为什么某项优化只影响其中一类。
- 为一次行优先/列优先实验写出工作集大小和步长，预测 cache 与 TLB 行为。
- 给 AoS、SoA、AoSoA 各写一个更适合它的访问场景。
- 用二级 AMAT 模型计算 L1/L2/DRAM 参数变化的影响，再说明模型忽略了哪些并行性。
多核让同一 line 出现在不同地方
单核 cache 只需维持层级内部的数据正确性。多个核心各有私有 cache 后，同一物理 line 可能出现多个副本，写入必须协调所有者。下一篇进入缓存一致性与伪共享，并区分 coherence、原子操作和语言内存模型。