推测执行 - 小鱼儿clouding的博客

一、课程回顾：Tomasulo 算法与 ROB

1.1 发展路径

从单周期 → 流水线 → 乱序执行的发展路径：

流水线提速有限，于是引入乱序执行（Out-of-Order Execution）。
为保证乱序执行的正确性，设计了保留站（Reservation Station）作为指令队列。
乱序发射（issue）、顺序提交（commit）需要重排序缓冲区（Reorder Buffer, ROB）。
ROB 使得指令按原始顺序提交，实现精确异常（Precise Exception）——任何指令发生异常时，处理器状态与顺序执行一致。

Tomasulo 练习题结果有时只减少了很少几个时钟周期——”费了这么大劲儿，就这点提升”。但这正是体系结构优化的常态，每一个微小进步在当时都是巨大的创新。

1.2 Tomasulo 硬件代价

乱序执行带来的硬件开销很大：

增加了大量保留站（本质上是寄存器）
增加了CDB（Common Data Bus，公共数据总线）——所有功能单元共享
增加了 Load/Store Buffer
增加了 ROB

1.3 记分板与 Tomasulo 的关系

没有 ROB 的乱序执行方案叫做记分板（Scoreboard）算法。
加了 ROB 之后就是 Tomasulo 算法——指令乱序执行完成后，按顺序从 ROB 中提交，保证精确状态。

1.4 CISC 内部转 RISC

一个重要的工程思想：

RISC（Reduced Instruction Set Computer）指令简单、流水线级数少、主频高，容易添加各种优化逻辑。
CISC（Complex Instruction Set Computer，如 x86/AMD64）指令复杂，直接做乱序执行非常困难。
解决方案：对外提供 CISC 指令集（给编译器/用户用），内部将 CISC 指令翻译为 RISC 微操作（micro-ops）执行。
现代 x86 处理器内部实际上是一个 RISC 内核，流水线通常有十几级。

x86/AMD64 看起来还是 CISC 指令集，但等到了 CPU 内部，实际上已经变成了 RISC 内核。

二、从单发射到多发射

2.1 为什么要多发射

前面的优化（流水线、乱序执行）已经做了，但还不够快。自然的想法是：

既然已经有了乱序执行，指令在 CPU 内部”随便捣鼓”，那能不能一个周期发射多条指令？
条件也成熟了：memory 总线已经是 64 位，一个周期本来就能读两条 32 位指令。

反正都乱序了，也别在乎哪条指令先来后到，多给点指令就行。

2.2 多发射面临的问题

一次发射多条指令并不简单：

数据依赖（Data Dependence）：后面的指令可能依赖前面指令的结果。
结构冲突（Structural Hazard）：多条指令同时需要同一个功能单元。
分支指令：遇到跳转指令时，后续指令是否有效取决于分支结果——预测错了后面全白做。

2.3 保留站对主频的影响

添加保留站等硬件会 slow down max clock frequency（降低最大时钟频率）。这是一个矛盾：

流水线本来就是为了提高主频。
加入乱序执行的复杂逻辑后，关键路径变长，反而可能降低主频。
需要在IPC（每周期指令数）提升与主频下降之间做权衡。

三、超标量与超长指令字

3.1 超标量处理器（Superscalar）

超标量（Superscalar）：每个时钟周期可以发射不固定数量的多条指令（通常 2-8 条）。

指令按序发射（in-order issue），在发射时进行冒险检测（hazard detection）。
根据检测结果决定本周期实际发射几条。
有静态调度和动态调度两种方式。

3.2 超长指令字（VLIW）

超长指令字（Very Long Instruction Word, VLIW）：每个时钟周期发射固定数量的指令，打包成一个”长指令”。

指令长度可达一百多位到几百位。
每个槽位（slot）对应一种功能单元，填什么指令是固定的。
编译器负责分析代码的数据依赖和并行性，将指令安排到合适的槽位。
典型应用：DSP 芯片（如 TI 的数字信号处理器），适合大量规则计算（卷积、傅里叶变换等）。

3.3 超标量 vs VLIW 对比

特性	超标量（Superscalar）	VLIW
每周期发射数	动态决定（不固定）	固定
并行性分析	硬件完成	编译器完成
硬件复杂度	高	较低
编译器复杂度	较低	高
槽位组合	任意组合	固定槽位
典型应用	通用 CPU（Intel/AMD）	DSP、特定领域处理器

