1 / 4概念
Misses, Prefetch and Blocking
未命中无法消除,只能分类、隐藏或绕开。分类告诉你该加容量还是加相联度,非阻塞缓存用并发把延迟摊薄,预取把未来访问提前,分块则把工作集切到某一层装得下。四种手段针对同一件事:让核少等。
1 概念
1.1 一句话定义
未命中是缓存中没有所需块,代价是从下级取回。预取是在程序访问之前提前把块搬上来。阻塞式缓存一次只允许一个未完成未命中,非阻塞式用未命中状态寄存器允许多个同时在途。
1.2 它解决什么问题
- 定位根因:未命中分为强制、容量、冲突三类,手段完全不同。
- 隐藏延迟:块已经在路上时,核可以继续执行别的指令。
- 提前搬运:预取把未来的未命中转成当前的命中。
- 压小工作集:分块让每一层的访问都落在容量之内。
1.3 不属于本页的内容
| 主题 | 去哪 |
|---|---|
| 替换算法、写回与直写 | hw-replacement-write |
| 相联度、组索引、行大小 | hw-cache-organization |
| 多级之间的包含与互斥 | hw-multilevel-inclusion |
| 缺页与页表遍历 | hw-paging-page-tables、hw-page-fault-working-set |
| 一致性失效造成的未命中 | hw-cache-coherence |
1.4 关键术语
| 术语 | 含义 | 容易混淆的点 |
|---|---|---|
| 强制未命中 | 块第一次被访问 | 也叫冷未命中 |
| 容量未命中 | 全相联下仍装不下 | 不是冲突 |
| 冲突未命中 | 组内被其他块挤掉 | 不是容量不足 |
| 一致未命中 | 其他核的写使本副本失效 | 第四类 C |
| MSHR | 记录未完成未命中的表项 | 不是 TLB |
| MLP | 内存级并行,同时在途的请求数 | 不是线程数 |
| 预取准确率 | 预取中有用的比例 | 不是覆盖率 |
| 分块 | 把工作集切成容量大小的块 | 英文也叫 blocking |
2 机制
2.1 心智模型
减少未命中靠容量与相联,隐藏未命中靠并发与预取,绕开未命中靠分块。 三者可以叠加,但都受带宽上限约束:预取与分块只是把等待挪到更早或更少的位置。
2.2 机制拆解
- 三 C 判定:先用全相联 LRU 模拟。首访问是强制未命中,全相联仍装不下是容量未命中,其余是冲突未命中。
- 第四类 C:多核环境下,其他核的写会让本地副本失效,产生一致未命中。
- 阻塞与非阻塞:阻塞式一次只有一个未完成未命中,处理器必须停顿;非阻塞式用 MSHR 支持命中在未命中之下,也支持多个未命中同时进行。
- MLP 上限:MSHR 数量、载入队列深度与乱序窗口共同决定并发请求数。
- 硬件预取:顺序预取器取下一行,跨步预取器按固定步长取,流预取器跟踪多条流,通常预取到 L2。
- 软件预取:
__builtin_prefetch(addr, rw, locality)与prefetcht0到prefetchnta,距离约为内存延迟除以一次迭代的时间。 - 分块:把循环切成 B 大小的块,使三个子矩阵同时驻留某级缓存,B 由容量与行大小决定。
- 预取污染:预取占用缓存与带宽,过量预取会挤掉真正要用的块。
2.3 完整枚举
| 未命中类型 | 判据 | 可否消除 | 主要手段 |
|---|---|---|---|
| 强制 | 块第一次被访问 | 不可消除 | 预取、增大行、流式搬运 |
| 容量 | 全相联下仍被淘汰 | 部分可缓解 | 加容量、分块、压缩 |
| 冲突 | 组内被其他块挤掉 | 可消除 | 加相联度、改布局、页着色 |
| 一致 | 其他核写导致失效 | 可减少 | 减少共享写、按行分离 |
| 预取方式 | 触发依据 | 覆盖率 | 主要风险 |
|---|---|---|---|
| 下一行 | 顺序访问 | 高 | 跨页或跳转后失效 |
| 跨步 | 固定步长 | 中 | 步长变化即失效 |
| 软件预取 | 编译器或手工插入 | 精确 | 距离不当、可移植性差 |
| 预取到末级 | 硬件启发式 | 中 | 污染共享缓存 |
2.4 关键数字与复杂度
| 指标 | 量级 | 说明 |
|---|---|---|
| 未命中代价 | 200–400 个周期 | 到 DRAM |
| MSHR 表项 | 8–64 | 决定最大 MLP |
| 单核并发请求 | 8–16 | 受载入队列限制 |
| 单流带宽 | 约 0.7 GB/s | 64 B 除以 90 ns |
| 预取距离 | 约 100–200 次迭代 | 按延迟换算 |
| 预取准确率目标 | 80% 以上 | 低于此值多为浪费 |
分块因子的约束是三个 B × B 双精度子矩阵要同时驻留:3 × B² × 8 ≤ 容量。1 MB 时 B 约 209,取 128 到 192 比较稳妥。
3 实践
3.1 最小示例
/* 分块矩阵乘:三块 B×B 子矩阵同时驻留 L2,B 取 128。 */
#define B 128
for (int ii = 0; ii < n; ii += B)
for (int jj = 0; jj < n; jj += B)
for (int kk = 0; kk < n; kk += B)
for (int i = ii; i < ii + B; i++)
for (int k = kk; k < kk + B; k++) {
__builtin_prefetch(&a[i][k + 16], 0, 3); /* 提前约 16 次迭代 */
for (int j = jj; j < jj + B; j++)
c[i][j] += a[i][k] * b[k][j];
}
分块解决容量未命中,预取解决剩余的强制未命中。两者叠加后,未命中率不再随矩阵规模上升。
3.2 常用操作与参数
| 操作 | 命令 | 说明 |
|---|---|---|
| 看分级未命中 | perf stat -e L1-dcache-load-misses,LLC-load-misses | 定位未命中层级 |
| 逐访存归因 | perf mem record、perf mem report | 未命中落在哪条指令 |
| 看跨核失效 | perf c2c record、perf c2c report | 一致未命中与伪共享 |
| 模拟 3C | valgrind --tool=cachegrind | 分容量与冲突统计 |
| 看容量与页 | getconf LEVEL2_CACHE_SIZE、getconf PAGE_SIZE | 分块上限与跨页判断 |
3.3 标准流程
- 用
perf stat取分级未命中,先确认瓶颈在 L1、L2 还是末级。 - 用
cachegrind模拟全相联,把未命中分成强制、容量、冲突。 - 按类型选手段:预取、分块或改相联度。
- 引入预取后复测准确率,确认没有明显污染。
3.4 与相邻技术的组合
- 分块与 TLB:块太大时数据跨页,TLB 未命中会抵消分块收益。
- 预取与 NUMA:跨节点预取会同时消耗链路带宽。
- 非阻塞与乱序:乱序窗口越深,MSHR 越容易成为瓶颈。
3.5 选型维度
| 手段 | 针对的未命中 | 典型收益 | 代价 |
|---|---|---|---|
| 加容量 | 容量 | 未命中率下降 | 面积、功耗 |
| 加相联度 | 冲突 | 冲突未命中下降 | 命中时间上升 |
| 硬件预取 | 强制与顺序 | 延迟被隐藏 | 污染、带宽 |
| 软件预取 | 强制 | 精确 | 需手工调距离 |
| 分块 | 容量 | 收益最大 | 需改代码 |
3.6 决策规则
- 强制未命中占主导时,宜用预取或流式搬运。
- 容量未命中占主导时,宜分块,而不是加相联度。
- 带宽已经饱和时,预取只会加剧争用,应减少访问量。
3.7 替代方案对比
| 方案 | 优势 | 代价 | 适用 |
|---|---|---|---|
| 硬件预取 | 全自动 | 不可控、污染 | 通用负载 |
| 软件预取 | 精确 | 需调距离、不可移植 | 已知循环 |
| 分块 | 收益大、可预测 | 改代码、受 TLB 限制 | 稠密线性代数 |
| 非阻塞缓存 | 提高吞吐 | 面积与验证 | 高性能核 |
3.8 何时不该用
- 数据只访问一次时,预取与分块都没有重用可换。
- 跨页边界附近不要盲目软件预取,未映射页会带来异常。
4 边界
4.1 典型故障
| 症状 | 根因 | 处理 |
|---|---|---|
| 预取后反而变慢 | 污染与带宽浪费 | 降距离、只预取到 L2 |
| 未命中率不降 | 预取太晚或步长不匹配 | 调距离、换预取器 |
| 并发上不去 | MSHR 或载入队列满 | 改循环顺序、减少依赖 |
| 分块后仍慢 | 块太大跨页或超容量 | 减 B、加大页 |
4.2 反模式
| 做法 | 后果 | 替代 |
|---|---|---|
| 无条件预取下一行 | 跳转后全是垃圾 | 用跨步或条件预取 |
| 用预取掩盖算法问题 | 带宽被浪费,收益有限 | 先改数据布局 |
| 分块因子照抄他人 | 容量不匹配 | 按实测容量算 B |
4.3 可观测信号
perf stat 的 L1-dcache-load-misses、LLC-load-misses 与 mem_load_retired.l3_miss;perf mem report 的逐指令未命中;perf c2c 的一致未命中;cachegrind 的三类未命中分解;perf stat -e page-faults 的跨页代价。
4.4 安全 / 性能 / 一致性边界
- 推测与预取:预取可能越过权限边界取数,侧信道可利用这种推测行为。
- 带宽共享:预取消耗的带宽与真实访问相同,多租户下会互相挤压。
- 确定性:硬件预取的时机不可控,实时系统难以给出最坏执行时间。