计算机体系结构 · 第 8 课|ILP 与寄存器重命名:让独立指令越过等待
2026 年 10 月 27 日|第 2 周第 1 课|约 17 分钟
上周用 CPI、Roofline 和 Little 定律定位资源瓶颈。本周开始追问更微观的原因:为什么 ALU 明明空闲,程序还会停住? 今天从指令级并行(ILP)和 RAW/WAR/WAW 入手,走完重命名、乱序调度与执行完成的逐周期 trace。讨论以整数寄存器指令为主,内存依赖留待后续课程。
1. 动机:程序顺序不一定等于数据流顺序(2 分钟)
I1: MUL R1, R2, R3 # R1 = R2 * R3
I2: ADD R4, R1, R5 # 等待 I1 的 R1
I3: ADD R6, R7, R8 # 与 I1、I2 无关
I4: SUB R9, R6, R10 # 等待 I3 的 R6
I5: XOR R11, R12, R13 # 独立
文本里的顺序是 I1、I2、I3、I4、I5,但真正的数值依赖只有 I1→I2 与 I3→I4。既然 I2 卡在乘法结果上,为什么不能先做 I3 和 I5?
ILP(Instruction-Level Parallelism)指同一指令流内部能够重叠执行的独立操作,并不要求有多个软件线程;与多核心 TLP、SIMD 数据并行是不同概念。
flowchart LR
I1["I1: MUL R1"] --> I2["I2: ADD R4"]
I3["I3: ADD R6"] --> I4["I4: SUB R9"]
I5["I5: XOR R11"]
没有箭头的两条指令,不一定必须依次执行。 这里已假设没有分支、访存、异常或共享功能单元之外的特殊先后要求。
2. 四个不同阶段:调度、执行完成和退休不能混用(2 分钟)
flowchart LR
F["Fetch / Decode"] --> R["Rename / Dispatch<br/>依程序顺序绑定源版本"]
R --> IQ["Issue Queue<br/>等待操作数"]
IQ --> EX["Issue / Execute<br/>可乱序"]
EX --> WB["Writeback<br/>写结果、唤醒后继"]
WB --> COM["Retire / Commit<br/>按程序顺序确认"]
Rename/Dispatch: 按程序顺序把源寄存器名字绑定到相应的物理寄存器版本,并把指令放入待调度结构。源数据可能还没算出来,只有标签。
Issue(本课采用“进入执行单元”的定义): 等源操作数就绪、执行端口和其他资源可用后,把指令送入功能单元。不同资料可能把 dispatch 也叫 issue,因此阅读资料时要看其具体含义。
Complete/Writeback: 运算结束,结果变成可用,可唤醒下游等待该标签的指令。
Retire/Commit: 按程序顺序让执行结果在架构层面成为确定状态。较年轻指令可先完成,但若更老指令异常,处理器需能恢复精确的程序边界。
本课数值例题先比较最后一次执行完成,不是未经证明的整个程序墙钟时间;退休带宽、取指窗口与异常开销均另计。
3. RAW、WAR、WAW 的定义与边界(3 分钟)
对程序顺序中 i 早于 j 的指令,记 R(i) 是源寄存器集合、W(i) 是目的寄存器集合:
| 相关 | 寄存器访问模式 | 正确性关注点 |
|---|---|---|
| RAW:Read After Write | i 写、j 读,W(i)∩R(j) 非空 | 真相关:j 需要 i 产生的值 |
| WAR:Write After Read | i 读、j 写,R(i)∩W(j) 非空 | 反相关:j 不能过早覆盖 i 尚须读取的旧值 |
| WAW:Write After Write | i 写、j 写,W(i)∩W(j) 非空 | 输出相关:写入顺序颠倒可能改变最终值 |
注意集合相交只是候选检测:一个源操作数真正依赖的,是程序顺序上离它最近、尚未被覆盖的前驱写入。不能把所有更早写过同名寄存器的指令都误认为真正的 RAW 生产者。
看一个同时有三类相关的例子:
S1: ADD R1, R2, R3
S2: MUL R4, R1, R5
S3: SUB R1, R6, R7
S4: XOR R8, R1, R9
S5: ADD R10, R4, R1
- RAW:S1→S2 的 R1,S3→S4 的 R1;S2→S5 的 R4 和 S3→S5 的 R1。
- WAR:S2 先读逻辑 R1,S3 随后写逻辑 R1。
- WAW:S1 与 S3 都向逻辑 R1 写入。
S3 的实际计算只需要 R6、R7,并不需要 S2 的乘法值。若 S3 不允许在 S2 真正读取 R1 前执行,是因为旧、新结果抢同一个物理名字。这就给寄存器重命名创造了空间。
重要边界: RAW/WAR/WAW是数据相关关系,不等于在所有处理器里都会形成同名流水线冲突。经典严格按序读写的五级流水线通常没有需要专门处理的WAR/WAW硬件hazard;乱序读写时假相关才会限制重排。
4. 寄存器重命名:同一个逻辑名有多个物理版本(3 分钟)
ISA 看到的是架构寄存器 R1;处理器内部能用 P20、P22 保存 R1 不同时刻的结果。RAT(Rename Alias Table)保存目前最新的“逻辑寄存器 → 物理寄存器”映射。
假设重命名前各 Rk→Pk,空闲 P20…P24。按程序顺序重命名 S1…S5:
| 指令 | 绑定的源版本 | 新目标物理版本 | 完成该条重命名后 RAT[R1] |
|---|---|---|---|
| S1: R1←R2+R3 | P2, P3 | P20 | P20 |
| S2: R4←R1×R5 | P20, P5 | P21 | P20 |
| S3: R1←R6−R7 | P6, P7 | P22 | P22 |
| S4: R8←R1 XOR R9 | P22, P9 | P23 | P22 |
| S5: R10←R4+R1 | P21, P22 | P24 | P22 |
S2 的 R1 固定指向 P20。后来 RAT[R1] 更新为 P22,不会倒回修改 S2 已经绑定的源标签。因此 S3 若其输入和执行单元就绪,不必等 S2 真正读出 P20 才能运行;S1 与 S3 也写在不同物理寄存器,不再竞争“谁最后写R1”。
反过来,S2 仍需等待 P20 被生产,S4 仍需等待 P22 被生产。重命名不能消灭真正的 RAW 数值依赖。
简化的按序重命名过程:
for ins in program_order:
src_tags = [RAT[r] for r in ins.sources] # 先捕获源版本
old_dst = RAT[ins.dest] # 记录旧目的版本供以后安全回收
new_dst = free_list.allocate()
RAT[ins.dest] = new_dst # 再更新新目的版本
ROB.allocate(src_tags, old_dst, new_dst)
issue_queue.insert(src_tags, new_dst)
它是概念伪代码,真实处理器还要处理异常恢复、无目的寄存器指令、特殊寄存器、提交和回收。
为什么“先读再改”不可颠倒? 对 ADD R1, R1, R2 这样的自读自写指令,源 R1 必须绑定到原来的物理版本。如果先改 RAT[R1],再查源,它就会把自己的新目标误当输入,造成未写就读的自依赖。
5. 逐周期比较:乱序不是加速乘法,而是隐藏等待(3 分钟)
回到第一节五条 I 指令,建立可手算的机器模型:
- 每周期最多发射 1 条;MUL 延迟 4 周期,ADD/SUB/XOR 延迟 1 周期。
- 所有指令已在第 1 周期前解码、完成重命名并进入指令窗口;初始源输入全部就绪,忽略取指、分支、其他执行单元竞争。
- 周期 t 发射、执行延迟 L 的指令在周期 t+L−1 末产生结果;消费者最早下一周期发射。
- 只比较最终运算结果完成周期,不把此表直接当实际退休时间。
按序发射:
| 周期 | 发射或等待 | 本周期末完成 |
|---|---|---|
| 1 | I1 MUL | — |
| 2 | I2 等待 I1,空闲 | — |
| 3 | I2 仍等待,空闲 | — |
| 4 | I2 仍等待,空闲 | I1 |
| 5 | I2 ADD | I2 |
| 6 | I3 ADD | I3 |
| 7 | I4 SUB | I4 |
| 8 | I5 XOR | I5 |
允许跳过尚未就绪的较老指令:
| 周期 | 发射 | 本周期末完成 |
|---|---|---|
| 1 | I1 MUL | — |
| 2 | I3 ADD | I3 |
| 3 | I4 SUB | I4 |
| 4 | I5 XOR | I1、I5 |
| 5 | I2 ADD | I2 |
在这个理想模型中,最后一次执行完成从周期8提前到周期5。乘法本身仍耗4周期,收益来自利用原来闲置的周期。现实还存在退休、窗口大小和队列回填开销,因此不能把8/5直接认作程序实测速比。
为什么无论如何最早也不可能早于周期5?因为 I1 的乘法延迟4,I2必须依赖I1再做1周期加法。任意依赖DAG,若功能单元/发射宽度无限且全部指令已就绪入窗,以周期1为第一周期,有:
[ C_i=L_i+\max_{j\in pred(i)}C_j,\qquad\max\varnothing=0. ]
这里 (C_i) 是节点 i 最早完成的周期末编号;最长依赖路径形成时间下界。I1→I2 这条路径长度4+1,单发射乱序方案恰好触达它;严格按序发射则因队头阻塞额外产生空槽。
即便无 RAW,如果每周期最多能发射 W 条、总共 N 条需要发射,发射槽也至少要经历 (\lceil N/W\rceil) 个周期。实际的时间约束还包括 ALU/MUL 端口吞吐、指令窗口、分支误预测、Cache miss和退休宽度。ILP不是只由指令数或频率决定,而是由关键路径与各类资源共同限制。
6. 三个易错的反例与适用边界(2 分钟)
反例一:以为重命名能消除RAW。 如果十条整数指令每条都读取上一条刚写的结果,它们是长链。给每次写分配不同 P 寄存器只改变名字,无法提前得到尚未计算的值。增大发射宽度也不保证提升吞吐。
反例二:以为完成顺序就是退休顺序。 I3 可以比 I2 先算完,但它不能直接越过 I2 对外暴露不可撤销的架构状态。真实 OoO 常配合 ROB 按序退休以维持精确异常。若 ROB 满,即使某执行端口空闲,前端也可能停住。
反例三:把寄存器重命名当成内存模型。 两条 Load/Store 目标寄存器互不相同,也可能访问同一内存地址。消解地址别名、Store Buffer 转发、约束对其他核可见的顺序,是不同的问题。本核心执行顺序与全局可见顺序不能画等号:第五周会专门用 TSO Store Buffering 讲清这一点。
7. 三个核心结论(1 分钟)
[ \boxed{\text{RAW 是真值依赖;WAR/WAW 是可用物理版本重命名解除的名字相关。}} ]
[ \boxed{\text{按程序顺序绑定源版本}\ \to\ \text{按就绪乱序执行}\ \to\ \text{按序退休。}} ]
[ \boxed{\text{最后完成时间至少受依赖关键路径与执行资源共同限制。}} ]
自测说明: 四道新题依次为Lv1概念辨析(15)、Lv2周期计算(20)、Lv3多步机制分析(25)、Lv4证明/设计(40),总分100。首次不展示标准答案;客观题60分可自动计分,开放题须人工、ChatGPT或自评。
8. 四级分级测评(共100分,不提前揭示答案)
Lv1|RAW与完成/退休区分(15分,单选,预计2分钟)
某处理器允许较年轻的独立整数指令越过一条正在等待乘法结果的旧指令执行,并按程序顺序退休。以下哪项说法最严谨?
A. 较年轻指令可以先完成,但真正的 RAW 数据依赖仍须等待生产者的结果。
B. 寄存器重命名消除全部 RAW、WAR、WAW,因此指令无需再等待操作数。
C. 为了正确性,每条指令的执行完成顺序必须与程序顺序完全一致。
D. 只要允许乱序发射,IPC 就必然等于机器的发射宽度。
可选提示(不泄露答案)
把“寄存器名字”“数值是否已经生产”“完成还是退休”分成三个问题。Lv2|双发射就绪调度(20分,数值,预计4分钟)
教学处理器从周期1开始,六条指令在周期1前全部完成取指/重命名。每周期最多发射2条,其中最多1条MUL、1条ALU,功能单元都可每周期接收一条。MUL延迟3周期,ALU(ADD/XOR)延迟1周期;若周期t发射、延迟L,则t+L−1周期末完成,消费者下一周期才能发射。可乱序跳过未就绪旧指令,不计退休。程序:I1 MUL a←b×c;I2 ADD d←a+e;I3 ADD f←g+h;I4 MUL j←f×k;I5 XOR m←d XOR j;I6 ADD n←u+v。问所有指令最早在第几个周期末全部执行完成?仅填写周期整数。
可选提示(不泄露答案)
画出两条较长的依赖链。尽量让独立的ALU和MUL在同一周期一起发射,并考虑最晚消费者。Lv3|重命名与源操作数版本(25分,多选,预计5分钟)
依程序顺序为 I1: R2←R3+R4;I2: R5←R2×R6;I3: R2←R7−R8;I4: R9←R2+R5。每次写入都分配新物理寄存器,源操作数按程序顺序在修改目的映射前绑定。选出所有正确判断(多选)。
A. I2所读的R2必须对应I1产生的物理版本,不能被后来的I3改写映射影响。
B. 即使正确重命名,I3也必须等待I2在执行单元里真的读完R2数值才可发射。
C. I1→I3的WAW及I2→I3的WAR可由重命名消除,而I1→I2的RAW必须保留。
D. I4可以直接使用I1写的旧R2,因为最后按序退休会自动修正计算中读错的数值。
可选提示(不泄露答案)
逐条追踪每条指令在重命名瞬间看到的R2版本,并区分假相关与源值是否就绪。Lv4|算法不变量、关键路径和精确异常(40分,证明/设计,预计10分钟)
开放设计。初始架构→物理映射:R1→P1、R2→P2、R3→P3、R4→P4、R5→P5、R6→P6、R7→P7;空闲物理寄存器按P20、P21、P22、P23、P24依次分配。程序:I1 ADD R1←R1+R2(自读自写);I2 MUL R3←R1×R4;I3 SUB R1←R5−R6;I4 ADD R7←R3+R1;I5 XOR R1←R7 XOR R2。 (A,12分) 对每条指令写出两个源物理标签、目标物理标签、重命名后R1的映射,解释自读自写操作顺序。 (B,10分) 给出必须保留的RAW边。假设所有指令在周期1前完成重命名、发射宽度/功能单元不限,ADD/SUB/XOR延迟1周期、MUL延迟3周期;周期t发射且延迟L的指令在t+L−1末完成,消费者下一周期才可发射。求I5的最早完成周期及一条关键路径。 (C,10分) 给出重命名保证正确版本的循环不变量,并说明它怎样消除WAR/WAW但保留RAW;举例说明先更新目的映射再读源为何错误。 (D,8分) 说明按序退休与精确异常的关系,并提出至少两个实际硬件限制及可观测指标。
可选提示(不泄露答案)
维持“当前映射总指向已重命名前缀中最近一次写入版本”的不变量;自读指令必须先绑定旧源。关键路径从每条指令的最早结束周期向后递推。9. 下一讲与反馈
第9课(2026-10-28)继续讨论Tomasulo机制:保留站、标签广播、wakeup/select、发射队列选择、ROB及精确异常,从“操作数就绪”走向“真正选得上执行端口”。第5周集中补强TSO、Store Buffer与全局可见性。
四题作答后逐题批改,指出依赖识别、周期口径与证明的漏洞:总分80及以上继续既定主题,60~79补针对性算例,低于60回顾本讲重点再练。补练不改变按自然日推进的课号。