极客教程

Appearance

共 2,360 字预计阅读约 8 分钟

L1 miss 连锁反应 —— 一次 D-Cache 未命中的完整代价解剖 ​

本篇是数据冒险拆分的miss 连锁反应篇：把前推网络解决不了的场景一次讲透——L1 D-Cache miss 之后 200+ 拍里，硬件各部件依次发生什么（load 卡在流水线 → 保留站 tag 监控 → 后续 µop 连锁 stall → ROB 对头阻塞），以及 MLP（内存级并行） 如何用多个独立 load 填满 miss 等待窗口。这是理解"为什么链表遍历慢、数组遍历快"的微架构根。前提：RAW 寄存器域（ALU→ALU 前推）见 RAW 篇，访存域（Load→Use/Store→Load）见 访存 RAW 篇，假依赖见假依赖篇。

一、前推的边界：什么 RAW 前推救不了 ​

前推网络只在流水线内部（最近 1~2 条）截胡数据。以下场景超出前推能力，只能靠乱序执行 + 保留站等待：

场景数据何时可用前推能做什么真正靠什么
ALU→ALUEX 级结束，1 拍✅ 直接旁路前推本身
Load→Use（L1 hit）MEM 级结束，4~5 拍⚠️ 只能减 1 拍（跳过 PRF 读）LSU 流水线 + 前推
Load→Use（L2 hit）+12 拍❌ 够不着保留站 tag 监控等待
Load→Use（L3 hit）+40 拍❌ 够不着同上
Load→Use（DDR）+200+ 拍❌ 够不着同上 + MLP 补偿
FMA→Use4~5 拍（深流水线）❌ 输出拍太晚保留站等待
FP 除法→Use20~40 拍（迭代近似）❌保留站等待
Store→Load~3~5 拍（SB forwarding）❌ 不在前推网络SB 地址比对

规律：前推只覆盖"数据还在流水线内、且距离不超过 1~2 条"的 RAW。数据一旦需要离开流水线（去缓存、去 DRAM）或延迟超过流水线深度，前推就无能为力——只能靠保留站把消费者挂起、让其他 µop 先执行（乱序执行的核心价值），实在不行就 ROB 对头阻塞。

二、L1 D-Cache miss 的连锁反应 ​

一次 L1 miss，牵动的是从 load µop 到整个乱序窗口的一系列连锁反应。下面这张 14 拍窗口图是全篇的心脏，先把各部件时间轴铺开，再逐段解剖。

2.1 14 拍时间轴全景 ​

L1 D-Cache miss：14 拍连锁反应全景

图上最值得盯的三条线：

  1. µop₁（LSU 线，拍3~11）：从 SB 查询、D-Cache 查询、miss、发 L2 请求、等 L2 返回——整整 8 拍卡在 LSU 里。
  2. µop₂（RS 线，拍6~12）：依赖 µop₁，从入 RS 起就挂起，直到拍11 µop₁ 数据可用才被唤醒、拍12 才发射。
  3. µop₃~µop₆（EU 线，拍8~11）：不依赖 µop₁ 的 µop 照常发射——乱序执行在 miss 窗口里继续填坑，这是 MLP 能救性能的硬件基础。

2.2 四阶段解剖 ​

把 14 拍拆成四个阶段，看每一拍谁在做什么：

阶段一：load µop 自身卡在 LSU（拍1~5）

  • 拍1：µop₁ 从 RS 发射到 AGU
  • 拍2：AGU 算地址 + TLB 翻译
  • 拍3：SB 查询（无匹配）→ 发送 D-Cache 请求
  • 拍4：D-Cache 内部查询（index 选 set + tag 比对）
  • 拍5：miss 判定——LSU 发出 L2 请求，µop₁ 留在 LSU 里等待返回

注意：miss 本身只需要 1 拍判定，但 µop₁ 的"结果"要等数据回来才算完成，所以它在 LSU/队列里挂着，不能释放——这是连锁反应的起点。

阶段二：依赖 µop 的连锁挂起（拍6~7）

  • 拍6：µop₂（依赖 µop₁ 的目的 PR）到达 RS，tag 匹配失败 → 挂起
  • 拍7：µop₂ 调度器反复尝试发射，源未就绪 → 持续不可发射

阶段三：不依赖 µop 的补偿执行（拍8~11）

  • 拍8~11：µop₃、µop₄、µop₅、µop₆（不依赖 µop₁）陆续被调度发射执行
  • 拍10：L2 命中返回，数据回填 L1，µop₁ 被唤醒
  • 拍11：µop₁ 数据写回 PRF 并广播 tag，µop₂ 被唤醒、发射

阶段四：依赖链收尾（拍12~13）

  • 拍12：µop₂ 执行
  • 拍13：µop₂ 写回，槽位释放

2.3 连锁反应的放大：ROB 对头阻塞 ​

如果 µop₂ 是 load→use 依赖链上的最后一个消费者，且它还没退休，那么 ROB 的对头（oldest entry）可能是 µop₁ 或 µop₂——ROB 头部的 µop 不完成，后面所有 µop 都无法退休。极端情况：

  • 依赖链上全是 load→use（如链表遍历 p = p->next）
  • 每个 load 都 miss（链表节点分散在内存各处）
  • µop₁ miss → µop₂ 挂起 → µop₃（无关 µop）执行完但无法退休（ROB 对头没完成）→ 流水线挤满

ROB 对头阻塞的判定信号：ROB 满 + 对头 miss → 整个流水线停摆，IPC 断崖。这就是为什么内存密集的链表遍历 IPC 只有 0.1~0.2，而顺序数组遍历能到 1+——后者 L1 命中率高、依赖链短。