“屁股决定脑袋”——做硬件的人希望编译器多干点活，做编译器的人希望硬件自己处理并行性。

四、静态调度超标量示例

4.1 VLIW 循环展开示例

以一个简单循环 x[i] = x[i] + s 为例，假设一个 VLIW 处理器每周期可同时发射 5 条指令（两条访存、两条浮点运算、一条整数/分支）：

循环展开 7 次后：
- 运行时间：9 个时钟周期产出 7 个结果
- 每个结果约需 1.29 个周期
- 平均每周期发射 2.5 条指令（5 个槽位只填充了约一半）

4.2 循环展开的代价

代码膨胀：展开后代码变长，占用更多的指令 Cache 空间。
代码太长会导致指令 Cache 频繁换入换出（thrashing），反而降低性能。
未填充的空槽位浪费了硬件资源。

可以采用智能编码、指令压缩等方法缓解，但做起来又要加很多额外的硬件。

4.3 VLIW 的锁步机制

早期 VLIW 采用锁步（lock-step）机制：任何一个功能单元出现停顿时，整个处理器都要停顿。这是为了实现简单，但在遇到 Cache Miss 时代价巨大。

五、动态多发射与推测执行

5.1 扩展 Tomasulo 算法支持多发射

将 Tomasulo 算法扩展为支持每周期发射两条指令（一条整数/分支 + 一条浮点/访存）：

实际现代处理器一般发射 3-4 条，超过 4 条的不多。
实现方式：可以半个周期发一条（利用时钟两个边沿），或直接加宽总线带宽一次读取多条。

5.2 无推测执行的多发射示例

以一个简单循环（LD → ADD → SD → DADDIU → BNE）为例，展开 3 次（15 条指令），每周期发射 2 条：

第 1 周期：发射 LD 和 DADDIU（无依赖冲突）
第 2 周期：发射 SD 和第 2 轮的 LD
第 3 周期：只能发射 BNE 一条（遇到分支指令不能同时发射下一条）
ADD 指令需要等待 LD 的结果写入 CDB 后才能执行

没有推测执行时，三个循环共 15 条指令需要 19 个时钟周期。

5.3 加入推测执行

有了 ROB，可以大胆进行推测执行（Speculative Execution）。
BNE 指令在第 7 周期执行，没有推测时后续指令必须等到第 7 周期确认分支结果后才能开始。
有推测执行后：BNE 后面的指令可以在第 4 周期就提前发射并执行，不必等分支结果。
如果预测正确，第 8 周期 BNE 提交后，后续指令第 9 周期直接提交。
结果：从 19 个周期降到 14 个时钟周期，节省了 5 个周期。

费了这么大劲儿，用了这么多智慧，就是为了再挤那么一点点的时间。

5.4 推测执行与精确状态

ROB 使得推测执行安全可靠：

推测执行的结果暂存在 ROB 中，不写入体系结构寄存器。
预测正确：按顺序从 ROB 提交到寄存器文件。
预测错误：丢弃 ROB 中的推测结果，从正确分支重新执行。
任何指令发生异常时，其上下文状态与顺序执行完全一致——精确异常。

六、提高取指带宽

6.1 多种提高取指带宽的方法

每个时钟周期提取 4-8 条指令。
利用时钟的上升沿和下降沿（DDR 技术的本质原理）：
- 时钟频率 100MHz，上升沿和下降沿都访问 memory → 等效 200MHz
- 再在两个沿之间插入采样点 → 一个时钟周期取 4 次（四分频）
为什么不直接提高时钟频率？因为频率太高会不稳定（毛刺等问题），所以在不提高时钟频率的前提下”压榨硬件”。

七、分支预测与 BTB

7.1 分支目标缓冲区（BTB）

分支目标缓冲区（Branch Target Buffer, BTB）：

本质是一个查找表：记录历史上遇到的分支指令及其跳转目标地址。
当前 PC 值同时送入指令存储器和 BTB。
如果 BTB 命中且预测为”跳转”，直接从 BTB 获取目标地址，无需等待分支计算。

7.2 BTB 的工作流程

