计算机体系结构 · 第9课|Tomasulo:为什么Ready不代表立即执行?
2026年10月28日|第2周第2课|约18分钟
第8课说明寄存器重命名能解除WAR/WAW名字相关,却不能消灭RAW。本课追问:结果尚未产生时,消费者怎样等待?结果产生后,为什么它有时仍不能执行?我们讨论本核寄存器指令;内存依赖、TSO和跨核可见性将在后续单独讲解。
一、动机:依赖图只给出了约束,还缺执行机制
I1: MUL R1, R2, R3 # 多周期,产生R1
I2: ADD R4, R1, R5 # 等待I1
I3: ADD R6, R7, R8 # 与I1、I2独立
I2若停住,不应该挡住独立的I3。但是不能简单等待架构寄存器名R1,因为后面的指令也可能写R1;指令需要等待特定生产者版本的标签。这就是Tomasulo思想:在保留站保存操作和操作数,源暂缺就存标签,结果通过带标签的广播通知所有消费者。
flowchart LR
A["按序Decode/Rename"] --> B["RS / Issue Queue"]
A --> C["ROB: 按程序顺序建条目"]
B --> D{"两个源都Ready?"}
D -- 否 --> B
D -- 是 --> E["Select仲裁"]
E --> F["ALU / MUL执行"]
F --> G["结果tag + value广播"]
G --> B
G --> C
C --> H["按序Retire或异常恢复"]
箭头G→B表示唤醒别的保留站,不是本指令重新入队。今天所有时间约定在周期末广播,依赖者最早下一周期发射。
二、Reservation Station保存什么?V与Q到底有什么区别?
假设物理寄存器重命名后,有以下指令:
ADD P21 <- P20 + P5
P5的值7已经就绪,P20尚未由乘法生产:
| 字段 | 状态 | 含义 |
|---|---|---|
| Busy / Op | 1 / ADD | 已占用的加法等待槽 |
| Dest | P21 | 本条指令的结果标签 |
| Vj / Qj | — / P20 | 源j尚无值,等待P20 |
| Vk / Qk | 7 / — | 源k的值已拿到 |
| Ready | false | 不可申请ALU发射 |
| State | Waiting | 已派发,未开始执行 |
V(Value)是已持有的实际源值;Q(Tag)是尚缺源值所对应的生产者版本。 每个源在这个教学模型里非V即Q。某些现代实现仅保留标签与ready位,值存在物理寄存器文件而非保留站里,功能逻辑相同。
当结果总线广播(tag=P20,value=42),各保留站的比较器监听标签。若Qj=P20,就把Vj更新成42、清除Qj、置源j ready。若源k原本ready,整条指令现在ready,下一周期开始才可参加发射选择。一次广播可同时唤醒多个等待同一P20的保留站,不需要逐个消费者单独传值。
概念伪代码(表示功能,硬件实际并行比较,不运行软件循环):
def broadcast(tag, value):
for station in waiting_stations:
for source in station.sources:
if not source.ready and source.wait_tag == tag:
source.value = value
source.ready = True
source.wait_tag = None
这也解释寄存器重命名与Tomasulo怎样配合:消费者在重命名时绑定的是最近一次较早写入的物理版本。只比较架构名R1而不区分不同版本,可能把后写的结果误送给先读者。
三、Wakeup不是Select:已经Ready,为什么还在队列?
Wakeup回答:所需源操作数到齐了吗? Select回答:这么多已就绪指令,本周期让谁真正拿到执行端口?
RS-A: ready=1 ─┐
RS-B: ready=1 ─┼──► Select/Arbiter ──► 本周期1个ALU发射槽
RS-C: ready=1 ─┘ 未选中的继续留在队列
有三条Ready ADD而只有一条ALU发射端口,本周期最多选一条。策略可能是最老优先,也可能是固定槽位优先、银行化调度等;每种方案的公平性、时序与功耗不同。即使两源Ready,也可能因ALU繁忙、端口不兼容、选择优先级或读取资源冲突而等待。
现代设计还能做fast wakeup或旁路提前唤醒,在能够保证ALU结果经bypass按时提供时,预测式地更早使消费者申请执行。但是这有严格的时序、取消和重放前提。本课故意采用结果广播之后下周期才可以发射的简化模型。BOOM官方资料也区分ALU快唤醒与较长延迟操作的慢唤醒。
四、CDB总线拥塞:执行完成未必等于数据可见
本节采用六条指令构成一个完整执行trace。先把假设列齐:
- MUL延迟3周期,ALU延迟1周期,两个独立功能单元均每周期至多发射1条;其余源数据初始就绪。
- 六条指令在周期1以前已解码、重命名并放入足够大的RS与ROB。忽略派发、取指、结构容量限制。
- 在周期t发射、延迟L的指令在t+L−1周期末完成,尝试广播。
- 共享CDB每周期末最多传一个(tag,value)。若冲突,先服务此前周期已等待广播的结果;当周期同时新完成则较老指令优先。未发送的完成结果可放入缓冲区。
- 无同周期旁路:消费者在周期t末收到数据,最早周期t+1参加选择。
I1: MUL P20 <- P2 * P3 # 3周期
I2: ADD P21 <- P20 + P5 # 等I1
I3: ADD P22 <- P6 + P7 # 独立
I4: ADD P23 <- P22 + P8 # 等I3
I5: ADD P24 <- P23 + P9 # 等I4
I6: ADD P25 <- P20 + P24 # 等I1和I5
flowchart LR
I1["I1 MUL P20"] --> I2["I2 ADD P21"]
I1 --> I6["I6 ADD P25"]
I3["I3 ADD P22"] --> I4["I4 ADD P23"]
I4 --> I5["I5 ADD P24"]
I5 --> I6
| 周期 | 执行端口启动 | 本周期末新算完 | 本周期末真正广播 | 结果 |
|---|---|---|---|---|
| 1 | MUL I1、ALU I3 | I3→P22 | P22 | I4下周期可运行 |
| 2 | ALU I4 | I4→P23 | P23 | I5下周期可运行 |
| 3 | ALU I5 | I1→P20与I5→P24 同时完成 | P20(较老) | I2获得P20;P24缓冲等待 |
| 4 | ALU I2 | I2→P21 | P24(上一周期已等待) | I6两个源都就绪;P21缓冲 |
| 5 | ALU I6 | I6→P25 | P21(上一周期已等待) | P25缓冲等待 |
| 6 | 无 | 无 | P25 | 全部结果已广播 |
逐步观察:I5在周期3末已经算完P24,却输掉CDB仲裁。I6需要P20和P24两个源,直到周期4末收到P24才真正Ready,因此最早周期5启动。I2在周期4算完P21,但结果总线被P24占用,只有周期5末广播。因此本案例最后结果广播结束于周期6末,不能把“执行完”简单当“依赖者已经拿到值”。
此表只定义了单结果广播的教学处理器;真实机器可能有多端口写回、bypass、分布式结果网络,不应套用单CDB的一般结论。
五、ROB为何必须按序退休?
上面I3周期1已经广播,但I2直到周期5才广播。若I3可以比I2先成为不可撤销的架构状态,而I2又出现精确异常,软件就会看到“后面的操作已经提交,前面的操作却未执行”的不一致断点。
现代OoO通常把Tomasulo风格的保留站、标签和动态调度同Reorder Buffer(ROB)组合。ROB按照程序顺序保存各条在途指令的完成标记、异常状态和目标版本;只有队头满足条件才能退休。执行与结果广播可乱序,但架构提交按序;一条较老指令异常时,后面的年轻投机结果必须能清除并恢复重命名状态。
历史区分:IBM System/360 Model 91的原版Tomasulo已有保留站与CDB,不能说原版已经包含现代ROB的精确异常提交机制。我们现在讨论的是现代教学组合模型。
再假设ROB每周期最多退休1条,并且指令在周期t末广播后最早周期t+1退休。依照I1至I6的程序顺序:
| 周期末 | 退休 | 为什么 |
|---|---|---|
| 4 | I1 | I1周期3末已广播,位于队头 |
| 5 | 无 | 队头I2直到周期5末才广播 |
| 6 | I2 | 队头结果已就绪 |
| 7 | I3 | 虽然周期1就广播,也必须等I1/I2 |
| 8 | I4 | 按序 |
| 9 | I5 | 按序 |
| 10 | I6 | 最后一条退休 |
最后结果广播是周期6,最后退休是周期10。退休宽度、状态更新和结果延迟都是案例假设;不能从表格推导“每个ROB天然额外需要4周期”。
精确异常不变量是:已经退休的指令始终构成原程序顺序的某个前缀;后续尚未退休的结果不能产生不可回滚的架构副作用。内存Store是否对其他核可见,还要考虑Store Queue/Buffer和一致性规则。本核退休≠进入Store Buffer≠全局可见;这是后续TSO专题需要特别强化的地方。
六、结构资源与性能下界:增大队列不一定提升IPC
区分三种相互独立的资源:RS/IQ容量控制可同时等待多少指令;Select/功能单元端口控制每周期多少Ready指令启动;结果广播网络控制每周期多少完成值送给依赖者。增大IQ条目可能在更大窗口中找到独立工作,却不能增加一条CDB的带宽。
假设N个队列条目每条有2个等待源,有b条结果标签并行广播,最朴素全互联方案约涉及最多2Nb个并行tag相等比较。增加窗口与广播宽度会增大比较器、布线、动态功耗和wake-up/select关键路径,不是免费收益;真实实现可能做银行化、局部广播或旁路优化。
如果K个结果已经完成,每周期最多广播c个,单为这些结果留出的广播时隙下界为
[ N_{\mathrm{slot}}\ge\left\lceil\frac{K}{c}\right\rceil. ]
这是占用时隙的数量下界,不是整个程序的精确耗时。结果到达时刻、依赖链和端口选择仍需建模。
对第4节,增加第二条CDB能让周期3的P20/P24同时广播,但到周期4单ALU可能同时有I2和I6就绪,仍只能选一条:瓶颈会迁移到执行端口。这与第一周Roofline/Little模型的资源下界分析是同一思路。
七、常见错误、反例与模型边界
错法1:Ready就是下一条执行。 Ready只是向Select提出请求,未被选中仍等待。若只有一条ALU,三条Ready ADD不可能同周期全部执行。
错法2:结果算完等于消费者收到。 CDB、写回端口可能争用;在无旁路模型里,消费者等到广播才由Q转为V。真实设计若有fast wakeup,需要另写时序和回滚假设,不能偷用。
错法3:ROB按序提交等于跨核Store按序可见。 ROB主要保证本核架构提交和精确异常,内存对其他核的可见性还受Store Buffer、内存模型与一致性协议控制。之前易混淆的TSO Store Buffering正是要分清这几个时间点。
八、一分钟总结与下讲预告
五个动词抓住机制:Rename先绑定正确版本;Wait把源值或未就绪标签留在RS;Wakeup通过tag+value广播转换Ready;Select/Execute根据端口与仲裁选择运行;Retire在ROB头按序提交或异常恢复。
真正的RAW依赖无法由重命名消除;相邻独立工作可以隐藏其等待。但若总线、发射端口、队列或ROB成为瓶颈,即使计算能力有余,也不能无限提高IPC。
第10课(2026-10-29)预告:ROB、Free List、Checkpoint和异常/分支误预测恢复;重点解释旧物理寄存器何时安全回收、错误路径结果为什么不能提交。
参考资料
- RISC-V BOOM: Issue Unit:wakeup、select、端口仲裁、fast/slow wakeup。
- RISC-V BOOM: Reorder Buffer:按序退休、精确异常与flush。
- University of Edinburgh: Tomasulo Model:原版Tomasulo的保留站与CDB模型。
九、四级分级测评(总分100;首次不提供答案)
Lv1至Lv3为可客观判分的题,Lv4需人工、ChatGPT或本人依评分要点评议,不做虚假开放题自动评分。作答后:总分≥80按既定日程继续,60–79补一例,低于60重点复习再练;课号始终按自然日不变。
Lv1|就绪与选择的机制辨析(15分,单选,预计2分钟)
关于保留站和 ROB,哪个判断最严谨?
A. 源数据全就绪只表示能够竞争合适的执行端口,仍可能因为端口忙或 Select 仲裁失败而继续等待。
B. 生产者一旦算完,消费者不论是否有旁路都能在同一周期发射。
C. 年轻指令必须越过较老指令退休,机器才算支持乱序执行。
D. 增大 Issue Queue 容量必然同比提高结果广播带宽。
可选提示(不泄露答案)
依次区分 Ready、Select、Execute、Broadcast 和 Retire。Lv2|广播时序和ROB退休计算(20分,数值,预计4分钟)
已完成重命名入队的四条指令:J1 MUL P30←P2×P3;J2 ADD P31←P4+P5;J3 ADD P32←P31+P6;J4 ADD P33←P30+P7。周期1开始,独立MUL延迟4周期,单ALU的ADD延迟1周期且每周期最多发射1条;总线每周期最多广播1个结果(本题无冲突)。周期t发射、延迟L的指令在t+L−1周期末广播,消费者最早下周期发射;ROB宽度1,只能从广播后的下一周期开始按程序顺序退休。问J4最早在第几个周期末退休?只填整数。
可选提示(不泄露答案)
先计算各指令的广播周期,再按J1至J4的ROB顺序逐条推退休周期。Lv3|CDB争用及历史机制边界(25分,多选,预计5分钟)
对于周期末广播、消费者最早下周期才能发射、无提前唤醒旁路的模型,哪些说法正确?(多选)
A. 同一次带有目标标签和数据的广播可以同时唤醒多个等待该目标标签的保留站输入。
B. 尚有未满足Q标签的指令应直接作为Ready候选参与执行端口竞争。
C. 功能单元已完成但CDB尚未轮到该结果时,其消费者可能继续处于等待状态。
D. 现代使用ROB的乱序机器允许年轻指令先完成,但退休必须受ROB队头约束。
E. 1967年IBM原版Tomasulo已经使用与现代OoO相同的ROB精确异常提交。
可选提示(不泄露答案)
关注谁接收广播、Q何时变成V,以及原版Tomasulo和现代组合设计的区别。Lv4|调度器设计和精确异常证明(40分,证明/设计,预计10分钟)
设计保留站+标签广播+选择器+ROB的简化乱序调度器:两个生产者的目标标签P30、P31均在周期4末完成;一条CDB每周期只能广播一个结果,周期4优先广播P30,未发送结果可缓冲。消费者U1等待[P30,P31],U2等待[P31,立即数5],U3等待[P30,立即数7]。无旁路,广播末更新Ready,下一周期才可发射。A(10分)列出保留站字段与标签匹配规则。B(10分)推导周期4和5的广播及各消费者最早Ready/可申请发射周期(忽略消费者自身广播与端口竞争)。C(12分)论证ROB如何维护精确异常、如何处理异常指令之后的结果。D(8分)比较加一条CDB和单纯扩大IQ容量的收益与硬件代价,提出两个可观测验证指标。