计算机体系结构 · 第14课
第2周复盘:一条指令从取指到退休,究竟经历了什么?
2026年11月2日|第2周第7节·综合复盘|约18分钟
第8—13课分别研究了寄存器重命名、Tomasulo动态调度、ROB与精确异常、LSQ中的访存投机、分支预测及其历史恢复,以及Fetch/ROB/LQ等共同构成的吞吐限制。今天不重复逐个介绍组件,而是把它们作为同一台处理器的协作协议,完整分析一个「正确路径Store → 提前转发的Load → 分支误预测 → 错误路径清除 → 正确路径退休」实例。
学习目标:能沿程序年龄追踪物理源和目的;区分执行完成、写回、退休与跨核可见;说清三种回滚状态(RAT、Free List、GHR);从数值Trace判断为何某种更快的乱序执行仍保持架构正确。
一、为什么需要这一节复盘?(约1分钟)
一条年轻ADD可以先于较老的长延迟Load完成,但不能越过未完成的老指令产生不可撤销的架构提交。一条Load可以从未全局可见的较老Store取得数据,但不能因此断言其他核也已看见该写入。一条分支可以先预测方向并更新GHR,但随后如果发现猜错,必须同时恢复寄存器状态、预测历史和相关资源。
“快”来自提前执行,“正确”来自所有权、依赖检查与提交/恢复边界。
flowchart TD
F["Fetch + BHT/BTB/GHR"] --> R["Decode / Rename"]
R --> M["RAT读源、分配pdst、记stale"]
M --> Q["Issue Queue与LSQ"]
Q --> X["执行与Writeback:可以乱序"]
X --> ROB["ROB记录完成/异常与程序年龄"]
ROB --> C{"ROB头可正常退休?"}
C -->|是| A["确认架构前缀,释放安全stale"]
C -->|未完成| W["阻塞后续退休,可能反压前端"]
C -->|异常/错误路径| S["Squash/Replay恢复"]
S --> R
S -. 恢复GHR与正确PC .-> F
A --> SB["已提交Store可能继续驻留Store Buffer"]
SB --> V["遵守内存模型的对外可见"]
二、统一符号与模型假设(约2分钟)
为避免把ISA规定误当成某台芯片的具体实现,以下采用一个明确的教学微架构。
- 一个核心,5个架构寄存器R1—R5;初始R1=4、R2=3、R3=R4=R5=0。
- 已提交初始映射:R1→P1、R2→P2、R3→P3、R4→P4、R5→P5。Free List初始为{P20,P21,P22,P23,P24,P25}。
- 物理寄存器文件保留投机值与已提交值;RAT是当前投机映射,已提交映射另行记录(如AMT或可回滚的ROB)。
- 单核普通可缓存、对齐整字访问:M[X]=17,M[Y]=23;没有其他核正在写X/Y、无MMIO或Fence。
- Rename对同一周期多条指令仍按程序年龄应用映射;每次写目的寄存器分配一个新物理寄存器,并记录原RAT对应版本为stale pdst。
- 有可用数据且覆盖完整时允许Store-to-Load Forwarding;Store进入/离开ROB的提交与真正对其他核可见分开处理。
- 预测错误时丢弃所有错误路径年轻指令,撤销其新物理目标,恢复RAT及投机GHR。回收的最小编号物理寄存器可再分配。下文的事件顺序是逻辑Trace,不是声称真实CPU固定使用这些周期数。
- ROB正常按序退休;正常退休一个写寄存器的指令,且无需额外保留旧值时,释放该指令的stale pdst。
我们把「分支解析是否正确」「Load返回值是否正确」「指令是否已退休」分别作为独立状态。一个指令可以执行结束却仍在ROB中等待。
三、先给一段完整程序(约2分钟)
I1: ADD R1, R1, R2 # R1 <- 4+3
I2: STORE [X], R1 # 使用I1产生的值
I3: LOAD R3, [X] # 读同址,可能SQ转发
I4: BRANCH if R3==7 to T5 # 预测Not Taken,实际Taken
# 预测错误的顺序路径
W5: ADD R4, R1, 1
W6: LOAD R5, [Y]
T5: ADD R4, R3, R2 # 正确目标路径
T6: ADD R5, R4, R2
注意I4会依赖I3的结果。前端预测Not Taken时,W5/W6可以先Rename、甚至执行完;这并不授权其错误结果提交。
3.1 第一步:Rename的物理版本表
| 指令 | 物理源版本 | 新pdst | stale |
|---|---|---|---|
| I1 | R1=P1,R2=P2 | P20 | P1 |
| I2 | 数据源R1=P20 | 无 | 无 |
| I3 | 内存地址X | P21 | P3 |
| I4 | 比较源R3=P21 | 无 | 无 |
| W5(错误路径) | R1=P20 | P22 | P4 |
| W6(错误路径) | 地址Y | P23 | P5 |
I1完成后P20的值为7,I2使用P20作为要存入X的数据。I3读取X时可由较老Store I2转发值7,不必等待I2对其他核可见。I3产生P21=7,I4因而实际应跳到T5。
I4预测后分支快照中的RAT是:
R1→P20 R2→P2 R3→P21 R4→P4 R5→P5
错误路径Rename之后,R4/R5暂时分别映到P22/P23。即使W5已经计算出8、W6已经从Y读取23,它们也不能越过I4提前退休。
3.2 第二步:Squash后的正确资源状态
分支I4发现真实Taken时,恢复其正确分支边界映射,丢弃W5和W6,新分配的P22/P23返还Free List。P20/P21虽然此刻可能仍未退休,却是分支之前正确路径的物理版本,绝不能一起归还。
随后正确路径T5/T6可以重用P22/P23:
| 指令 | 源版本 | 新目的 | 结果 | stale |
|---|---|---|---|---|
| T5 | P21、P2 | P22 | 10 | P4 |
| T6 | P22、P2 | P23 | 13 | P5 |
最终正确RAT应为:
R1→P20 R2→P2 R3→P21 R4→P22 R5→P23
所有权不能因为「两个分支版本曾使用同一个物理编号」就混淆:错误路径P22失效并归还后,正确路径再次分配P22是合法的两段不同生命期。
四、完整Free List账本与不变量(约2分钟)
从初始6个空闲寄存器开始:
| 事件 | 变化 | 空闲数量 |
|---|---|---|
| 初始 | — | 6 |
| I1与I3新分配P20/P21 | −2 | 4 |
| 错误路径W5/W6分配P22/P23 | −2 | 2 |
| I4误预测,Squash W5/W6 | +2 | 4 |
| 正确路径T5/T6重新分配P22/P23 | −2 | 2 |
| I1、I3、T5、T6依序正常退休,释放stale P1、P3、P4、P5 | +4 | 6 |
这一账本只有在「中间无其他分配/释放,所有旧版本不需额外保留」的假设下成立。I2、I4、分支本身没有新pdst,也不需要释放一个stale。
重要资源不变量:
[ \boxed{\mathrm{Free}\cap\mathrm{LivePhysical}=\varnothing} ]
其中LivePhysical包括有效架构映射、尚有消费者的物理版本,以及被正确恢复机制明确保留的状态。RAT不再指向P1,不代表P1可在Rename时立即释放;较老读者可能仍绑定P1。通常在覆盖者正常退休、且更老读者都已退休时回收其stale。
另一个不变量:
[ \boxed{\text{已退休的指令必须形成程序顺序上的连续前缀}} ]
这允许精确异常与正确分支恢复。需要特别注意:提交路径的逻辑顺序可以由ROB维护,但这不等于每个Store的对外传播也与ROB退休同周期完成。
五、恢复的不只是RAT:分支预测历史(约2分钟)
回顾第12课:GShare可能在分支尚未执行时就将预测结果移入GHR,以便下一个分支使用较新的投机历史。
假设2位GHR在I4预测前为 (10_2),I4预测Not Taken(位0),更新规则为:
[ GHR’=((GHR\ll1)\mid bit)\ \&\ 3 ]
预测后投机GHR变为 (00_2)。W5/W6路径上如果还有其他分支,可能进一步污染投机GHR。I4确认实际Taken(位1)后,必须恢复I4预测前的 (10_2),再移入真实位1,得到正确路径历史 (01_2)。
这里要把三个恢复对象分开:
- RAT:哪个架构寄存器映射哪个物理版本?
- Free List/Allocation记录:哪些物理编号仍在使用,哪些分支之后的新分配应撤销?
- GHR与PC:下一条应从哪里Fetch,后续PHT索引应该看到怎样的历史?
单纯将PC改成正确目标,不足以恢复寄存器和预测状态。单纯恢复RAT,也不保证Free List处理了所有分配、释放、再分配的交错。BOOM的显式重命名设计为分支保存映射快照,并跟踪分支后的物理寄存器分配;预测器还管理独立的GHR恢复状态。
六、执行完成、Writeback、Commit、Store对外可见:四条不同时间线(约2分钟)
| 事件 | 允许发生什么 | 尚不能推出什么 |
|---|---|---|
| Execute完成 | 算术结果或Load结果已经计算/返回 | 不能推出年轻指令已退休 |
| Writeback | PRF中的值可唤醒其他消费者 | 不能推出软件可见架构状态已不可撤销 |
| ROB Commit/Retire | 按程序顺序确认合法指令;合适时回收旧版本 | 不能推出Store已经被其他核观察到 |
| Store对外可见 | 写入沿缓存/一致性体系传播,按内存模型供其他核观察 | 不能把这个时刻简单等同于本核提交 |
在本例中I2可以先退休,再由已提交Store队列继续等待写入。I3仍可通过本核较老Store的转发看到7。与此同时,其他核在尚未看见I2写入之前可能仍观察到X的旧值;这与本核I3转发正确并不矛盾。
6.1 TSO Store Buffering 的严格反证
两个核、初始X=Y=0:
Core 0: Core 1:
Sx: STORE X=1 Sy: STORE Y=1
Ly: r0=LOAD Y Lx: r1=LOAD X
在SC(顺序一致性)下,程序顺序要求 (Sx<Ly) 与 (Sy<Lx)。若两次Load均读0,则需 (Ly<Sy)、(Lx<Sx)。组合成:
[ Sx<Ly<Sy<Lx<Sx ]
出现严格顺序环,因此SC下不可能两次都读0。
但在一个允许Store→不同地址Load放松的TSO类Store Buffer模型中,各核先将自身Store放入缓冲,随后各自Load读取另一个地址的旧0,最后两个Store向外传播,((r0,r1)=(0,0))可以出现。注意这是不同地址;同核Load读取自身较老的同址Store仍需满足相应Store Forwarding规则。
本核程序按序退休≠所有核严格按同一SC序列观察到全部内存访问。 这将在第5周作为重点重新证明。
七、把整个执行闭环映射到性能瓶颈(约2分钟)
假设每条架构指令一uop,稳态指令退休吞吐为 (\lambda)(IPC),Fetch/Rename/Issue/Commit宽度分别是 (W_F,W_R,W_I,W_C)。再设ROB有R条目、平均占用 (T_R) 周期;LQ有Q个条目、Load比例 (f_L)、平均占用 (T_L)。
从第13课的宽度上限及Little定律:
[ \boxed{\lambda\le\min(W_F,W_R,W_I,W_C,R/T_R,Q/(f_LT_L))} ]
这是必要上界,不是程序的保证IPC。使用同一计数边界、相对稳态和一致单位是前提;扩大硬件队列后,平均占用周期本身可能改变。
新的综合数字:宽度分别是5/4/4/3,ROB=80且 (T_R=40),LQ=30且 (f_L=0.25,T_L=40)。则宽度上界3、ROB容量上界2、LQ上界3,所以总上界2 IPC。这时仅把Fetch从5改成8,并不能突破2;若把ROB改成120且其他参数暂保持,两个容量上界都变为3,新的理论上界是3,但实际结果还受执行依赖、Cache、恢复和其他限制。
7.1 分支错误为什么不能简单把停顿周期全部相加?
简化分支损失模型:
[ \Delta CPI=f_b r_m P=\frac{MPKI}{1000}P ]
其中P被定义为相对于基线真正额外、未被其他等待隐藏的周期损失。若ROB Full和Branch Recovery发生在同一个周期,把两个计数器各加1,并不意味着时间真实经过2周期。
更严谨的实验应保存:按周期的Fetch有效量、Rename背压、ROB/LQ占用与Full、Issue ready数、分支恢复事件、Commit数及真实完成时间。反事实评估要在保持工作量相同时单独改动某个限制。
八、专题反例:每次都先问“哪个保证被破坏?”(约1分钟)
反例A:错误路径W6已经从L1命中Y,便把R5=23作为正式结果。——违反正确路径的按序退休/恢复边界;命中不等于授权提交。
反例B:Squash时把P20/P21一并归还,因为它们尚未退休。——违反分支前正确物理版本的所有权;未退休不等于错误路径。
反例C:只恢复RAT,不恢复GHR,随后预测器继续使用错误路径的分支历史。——破坏正确路径预测状态,虽然RAT已正确。
反例D:认为Store I2已经退休,所以其他核必须同步看见X=7。——混淆架构退休与Store Buffer传播。
反例E:发现ROB平均占用低,就断言它从未阻塞前端。——平均值可能掩盖短时间满队列和尖峰反压,应查逐周期事件。
反例F:ROB和分支恢复各报告100个stall周期,直接说额外损失200周期。——如果两事件重叠,需要以时间区间并集或经过清晰定义的关键原因分类分析。
九、完整验证路线与下一轮(约1分钟)
让另一个人复查一次乱序Trace,至少应能从记录中重建:
cycle / instruction ID / program age
predicted PC / actual PC / GHR snapshot
source physical tags / pdst / stale pdst
ROB state / issue-ready / execution complete / writeback
LQ-SQ address-known / data-known / forwarding / violation
squash boundaries / RAT restore / returned allocations
committed register map / free ownership
committed Store / Store Buffer status / visibility events
检查三个不变量:
[ \text{无错误路径不可撤销退休} ] [ \text{无有效物理版本与Free同时拥有同一寄存器} ] [ \text{每个Load的最终值符合其内存模型与有效Store顺序} ]
以上三条可由确定性模拟器、断言和对照执行实现自动检查;真实芯片仍需结合设备约束验证。
下节预告:第15课(2026年11月3日)进入第3周“分支、ROB与推测执行”的深化专题:精确异常之外:错误路径微架构痕迹、预测恢复与Spectre基本威胁模型。重点是“架构结果正确”为什么不必然提供安全隔离,而不是简单重复两位计数器公式。
参考材料
- BOOM Rename Stage:stale pdst、Branch Map快照及Allocation List。
- BOOM ROB:按序退休、异常及Store提交后继续排空。
- BOOM Backing Predictor:投机GHR与恢复。
- RISC-V RVWMO:内存操作的程序顺序、load值与全局内存顺序;本讲TSO只作分模型对照,不将其等同RVWMO。
第2周四级分级测评(100分)
首次授课不公布标准答案。 前三题可客观判分;Lv4提交推导后按评分要点人工或自评,不能把未评开放题计入已自动通过。题目是综合性新题,不是将前几课习题简单改数字。
Lv1|Store退休、Load转发与全局可见|15分|单选|预计2分钟
在一个按序退休、拥有Store Buffer与Store-to-Load Forwarding的单核中,较老Store已准备好完整地址和数据,但尚未对其他核可见。较年轻、同址且完全重叠的Load需要读取该数据。哪种判断最准确?
A. Load只有在其他核都看到Store以后才允许得到该值。 B. Store在ROB中按序退休即可证明所有核同时看到该写入。 C. 满足转发条件时,Load可以从较老Store取得正确值;这不意味着Store已经全局可见。 D. 寄存器重命名已经消除了所有内存别名依赖,所以不必检查SQ。
可选提示(不泄露答案)
分别列出Store数据可被本核转发、Store正常退休与写传播到其他核这三个时间点,并判断是否必须同时发生。Lv2|按序退休的逐周期Trace|20分|数值|预计4分钟
一台教学CPU已经把I1— I5依程序顺序分配到ROB。Commit宽度为每周期最多2条,只能从ROB头连续退休,不能跨过未就绪指令。Cycle从1开始,每个周期开始时检查就绪状态;不考虑其他异常或资源限制。
| 指令 | 从哪个周期开始就绪 |
|---|---|
| I1 | 7 |
| I2 | 2 |
| I3 | 4 |
| I4 | 3 |
| I5 | 2 |
每周期最多退休两条,并在下一周期继续处理剩余ROB条目。I5最早在哪个周期退休? 只填写整数。
可选提示(不泄露答案)
先观察最老I1什么时候允许退休,再逐周期从ROB队头连续取最多两条。不要因为I5早已完成而允许它越过更老指令。Lv3|恢复不变量、分支历史与内存模型|25分|多选|预计5分钟
考虑采用显式寄存器重命名、ROB、LSQ、预测GHR与可恢复分支投机的CPU。选择所有成立项。
A. 如果GHR在Fetch时按预测方向投机更新,误预测后应排除错误路径历史并恢复正确路径历史。
B. 分支Squash只要恢复RAT,就能在任意Free List分配/释放交错中自动保证物理寄存器所有权正确,无需其他记录或机制。
C. 满足覆盖与数据有效条件时,本核年轻Load可以在较老Store对外可见之前从该Store转发数据。
D. 在顺序一致性SC中,两个核各自先写一个不同地址、再读对方地址,两个Load都读到初始0必然允许。
E. 按序退休下,较老未完成指令可以挡住已经写回的年轻指令退休,并进一步产生ROB背压。
F. 只要错误路径的ALU结果曾写入物理寄存器,恢复时就必须逐位将所有相关寄存器的物理存储清零,不能依靠失效映射和资源所有权来恢复。
可选提示(不泄露答案)
把“预测历史”“物理版本所有权”“本核转发”“SC全局总顺序”“按序退休”分成五套分别检查。对于错误路径,区分删除错误状态的有效引用与把物理比特全部抹零。Lv4|内存依赖违例触发分支翻转:完整恢复与资源守恒|40分|开放推导|预计10分钟
这是一道与正文不同的综合情形:错误的Load数据导致分支沿错误方向继续执行,随后较老Store的地址才揭晓。
教学假设:单核、普通可缓存对齐整字访问,无其他核写入、无Fence;支持对未知Store地址的Load投机。发现违例时,本实现选择从违例Load开始Squash并重取它及所有年轻指令,旧分支历史和有效物理所有权必须恢复。恢复后按最小编号分配Free寄存器。最终按序退休,安全释放stale。
初始:R1=4,R2=3,R3=0,R4=0;RAT分别为P1、P2、P3、P4。M[X]=5,M[Y]=8。Free List为{P20,P21,P22,P23,P24,P25}。
S0: STORE [p], R1 # 数据4已知,但p尚未解析
L1: R3 = LOAD [X] # 分配P20,提前读旧M[X]
B2: BRANCH if R3==5 to W3 # 基于投机Load结果预测/暂判Taken
# Taken方向先执行的工作
W3: R4 = R3 + 10 # 分配P21
W4: R1 = R4 + R2 # 分配P22
# 直到后来S0地址揭晓:p = X
# 处理器从L1开始Squash/重取,按正确结果决定B2方向
# 正确Not Taken方向
C3: R4 = R3 + R2 # 允许重用返还的P21
A|依赖和错误传播(12分):列出L1、W3、W4的pdst、stale、物理源版本及最初的值;说明从未知Store地址开始,为什么L1读到的值只能算投机正确。指出分支为何可能因错误Load值而进入错误路径。
B|发现违例后的恢复(12分):p解析为X后,说明哪个Load与哪条较老Store冲突;本题定义的Squash范围是什么?重取L1后应从哪里取得哪个值?分支B2的正确方向如何改变?给C3的最终结果。解释必须恢复哪几类投机状态。
C|Free List和退休(10分):列出初始、首次错误路径重命名完、Squash完、正确路径重命名完、最后S0/L1/B2/C3退休完的Free寄存器数量,以及最终RAT映射。说明哪些stale在正确路径正常退休时才释放。
D|两项不变量(6分):写出一个防止“仍有效的物理版本同时位于Free List”的断言,和一个保证错误的Load/分支结果不会提前不可撤销提交的检查。再用一句话说明S0退休与其跨核可见不是同一时刻的必然事件。
可选提示(不泄露答案)
先把「首次投机执行」与「从Load重取后的正确执行」分成两条时间线。别把仍需保留的P1/P2/P3/P4与错误路径新分配混为一谈;正常回收stale只发生在对应的正确路径覆盖指令安全退休时。作答与进度规则
Lv1:
Lv2:
Lv3:(字母组合)
Lv4:
A:
B:
C:
D:
评分按15、20、25、40分:≥80分继续既定新专题;60–79分补一题针对性的恢复Trace;<60分回顾第9—14课对应机制后再练。测验表现不会改变日期编号:第15课仍是2026年11月3日。作答保存在网站浏览器本地;开放题只记录人工/自评与rubric,不冒充全自动证明评分。