这也是"缓存友好代码"的微架构根：顺序访问让 L1 命中率高（MLP 天然高）、依赖链短（RAW 少）、ROB 不阻塞。详见 cache-friendly-code。

2.4 唯一补偿：MLP（Memory-Level Parallelism，内存级并行） ​

miss 窗口（拍5~10）里，不依赖 µop₁ 的 µop 照常执行——这就是乱序执行给访存延迟的补偿。如果程序在等第一个 load 的同时，还有第二个独立 load 可以发出去，两个 miss 并行进行：

bash
循环体（独立数组访问，可并行）：
  load a[i]      ; miss 窗口里发出
  load b[i]      ; 独立！miss 窗口里也发出 → 两个 miss 并行
  load c[i]      ; 独立！三个 miss 并行
  x = a[i] + b[i] + c[i]   ; 最后才用

总延迟 ≈ 1 个 miss 的延迟（200拍） + 最后一级运算
        ≠ 3 个 miss 串行（600拍）

硬件层面支撑 MLP 的机制：多个 load miss 可以同时在 MSHR（Miss Status Holding Register）里登记，各自独立等待内存返回——现代 x86 每个核支持几十个 in-flight miss。只要依赖链不强制串行，MLP 就能把"等内存"的时间重叠掉。

MLP 的代价：in-flight miss 越多，占用的 MSHR/LSQ 资源越多；miss 太多挤爆 MSHR → 新的 miss 无法登记 → 排队。所以"完全串行的依赖链"（MLP=1）和"无限并行的 miss 洪流"（挤爆 MSHR）是两个极端，性能都差。中间地带（几个独立 load 并行）才是最佳。

2.5 极端情况：完全串行的 load 依赖链 ​

最坏情况——每个 load 都依赖前一个 load 的结果（链表遍历、指针追逐）：

bash
节点地址    0x1000 → 0x5000 → 0x8000 → 0x2000 → ...
load [0x1000] miss(200拍) → 返回 0x5000
load [0x5000] miss(200拍) → 返回 0x8000
load [0x8000] miss(200拍) → ...
每个节点都要 200 拍，MLP 救不了（依赖强制串行）
1M 节点的链表遍历 ≈ 1M × 200 拍 = 2 亿拍

对比顺序数组：

bash
数组 arr[0..1M]（连续内存）：
load arr[0] miss(200拍)  ← 只有第一个 miss
load arr[1..] 全部 L1 hit（prefetch 已把相邻行拉进来）
load arr[0] miss 窗口里，其他 63 个 load 全在 L1 hit
1M 节点数组遍历 ≈ 200 拍 + 1M × 1 拍（L1 hit）

结论：链表 vs 数组的性能差不是"链表的节点在哪"决定的，而是依赖链的 MLP 决定的——链表强制 MLP=1，数组天然 MLP≈64（一条 cache line 有 64 字节/8 字节指针 = 8 个元素连续命中）。

2.6 什么代码最容易被连锁反应盯上 ​

三个高发场景，本质都是"依赖链上叠加 miss"：

  1. 链表/树的遍历：p = p->next 这种指针追逐，每次 load 的地址来自上一次 load 的结果——miss 全部串行，MLP=1，200 拍 × 节点数。
  2. 稀疏访问的哈希表：桶内的链表节点散落在内存各处，h = hash(k) 拿到桶之后还要再去 chase 节点，命中和 miss 交错，连锁反应断断续续但始终存在。
  3. 深拷贝/序列化的随机访问：memcpy 是顺序的（硬件 prefetch 兜底），但按字段到处挑着读的结构体拷贝访问模式乱，miss 率高且依赖链无处不在。

共同信号：perf stat 里 stalled-cycles-backend 占比高、cache-misses/cache-references 命中率掉到 90% 以下、IPC 明显低于 1。遇到这种组合，先别急着怪乱序执行——是 miss 连锁在拖后腿。改数据结构布局（SoA/顺序化）比调任何流水线参数都有效，具体手法见 cache-friendly-code。

2.7 用 perf 验证 miss 的代价 ​

指标含义怎么用
cache-missesL1 D-Cache miss 次数perf stat -e cache-misses ./app
cache-referencesL1 D-Cache 访问次数和 misses 一起算命中率
cycles总周期除以 miss 数 = 每次 miss 的周期成本
stalled-cycles-frontend/backend前/后端停顿miss 造成的后端停顿
bash
perf stat -e task-clock,cycles,cache-references,cache-misses,stalled-cycles-backend ./app
# 关注 cache-misses / cache-references 的命中率，和 stalled-cycles-backend 占比

更深入的 perf 案例（L1 miss 主导的 IPC 拖累）见 perf 案例分析。地址翻译侧的 miss（TLB miss → page walk）与缓存 miss 同理，详见 tlb。

三、一句话总结 ​

一次 L1 miss，从 load 卡在 LSU（1 拍判定）开始，连锁到依赖 µop 挂起（保留站 tag 匹配失败）、再到无关 µop 补偿执行（乱序执行的价值）、最坏 ROB 对头阻塞（整个流水线停摆）——总代价 200+ 拍，是 L1 hit 的 40~50 倍。 唯一补偿是 MLP：多个独立 load 的 miss 并行等待（MSHR 登记），把"等内存"的时间重叠。所以程序性能的分水岭不是"访问了多少数据"，而是依赖链上每个 load 的 miss 能不能并行——数组天然 MLP≈64，链表强制 MLP=1，这就是两者差一个数量级的微架构根。