乱序执行

一、循环展开（Loop Unrolling）

1.1 动机：流水线中的停顿

原始循环代码（5 条指令 + 跳转）在流水线中执行：

原始：9 个时钟周期完成一次循环迭代（其中 5 个有效指令 + 2 个停顿 + 跳转开销）。
通过简单调度可减少到 7 个周期。

问题在于：指令之间存在数据相关，导致流水线停顿（stall）。

1.2 展开过程

将循环体展开 3 次（得到 4 个循环体），初步结果：

4 个循环体使用 27 个周期（看起来并没有显著提升）。
仅减少了 3 次跳转开销。

1.3 寄存器重命名 + 指令重排序

关键优化步骤：

寄存器重命名：为每个展开的循环体分配不同的寄存器（F6、F8、F10、F12、F14、F16等），消除循环体之间的假相关。
指令重排序：将 Load 指令集中在前面，Add 指令紧跟其后，Store 指令推到后面，使得每条指令的操作数在执行时已经准备好。

优化结果：

14 个周期完成 4 次迭代，零停顿（no stall）。
平均每个元素 3.5 个周期。
从 27 周期到 14 周期，接近 2 倍加速。

从 27 个周期直接到 14 个周期，太漂亮了。这就是编译器 -O3 全局优化做的事情。

1.4 循环展开的限制条件

限制	说明
有效性	必须找到不同循环体之间的无关性，才能安全展开
寄存器压力	展开需要使用更多寄存器，寄存器数量有限
正确性保证	Load/Store 地址不能冲突（如基址寄存器 R1 在循环中是否被修改）
跳转修正	需要删除多余的分支指令，修正循环计数代码

核心原则——不管怎么优化，必须得到与源代码相同的结果。

二、分支预测的性能边界

2.1 预测器的性能上限

分支预测器的数据：

简单预测器准确率已达 96%-98%。
两级预测器、竞赛预测器等高级方法：最差也有 93%-96%。
当 predictor size 达到 128 时，错误率仅 2.6%，已趋于平坦。

2.2 Amdahl 定律的启示

\[S = \frac{1}{(1-x) + \frac{x}{N}}\]

其中 $x$ 为可并行部分占比，$N$ 为加速倍数。

做任何一件事情，任何一个技术改进都是有边界的。当你领导团队时，要知道每个方向的上限在哪，决定资源投放。

三、静态调度 vs 动态调度

3.1 静态调度（编译器完成）

在编译时分析代码，重排指令顺序以减少停顿。
“拿一个超长的本子，一行一行写开”——纸上就能做的优化。
优点：简单，不增加硬件复杂度。
缺点：编译器无法处理运行时才确定的依赖（如通过指针/间接寻址的内存访问）。

3.2 动态调度（硬件完成）

CPU 在运行时根据实际情况自行调度指令。
对软件是黑匣子——程序员和编译器不需要知道内部细节。

核心优势：

保护软件资产：以前编译好的程序不需要重新编译，换了新 CPU 照样高效运行。
处理编译器无法分析的情况：如存储器地址冲突（指针别名问题）。
应对意外延迟：如 Cache Miss 导致的不确定延时。

代价：硬件复杂性显著增加。用户只要结果，不关心内部怎么实现。动态调度让硬件承担优化责任，解放了软件工程师。

四、乱序执行（Out-of-Order Execution）

4.1 基本概念

按序发射（In-order Issue）：指令从指令队列中按原始顺序取出。
乱序执行（Out-of-order Execution）：操作数已经准备好的指令可以先执行，不必等待前面尚未就绪的指令。

4.2 数据相关性分析

以一段代码为例：

DIV F0, F2, F4      ; F0 = F2 / F4
ADD F6, F0, F8      ; F6 = F0 + F8  ← 需等 DIV 完成（RAW）
SUB F8, F10, F14    ; F8 = F10 - F14 ← 与 ADD 的 F8 有 WAR
MUL F6, F10, F8    ; F6 = F10 * F8  ← 与 ADD 的 F6 有 WAW

4.3 三种数据相关

类型	英文	中文	本质	能否消除
RAW	Read After Write	先写后读（真相关）	后面的指令需要前面的计算结果	不能消除，必须等待
WAR	Write After Read	先读后写（反相关）	后面的写可能覆盖前面还需要读的值	可通过寄存器重命名消除
WAW	Write After Write	输出相关	两条指令写同一个寄存器	可通过寄存器重命名消除

RAW 是”要命的”——先写后读必须等他写完。WAR 和 WAW 是”假相关”，换个寄存器就解决了。

4.4 乱序执行中的发射流程

流水线分为三个阶段：

发射（Issue）：从指令队列按序取指令，检查结构冒险，分配到保留站。
执行（Execute）：操作数就绪即可执行（乱序）。
写结果（Write Back）：通过公共数据总线（CDB）广播结果。

五、Tomasulo 算法

5.1 核心思想

由 IBM 360/91 的 Robert Tomasulo 发明，核心创新：

使用保留站（Reservation Station）实现分布式冒险检测。
通过保留站实现寄存器重命名，消除 WAR 和 WAW。
指令在保留站中等待操作数就绪后即可执行。

5.2 硬件结构

Tomasulo 结构包含：

组件	功能
指令队列	按序从 I-MEM 读取指令
保留站（RS）	乘法RS、加法RS、Load/Store缓冲区；存放待执行指令及其操作数状态
功能单元	加法器（2周期）、乘法器（6周期）、除法器（12周期）
寄存器文件	浮点寄存器 F0~F30
公共数据总线（CDB）	结果广播通道，所有保留站和寄存器文件都监听