当前 PC 送入 BTB 查找：
- 命中 → 预测为分支指令，直接获取目标地址
- 未命中 → 可能不是分支指令，也可能是新的分支指令
后续执行确认预测是否正确：
- 预测正确 → 继续
- 预测错误 → 不立即删除该项（给一次免费错误机会），类似两位预测器的”宽容”策略
- 新发现的分支指令 → 加入 BTB

7.3 分支预测的代价分析

以一个量化例子说明（参考《计算机体系结构：量化研究方法》）：

预测准确率 90%，BTB 命中率 90%
BTB 命中但预测错误的概率：$0.9 \times 0.1 = 9\%$
不在 BTB 中但实际是分支的概率：$10\%$
总分支代价：$0.09 + 0.1 = 0.19$（约 0.38 个周期的动态代价）

现代高性能处理器的分支预测错误代价约为 15 个时钟周期。前面费了那么大劲攒了几个 clock，一个 Cache Miss 就把几百个周期扔进去了——”千日砍柴一日烧”。

7.4 预测准确率的重要性

现代预测器准确率可达 90%-95%。
代码特征影响预测准确率：大量循环（如图像处理）中的分支几乎都是”跳转”，预测容易；控制流复杂的代码预测困难。

八、寄存器重命名

8.1 为什么需要更大的物理寄存器集

指令集中可见的寄存器数量有限（如 RISC-V 的 32 个通用寄存器），受制于指令编码宽度（32 位中每一位都很宝贵）。
CPU 内部可以使用更大的物理寄存器文件进行寄存器重命名（Register Renaming）。
这是 ROB 的一种替代/补充方法：使用明确的、更大的物理寄存器集合，消除 WAR 和 WAW 冲突。

ISA 限制了你能看到的寄存器数量，但进入 CPU 内部后，用 Tomasulo 的方法重新给它改名就好。

九、指令级并行的极限

9.1 Amdahl 定律回顾

Amdahl 定律（Amdahl’s Law）：如果程序中比例为 $x$ 的部分可以被加速 $n$ 倍，则整体加速比为：

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

当 $n \to \infty$ 时，$S \to \frac{1}{1-x}$。即不可并行的部分决定了加速的上限。

9.2 理想处理器的 ILP 实验

假设一个”理想处理器”：无限寄存器、完美分支预测、完美存储器别名分析、完美缓存。

在这种理想条件下测试不同 benchmark 的 ILP：

条件	每周期可发射指令数上限
理想（无限）	约 75-150（取决于程序）
可实现（64 发射）	约 30-50
实际（4 发射）	约 2-4

9.3 发射宽度的收益递减

从实际数据可以看出：

4 → 8 → 16 发射：性能增长明显
16 → 32 → 64 发射：增长趋缓
64 → 128 → 256：几乎没有额外收益

工程决策方法：盯着性能-成本曲线，找到”拐点”。4 条太少，8 条”咬咬牙也能搞定”，16 条”再去申请点经费”，32 条以上”再给钱也没用了”。

9.4 当前 ILP 的实际水平

到目前为止，ILP 的实际水平是每个周期发射 3-4 条指令。这就是指令级并行的瓶颈。要进一步提升性能，需要从更高层次挖掘并行性——线程级并行（Thread-Level Parallelism, TLP）。

十、线程与进程的区别

特性	线程（Thread）	进程（Process）
内存空间	共享同一内存空间	各自拥有独立的内存空间
数据通信	直接通过共享内存访问	需要通过消息机制（IPC）
通信效率	高	低（打包、协议、解包）
隔离性	弱（需要同步机制）	强（互相不影响）
示例	一个程序内的多个执行流	Word 和浏览器是两个进程

十一、Cache 与存储层次结构预告

指令执行的优化已经提升到一定程度，继续提升收益递减。
真正的瓶颈是访存效率。
一个 Cache Miss 就可能浪费几十到几百个时钟周期，远超指令优化攒出来的那点收益。

多级 Cache 结构：

L1 Cache：速度最快，容量小
L2 Cache：速度次之，容量更大
L3 Cache：速度更慢，容量最大
L4 Cache：极少使用，因为级数太多会使控制逻辑过于复杂

一级不行弄二级，二级不行弄三级，三级再不行——冷静一下，不要四级了。