Tomasulo 算法 — 让 CPU 自己决定指令的执行顺序

待复核

是什么

Tomasulo 算法是 IBM 工程师 Robert Tomasulo 在 1967 年为 System/360 Model 91 设计的一套让 CPU 在运行时动态决定指令执行顺序的方法。日常类比：像一个高效的厨房——配菜员（CPU 前端）按菜单顺序写单，但灶台（执行单元）谁的食材先备齐谁先开火，不必死等菜单顺序。

你写一段普通代码：

a = b + c;
d = e + f;
g = a + d;

按”先写先做”的死板规则，第三行得等前两行都算完。Tomasulo 让 CPU 看出”前两行互不依赖”，同时送进两个加法器一起算，第三行等结果广播回来再算。三步可能压成两步。

这套机制的三大件——保留站（reservation station）、寄存器重命名（register renaming）、公共数据总线（CDB）——构成了现代超标量乱序 CPU 的核心骨架。Apple M 大核、x86 Zen、ARM Cortex-X / 高端乱序 Cortex-A 都是 Tomasulo 的徒孙（同系列里的 A53/A55 等顺序核不算）。

为什么重要

不理解 Tomasulo，下面这些事都没法解释：

为什么现代 CPU 主频卡在 5 GHz 二十年，性能却年年涨——靠同时跑多条指令而不是更快跑一条
为什么 CPU benchmark 经常出现”实际 IPC 大于 1”——一个时钟周期跑完不止一条指令，靠的就是乱序发射
为什么编译器优化和 CPU 调度看起来在做重叠的事——编译器是静态调度，CPU 是动态调度，互补不替代
为什么 Spectre / Meltdown 会出现在 2018——乱序/投机执行谱系上的后代：错预测路径留下的微架构痕迹（如 cache）可被侧信道读走，不是 1967 原文本身的设计目标

核心要点

Tomasulo 解决的核心问题是数据冲突，分三类：

RAW（读后写，read-after-write）：真依赖。下一条要读上一条写的值，必须等。
WAR（写后读）和 WAW（写后写）：假冲突。只是因为两条指令偶然用了同一个寄存器名。

算法三大件如何配合：

保留站：每个执行单元（加法器、乘法器）前面挂一个等待区，存放”已经发射但操作数没全到位”的指令。类比：餐厅每个灶台旁的备餐台，菜单已经下了，但还在等某个食材。
寄存器重命名：当一条指令要写寄存器 R5，CPU 不真写 R5，而是把这条指令所在的保留站编号当作 R5 的”临时身份证”（tag）。后面所有读 R5 的指令记住这个 tag。WAR / WAW 假冲突自动消失——因为每次写都换新身份。
公共数据总线 CDB：执行单元算完后，把 (tag, 结果值) 广播到所有保留站。谁的等待格里写着这个 tag，谁就把它替换成具体值，操作数齐了立刻发射。

整个过程没有”等前一条指令算完”这种线性逻辑，只有”我等的 tag 到了没”。

实践案例

案例 1：假冲突如何消失

i1: R1 = R2 + R3
i2: R1 = R4 + R5

按朴素流水线，i2 要等 i1 写完 R1 才能写——这是 WAW 假冲突。Tomasulo 的做法：

i1 发射时分到保留站 RS1，R1 临时身份变成 tag=RS1
i2 发射时分到保留站 RS2，R1 临时身份立即被覆盖成 tag=RS2
两条指令在不同物理位置并行算，互不影响

后续读 R1 的指令拿到的永远是最新的 tag，正确性保住了。

案例 2：CDB 怎么唤醒等待者

i1: R3 = R1 * R2     (慢，乘法 4 周期)
i2: R5 = R3 + R4     (依赖 i1 的结果)

时间线：

周期 1：i1 进乘法器保留站，i2 进加法器保留站，i2 的第一个操作数标记为 等 tag=RS_mul
周期 2-4：乘法器在算，i2 在保留站睡觉
周期 5：乘法器算完，把 (tag=RS_mul, 值=42) 广播到 CDB
周期 5 同周期：i2 的保留站监听 CDB，看到自己等的 tag 来了，把 42 填进操作数槽，下周期发射

i2 没有反复轮询，是 CDB 主动喊它。

案例 3：一条指令在现代核里走完

以 R3 = R1 * R2 为例，跟读四步（名字是后人加的，骨架仍是 Tomasulo）：

