计算机体系结构 · 第10课|ROB、Free List 与投机恢复:结果算完,为什么还不能提交?
2026年10月29日|第2周第3课|约18分钟
第8课解决“如何用物理寄存器区分不同版本”,第9课解决“谁醒来、谁拿到执行端口”。今天处理更难的收尾问题:旧物理寄存器什么时候可以释放?遇到分支误预测或异常,怎样把机器恢复到正确的程序前缀? 特别注意:执行完成、ROB退休、Store进入缓冲和对其他核全局可见,不是同一个事件。
1. 动机:最先算完的,可能最不该提交(2分钟)
设按程序顺序有四条指令:
I1: DIV R1, R2, R3 # 很慢,或可能除零异常
I2: ADD R4, R5, R6 # 独立,较快
I3: ADD R7, R4, R8 # 依赖I2
I4: STORE [addr], R7 # 如果I1异常,这条绝不能留下不可回滚的架构效果
乱序执行允许 I2、I3 比 I1 先完成。如果 I1 最终异常,而 I4 已经让内存架构状态不可回滚,那么异常处理器无法看到“恰好执行了 I1 之前所有指令”的状态。ROB(Reorder Buffer)通过按程序顺序退休,把乱序执行的结果整理成精确的架构前缀。 这不是要求计算按序,而是要求不可撤销的提交遵守顺序。
flowchart LR
A["Decode / Rename:按序建版本"] --> B["ROB尾部:按序分配条目"]
A --> C["Issue Queue:等待/选择"]
C --> D["执行、写回:可乱序完成"]
D --> E["ROB条目置完成/异常标志"]
B --> F{"ROB头部完成且无异常?"}
E --> F
F -->|是| G["按序退休,更新已提交状态"]
F -->|否| H["等待或异常/恢复"]
G --> I["回收该指令的stale pdst"]
H --> J["冲刷年轻指令,恢复重命名状态"]
这里“已写回物理寄存器”不代表已成为不可撤销架构结果;ROB里的年轻结果仍可被丢弃。
2. 先定义状态与不变量(2分钟)
采用显式物理寄存器重命名的教学模型:
| 符号 | 意义 | 更新时机 |
|---|---|---|
| (\mathrm{RAT}[a]) | 架构寄存器 (a) 当前投机映射到的物理版本 | 按序Rename |
| (\mathrm{AMT}[a]) | 已退休架构状态对应的物理版本;有的实现用提交映射表 | Commit |
| (pdst_i) | 第 (i) 条写目的的新物理寄存器 | Rename分配 |
| (stale_i) | 该条指令重命名前,目的架构名映射的旧物理寄存器 | Rename记录 |
| (\mathrm{Free}) | 可供下一次Rename分配、当前不再需要的物理寄存器集合 | 分配、提交回收、回滚 |
| ROB head/tail | 最老可退休候选/新指令加入位置 | Dispatch/Retire |
最重要的两个不变量:
- RAT 指向“当前已重命名程序前缀中该架构寄存器的最后一个写入版本”;新指令应先读取旧源标签和 stale,再更新目的映射。AMT 则只反映已提交前缀。
- 已退休指令集合始终是程序顺序的一个连续前缀。可撤销的投机结果可以在物理寄存器里,但不能在错误路径上留下不可回滚的架构副作用。
现实中不是所有微架构都用独立 AMT 或在 ROB 保存全部数据;例如 BOOM 允许使用提交映射表快速复位,也可通过 ROB 回滚重命名状态。这是具体实现选择,不是ISA必须规定的硬件结构。
3. 为什么 stale pdst 不能在 Rename 或 Writeback 就释放?(2分钟)
假设初始 R1→P1,老指令 A 已绑定 P1 作为源;年轻指令 B 写 R1,获得新目标 P20,并记录 stale_B=P1:
老A: READ R1 -> 绑定源P1(可能尚在等另一个操作数)
年轻B: WRITE R1 -> 分配P20;stale=P1;RAT[R1]=P20
不能在 B Rename 时释放 P1:A 以后仍需要旧值。如果把 P1 交给另一条新指令覆盖,A 会读到错误版本。
也不能仅因为 B 执行完成就释放 P1:更老消费者可能仍在飞;B 可能随后因更老异常或分支而被取消。在本课的按序退休机制下,当 B 正常退休时,所有更老指令已退休,所有更年轻指令在重命名时也不会错误绑定被覆盖前的旧版本,因此才能安全回收 B 记录的 stale 版本(忽略专门保留寄存器的额外调试/回滚设计)。
分配与回收的简化守恒式是:
[
\begin{aligned}
|\mathrm{Free}{\mathrm{after}}|
=&\,|\mathrm{Free}{\mathrm{before}}|
&-#\mathrm{Allocations}
&+#\mathrm{CommittedStaleReleases}
&+#\mathrm{SquashedAllocationsReturned}.
\end{aligned}
]
三项分别是成功分配新pdst、正常退休释放stale、回滚返还的错误路径新分配;同一物理版本绝不能重复入Free。
注意三项集合必须互斥,不能把同一个物理寄存器回收两次;真实硬件需要跟踪精确所有权,而非只维护一个数字。
4. 完整数值例:重命名、旧值与 Free List(3分钟)
初始 R1→P1、R2→P2、R3→P3,空闲池是 P20…P26,共 7 个。依程序顺序重命名:
| 指令 | 逻辑操作 | 新pdst | stale pdst | Rename之后与之相关的RAT |
|---|---|---|---|---|
| J1 | R1 ← R2+1 | P20 | P1 | R1→P20 |
| J2 | R2 ← R1+2 | P21 | P2 | R2→P21;J2源R1仍指P20 |
| J3 | R1 ← R2+3 | P22 | P20 | R1→P22;J3源R2指P21 |
三个新目的占用三格,所以单看Rename后的Free池为 7−3=4。J3 的 stale 是 P20,不是 P1:因为它覆盖的是 J1 版本。这一点不能通过仅看初始架构映射得到,必须按序追踪 RAT。
假定 J1、J2 已正常退休并释放各自 stale,而 J3 虽执行完成但尚未退休:Free池增回两个物理寄存器;J3 的 P20 仍须保留。请在课后 Lv2 独立完成最终计数,不要因 J3 已算完就提前回收。
这同时说明为什么 ROB 条目通常要保存逻辑目的、stale 版本、完成/异常状态等元数据;只存“计算结果”不够支持资源回收。
5. 分支误预测:Checkpoint恢复的是什么?(3分钟)
把分支 B 放在一批投机写入之前。分支点RAT快照保存当时正确的版本映射;错误路径 I3、I4、I5 可以先执行甚至写回,却不允许最终退休。若预测错误,恢复分支时的映射并取消错误路径,释放那些错误路径新分配的物理目标。
B以前: R1→P20、R2→P2、R3→P3
B以后(预测路径):
I3 写R2 -> P21
I4 写R1 -> P22
I5 写R3 -> P23
B被判误预测:
恢复 R1→P20、R2→P2、R3→P3
丢弃 I3/I4/I5,回收本错误路径分配的P21/P22/P23
保留B以前尚在途的P20
恢复 RAT 不能自动恢复 Free List 的全部分配历史。 一个看似直觉的方案是只复制Free位图;但在存在“检查点后分配、其他合法指令释放、又重新分配”的交错时,单纯旧快照与当前Free集合不一定足以正确回收。BOOM文档明确采用每分支的 Allocation List 跟踪分支之后分配过的寄存器,误预测时据此回收。其他处理器可用ROB逆向回滚、日志或引用计数等,只要满足所有权不变量即可。
反例: 错把分支之前 J1 分配的 P20 也归还 Free 池。恢复后 RAT[R1] 仍指 P20,却同时允许新指令分配并覆盖 P20——同一物理寄存器既是当前有效版本又被标为空闲,直接破坏正确性。
6. 精确异常:错误路径上的异常应不应该发生?(2分钟)
情况 A: 更老指令发生真实架构异常。ROB 不允许它后面的年轻指令退休;当异常成为最老待处理事件时,恢复到精确提交前缀并转异常处理程序。
情况 B: 一条错误预测路径上的年轻 DIV 除零,后来更老分支判定该路径本就不应执行。该DIV的投机异常不得作为正常程序的架构异常报告:它应随错误路径一起被 squash。真正需要处理的异常以正确路径的顺序语义为准。
情况 C: 年轻 Load 因猜测内存依赖发生违例,可以触发重放/流水线恢复,不一定是软件可见的架构异常。处理器内部 retry 与交给OS的页故障必须分开描述。
这里说的“无架构副作用”不等于没有任何微架构痕迹:错误路径访问可能改变Cache或预测器状态。精确异常保证的软件视角与推测执行侧信道安全,是两个不同问题。
7. 两条恢复路径:快照与 ROB rollback(1分钟)
如果维护AMT,发生全流水线冲刷时可将投机RAT恢复为提交映射,代价是额外状态存储与写入。若不维护,可从ROB尾部逆序撤销写入,依次把每条目的 (stale_i) 恢复为RAT中对应逻辑目的;代价是恢复可能需要多个周期。分支独立checkpoint有助于局部误预测的快速恢复。
两者的共同正确性条件不是“用了哪种电路”,而是恢复后所有活跃源标签、映射、Free池和ROB有效条目彼此一致,不能把仍有活跃消费者的物理版本回收。BOOM文档分别说明了提交映射表复位、逐行回滚和分支检查点。
8. 最容易混淆的第四个时刻:Store 全局可见(1分钟)
执行完成 → ROB正常退休 → Store被准许进入/离开提交阶段
↓
Store Buffer等待传播
↓
其他核依内存模型观察到写入
某些乱序处理器允许 Store已按序退休,但仍在Store Buffer中尚未对别的核可见。因此“本核ROB按序退休”不能推出“所有核都按SC观察内存”。第五周会用熟悉的Store Buffering试验系统证明:
初始x=y=0
核0:x=1;r0=y
核1:y=1;r1=x
要分清指令执行、架构退休、写缓冲驻留、全局可见四层,再分析为何某些内存模型允许不同核看到的顺序不等于单一全局SC顺序。今天不提前把第5周课程讲完;这里只建立必要区分。
9. 反例、适用边界与一分钟总结
- 错法一: “RAT不再指P1,所以P1立即空闲。”——旧物理版本仍可能被更老、尚未执行完的消费者使用。
- 错法二: “结果已经写回,所以能提交。”——ROB较老指令可能未完成或异常,不能越过队头提交。
- 错法三: “恢复RAT就完成全部回滚。”——Free池、在途指令、错误路径分配和旁路标签都要一致。
- 错法四: “错误路径有DIV异常,操作系统必须处理。”——更老分支否定该路径时,应取消这个架构异常。
- 错法五: “Store退休就已对所有核可见。”——在允许Store Buffer的模型里,两者可分离。
一句话: RAT 决定当前投机版本,AMT/提交前缀表示已认可的架构状态,ROB决定何时可退休,Free List决定哪些旧版本真能重用,Checkpoint/rollback保证发现走错路后还能恢复。
第11课预告(2026-10-30): Load/Store Queue(LSQ)、内存依赖预测与Store-to-Load Forwarding:为什么内存地址尚未算出时可能需要保守等待或投机执行,以及违反依赖时怎样重放。第5周再系统证明TSO、SC、跨核可见性与缓存一致性,不改变既定课号。
10. 四级测评(总分100;首次不公布答案)
Lv1–Lv3可客观判分,Lv4以完整步骤人工/自评,不伪装为自动证明判分。每题可展开不泄露答案的提示。
Lv1|旧物理版本的生命期(15分 · 单选 · 预计2分钟)
在本课的显式重命名、按序退休模型中,指令B为架构寄存器R1分配新物理寄存器P20,并记录stale=P1。另有更老指令A已绑定P1作为源,尚未完成。下列哪项最严谨?
A. B一完成Rename,就可以回收P1,因为RAT不再指它。
B. B正常退休时,在较老指令均已退休且无需额外保留旧版本的前提下,可回收B记录的stale版本。
C. B写回P20那一刻,无论ROB队头状态如何都必须立即回收P1。
D. 只要出现分支checkpoint,P1自动变成Free。
可选提示(不泄露答案)
明确A的源标签什么时候确定,及哪一事件保证比B更老的消费者不再运行。Lv2|多次覆盖与延期回收的计数(20分 · 数值 · 预计4分钟)
初始 R4→P4、R5→P5、R7→P7,Free List 只有 P40…P48,共9个。依次重命名四条写寄存器指令:
K1: 写R4,分配P40
K2: 写R5,分配P41
K3: 再写R4,分配P42
K4: 写R7,分配P43
之后只有K1、K2正常退休;K3、K4虽已执行完成但尚未退休。没有回滚、额外分配或其他释放。此刻Free List共有几个物理寄存器?只填整数。
可选提示(不泄露答案)
逐步列出每条的stale:它是重命名前相应架构寄存器的当前物理映射,不一定是初始值。再仅对真正退休的指令执行释放。Lv3|Checkpoint、异常与内存可见性边界(25分 · 多选 · 预计5分钟)
下列哪些说法正确?可多选;遵循正文的显式重命名和按序退休模型,Free List与Branch恢复必须保持所有权一致。
A. 只复制分支时的RAT即可处理所有Free List分配、回收、再分配交错,完全不需要其他记录。
B. 误预测恢复应保留分支之前虽尚未退休、但仍属正确路径的有效物理目标版本。
C. 为提高效率,可以让一条年轻指令在更老架构异常尚未处理时不可撤销地退休,稍后清空ROB即可恢复精确异常。
D. 在正常提交、无需额外保留旧值的前提下,覆盖某架构寄存器的指令退休后,可回收其记录的stale pdst。
E. 在允许Store Buffer的实现中,Store可能已从ROB按序退休,却尚未对其他核全局可见。
可选提示(不泄露答案)
分别检查“RAT/Free是否是同一状态”“分支前后谁应保留”“异常时退休前缀”和“本核退休/跨核可见性”。Lv4|误预测恢复、错误路径异常与资源守恒(40分 · 开放推导 · 预计10分钟)
初始 R1→P1、R2→P2、R3→P3,Free Pool仅 P10…P16 七个物理寄存器,旧 P1、P2、P3 不在Free中。按序重命名:
I1: ADD R1 <- R2 + 1 # 分配P10
I2: BRANCH # 预测taken,实际not-taken;在I2之后建立分支快照
I3: MUL R2 <- R1 * 2 # 错误路径,分配P11
I4: ADD R1 <- R2 + 3 # 错误路径,分配P12
I5: DIV R3 <- 10 / 0 # 错误路径,分配P13,可产生投机异常
I2判定误预测时,I1尚未退休。恢复后,从正确路径继续重命名:
I6: ADD R3 <- R1 + R2 # 恢复的Free Pool按编号顺序分配P11
假定I6在I1退休之前完成重命名;之后I1、I2、I6依程序顺序正常退休,期间没有其他指令分配或释放。Free Pool遵守精确所有权原则。
(A,12分) 列出I1、I3、I4、I5各自的pdst与stale,并列出分支快照对应的RAT。注意I3读取R1、I4读取R2时各自绑定的版本。
(B,12分) 误预测后写出RAT的正确恢复值、应回收和不得回收的物理寄存器;解释I5的DIV异常是否应向软件报告。
(C,10分) 按“初始→五条指令重命名(其中分支不分配目的)→squash→I6重命名→I1/I2/I6退休”的时间线,计算每个关键阶段Free寄存器数,写出最终已提交映射。说明I1和I6退休分别释放哪个stale。
(D,6分) 设计一个可机器检查的不变量,能抓住“错误地把P10回收到Free”的bug;再说明分支全快照和按ROB回滚各有一个资源或延迟代价。
可选提示(不泄露答案)
先画出每条指令重命名**之前**的RAT。恢复时保留分支以前的正确路径目的,丢弃分支以后的错误路径新分配。Free计数要分别处理“分配新pdst”“squash回收”“正常退休释放stale”,不要把未退休的stale提前释放。作答方式: 可回复“Lv1: …;Lv2: …;Lv3: …;Lv4: A/B/C/D 的步骤”。将逐题按15/20/25/40分评分,指出具体状态或证明漏洞。总分≥80按既定日历继续;60–79补充针对性例题;<60重点回顾后再练。补练不改变下一自然日的课号。
参考阅读(背景、非本课全部案例的硬件承诺): BOOM Rename Stage;BOOM Reorder Buffer;BOOM Pipeline。