计算机体系结构 · 第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)。

这里要把三个恢复对象分开:

  1. RAT:哪个架构寄存器映射哪个物理版本?
  2. Free List/Allocation记录:哪些物理编号仍在使用,哪些分支之后的新分配应撤销?
  3. 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,不冒充全自动证明评分。