发射：前端按程序序取指；重命名表给 R3 换一个新物理寄存器身份（像换临时工号），指令进 Scheduler（保留站的现代名）
等待：若 R1/R2 还没就绪，指令在 Scheduler 里睡；谁算完谁经 Result Bus（CDB 升级版）广播 tag+值
执行：操作数齐了就进乘法器；算完再广播，唤醒下游
提交：结果先记在 Reorder Buffer（ROB，1988 年补上）里；按原程序序提交，异常时能回到”精确状态”（像账本按页回滚，不是算到哪算到哪）

Physical Register File（PRF）就是那一大堆”临时工号”对应的真实格子。骨架没变，规模大了几十倍。

踩过的坑

ROB 不是 Tomasulo 原始设计：原版没有重排序缓冲区，遇到异常无法精确恢复。Smith & Pleszkun 1988 年才加 ROB。读老论文别把后人的优化算成原作者的功劳。
CDB 是单总线瓶颈：每周期最多广播一个结果。多个执行单元同时算完会排队。现代 CPU 用多条 CDB 或更复杂的 forwarding network 解决。
WAR / WAW 假冲突容易误以为真：教学时经常被当成”必须等”。其实它们只是寄存器名复用，重命名后完全消失，真依赖只有 RAW。
静态 vs 动态调度不是替代关系：编译器可以重排指令（静态调度），CPU 又可以乱序发射（动态调度）。两者是叠加优化，不是二选一。VLIW 架构（如 Itanium）赌”全靠编译器”，结果失败——因为编译时不知道 cache miss 等运行时信息。
投机执行把乱序推远了才冒出 Spectre：错预测路径也会往前算，回滚却常不擦 cache，侧信道可读残留——这是谱系后代的副作用，不是 1967 原文要解决的问题。

适用 vs 不适用场景

适用：

通用 CPU 乱序大核（Apple M、x86 P-core、ARM Cortex-X / 高端 Cortex-A）—— 主流方案
FPGA 软核里的乱序实现（如 BOOM）—— 直接以 Tomasulo 为蓝本，便于对照论文读 RTL

不适用：

嵌入式/低功耗核 —— Cortex-M、A53/A55 等顺序流水线；乱序要付 ROB + 重命名表 + 唤醒网络的面积/功耗，同工艺下往往换不回性能
VLIW / DSP —— 调度丢给编译器，硬件极简
GPU SIMT —— 用大量线程藏延迟，一般不靠单线程保留站式乱序（独立线程调度 ≠ Tomasulo）

历史小故事（可跳过）

1964 年：IBM System/360 Model 91 项目启动，要做”科学计算最快的机器”，浮点单元慢于整数单元，需要并行流水。
1967 年：Tomasulo 在 IBM Poughkeepsie 发表 8 页论文，全文没有”register renaming”这个词，但思想已经完整。
1968-1990：算法被搁置 20 年——Model 91 太贵，只造了 20 台；后来 RISC 兴起，业界相信”简单流水线 + 编译器优化”够用。
1995 年：Intel Pentium Pro 把 Tomasulo 思想搬到 x86，开启乱序时代。从此每代 Intel/AMD/ARM 大核都是 Tomasulo 派。
2020 年代：Apple M1 Firestorm 核 ROB 深度 630+，保留站规模空前，本质仍是 1967 年那张图。

一篇 8 页论文，等了 28 年才被工业界完全接受。

学到什么

假冲突可以重命名消除——这是过去 60 年体系结构最重要的一个洞见之一
保留站 + 重命名 + 广播总线 是动态调度的三板斧，组合起来威力惊人
静态信息 vs 动态信息：编译器看不到 cache miss，CPU 看不到全局优化，两者必须互补
超前发明的代价：1967 年的算法，工业界 1995 年才真正吃透；好想法常需要等硬件密度跟上

关联

ssa —— 静态单赋值，编译器 IR 用一次写一个新名字消除假依赖，与寄存器重命名同构
hotspot-server-compiler —— JVM 的 C2 编译器在 IR 层做静态调度，与 CPU Tomasulo 互补
self-pic —— 内联缓存，CPU 投机思想在动态语言运行时的对应物
tracemonkey —— 只编译”真的走过的那条路”，与乱序投机执行精神相通
ampere-architecture-2020 —— GPU 用线程藏延迟，对照 CPU 单线程 Tomasulo 乱序

反向链接

case-for-risc-1980 —— Case for RISC 1980 — 一篇没有芯片的论文，掀起 CPU 半世纪革命
multics-1965 —— MULTICS 1965 — 把计算机做成像电力一样的公共服务
risc-i-1981 —— RISC I — 砍掉 90% 指令反而让 CPU 跑得更快