5.3 保留站字段

字段	含义
Op	操作类型
Vj, Vk	已就绪的源操作数值
Qj, Qk	等待的结果来源（哪个保留站/缓冲区会产生该值）
Busy	该保留站是否被占用

规则：

Q 为 0（或空）：表示对应的 V 值已经就绪，可以使用。
Q 非 0：表示还在等待某个保留站的结果，不能执行。

保留站就像厨房里的备菜架——菜（操作数）到齐了就开始炒，没到就在架子上等着。

5.4 执行流程详解

发射阶段：

从指令队列取出一条指令。
检查对应保留站是否有空位（无空位则暂停发射）。
将指令放入保留站，填写操作数状态：
- 操作数在寄存器文件中已就绪 → 填入 V 列。
- 操作数由某个未完成指令产生 → 在 Q 列标记来源。

执行阶段：

保留站中 Qj = 0 且 Qk = 0 → 两个操作数都就绪 → 送入功能单元执行。
多条指令都就绪时，各功能单元并行执行。

写结果阶段：

功能单元计算完成后，通过 CDB 广播结果。
所有监听 CDB 的保留站检查：如果 Q 匹配，则将结果填入对应的 V 字段。
寄存器文件也同步更新。

5.5 Tomasulo 如何消除假相关

WAW 消除：两条指令写同一个寄存器 → 在保留站中，后面的指令只关心”第几条指令的结果”，而非寄存器名字。最终以最后一条写入为准。
WAR 消除：前面的读操作已经在发射时将值拷贝到保留站的 V 字段中，后面的写不会影响已拷贝的值。

用保留站进行寄存器换名后，WAW 和 WAR 自然而然就消失了。只剩下 RAW 需要真正等待。

5.6 CDB（公共数据总线）的作用

CDB 是单总线，同一时刻只能有一个结果在上面广播。
如果有多个功能单元同时完成，需要仲裁：一个先用，其他等下一个周期。
所有保留站和寄存器文件同时监听 CDB，实现”一次广播、多处接收”。

六、ROB 与精确异常处理

6.1 乱序执行带来的异常问题

乱序执行时，如果一条指令发生异常（如除零、缺页）：

该指令之后的指令可能已经执行完并写回了结果。
从外部看，程序状态不一致——违反了”精确异常”（Precise Exception）要求。

6.2 重排序缓冲区（ROB, Reorder Buffer）

为解决精确异常问题，引入 ROB：

所有指令按原始程序顺序在 ROB 中排队。
指令可以乱序执行，但必须按序提交（Commit）。
只有到达 ROB 头部（前面的指令都已完成）时，才能将结果真正写入寄存器文件或存储器。

6.3 ROB 的提交规则

指令类型	提交行为
普通运算指令	将结果从 ROB 写入寄存器文件
Store 指令	将数据写入存储器
分支指令（预测正确）	正常推进
分支指令（预测错误）	清除 ROB 中该分支之后的所有条目，从正确分支重新执行

ROB 就像一个”排队等出头”的机制——内部随便折腾，但对外只能按顺序交活。万一前面的指令出异常了，后面的结果全部作废。

6.4 带 ROB 的完整流水线

四个阶段：

发射（Issue）：分配保留站 + 分配 ROB 表项。若保留站或 ROB 满，暂停发射。
执行（Execute）：操作数就绪即执行。对于 RAW 依赖，监听 CDB 等待结果。
写结果（Write Result）：结果通过 CDB 写入 ROB（而非直接写寄存器文件）。
提交（Commit）：当指令到达 ROB 头部且执行完毕，将结果提交到寄存器文件/存储器。

6.5 Store 指令的特殊处理

Store 准备好数据后不能立即写入存储器。
必须等到 ROB 头部（按序提交）时才执行实际的存储器写入。
原因：如果前面某条指令出异常，Store 已经修改了存储器就无法撤销。

真要”改变这个世界”（写存储器）的时候，就得小心按顺序来。

七、Tomasulo 算法的练习

7.1 练习配置

典型练习参数：

Load 指令：1 个周期执行。
加法/减法：2 个周期执行。
乘法：6 个周期执行。
除法：12 个周期执行。

7.2 练习方法

对给定的指令序列，逐周期填写：

保留站状态表：每个保留站的 Op、Vj、Vk、Qj、Qk、Busy。
寄存器状态表：每个浮点寄存器当前由哪个保留站/ROB 负责写入。
ROB 状态表：每个表项的指令类型、目的寄存器、值、就绪状态。

关键判断：

检查 Q 字段是否为 0 判断能否执行。
CDB 同一周期只能广播一个结果（优先级仲裁）。
提交必须按 ROB 顺序进行。

八、核心总结

循环展开通过复制循环体减少跳转开销，配合寄存器重命名和指令重排序可实现零停顿（27周期 → 14周期）。
分支预测准确率已达 96%-98%，进一步优化空间有限——体现了 Amdahl 定律的边界思想。
静态调度由编译器完成，简单但受限；动态调度由硬件完成，对软件透明但硬件复杂度高。
乱序执行的核心：按序发射（in-order issue）、乱序执行（out-of-order execution）、按序提交（in-order commit）。
数据相关分三类：RAW（真相关，不可消除）、WAR 和 WAW（假相关，通过寄存器重命名消除）。
Tomasulo 算法通过保留站实现分布式冒险检测和隐式寄存器重命名，消除 WAR/WAW。
ROB（重排序缓冲区）保证按序提交，实现精确异常处理。
CDB（公共数据总线）实现结果广播，让所有等待该结果的保留站同时获得数据。

循环展开优化、Tomasulo乱序执行与精确异常处理