面对 CDC 6600 的竞争，Robert Tomasulo 为 IBM Model 91 设计了动态调度算法

在上一篇 CDC 6600 的文章里，我们讲了 Seymour Cray 和 James Thornton 如何用紧凑布线、外围处理器和记分板，把多个功能单元组织起来，造出了当时最先进的超级计算机。

那篇文章还留下了另一条线索：IBM 曾发布与 CDC 6600 竞争的 Model 92，但最终未能按原计划交付。经过调整后，IBM 在 1967 年交付 Model 91。

Model 91 的浮点单元目标也是让多个运算部件同时工作，但 IBM 面临另一道约束：System/360 的指令集只提供 4 个架构浮点寄存器。如果程序反复使用同一个寄存器，原本彼此独立的运算也可能因此互相等待。

负责浮点单元设计的 Robert Tomasulo 为此设计了一套动态调度机制。它让指令等待真正需要的数据，同时减少寄存器重复使用造成的停顿。

从 Model 92 到 Model 91

IBM 在 1961 年启动了代号为 Project X 的高性能计算机研究计划，后来将它纳入 System/360 体系。1963 年，CDC 发布了 6600；IBM 董事长小托马斯·沃森在内部备忘录里追问，为什么对手能够率先推出更强大的机器。

IBM 随后在 1964 年公布了 Model 92。该型号最终没能按照原计划交付。IBM 后来推出了使用磁芯存储器的 Model 91 以及使用薄膜存储器的 Model 95。

但是这台机器总共只制造了 15 台，其中 4 台还留在了 IBM 内部。

IBM System/360 Model 91，摄于 1960 年代。Source: NASA，摄影者未署名，Public Domain，经 Wikimedia Commons 获取。

虽然 Model 91 的制造数量有限，但其浮点单元为动态调度和寄存器重命名提供了影响后世的思路。要看清 Model 91 做了什么，还得先回到 CDC 6600 的记分板功能。

记分板能解决什么，又解决不了什么

上一篇讲过，CDC 6600 有多个功能单元：有的负责加法，有的负责乘法和除法。它们可以同时工作，不必让一条缓慢的除法指令挡住所有计算。

协调这些部件的是记分板（Scoreboard）。它检查部件是否空闲、指令所需的数据是否准备好，再让符合条件的运算继续。指令按顺序发出，但开始计算和完成的顺序可以不同。

但有些等待并非源于真正的数据依赖。

假设一条指令需要前一次除法的结果，那么它必须等到除法完成。这是必要的等待：数据还没算出来。

另一种情况是，两条本来互不相关的指令，恰好使用了同一个寄存器。寄存器是处理器中用于暂存数据的小空间；如果后面的指令要将新数据写进去，而前面的指令还需要旧数据，硬件就得让它等一等。

这里限制并不来自计算本身，而是来自两条指令使用了同一个位置。记分板能发现冲突并阻止错误，但它通常需要通过等待来处理这类冲突。Thornton 在 CDC 6600 设计著作中详细描述了这些检查。

程序绘制的教学动画（Illustration）。早先的指令还在等除法结果，因此尚未读取寄存器 R 中的旧值 10；后来的指令虽然已算出 99，也必须等旧值被读走后再写入。数值用于示意，不是原机测试数据。 三图均为基于 Tomasulo 原论文与 Thornton 原著的简化说明，不代表精确时序或完整硬件拓扑。

IBM 只有四个浮点寄存器

这种问题对 IBM 尤其棘手。System/360 家族需要维持软件兼容性，但其指令集只提供 4 个浮点寄存器，编号分别为 0、2、4、6。程序中的浮点计算反复使用这些名字，很容易导致寄存器空间被重复占用。

IBM System/360 Model 91 控制台，2007 年摄于计算机历史博物馆。Photo by Carlo Nardone，CC BY-SA 2.0，经 Wikimedia Commons 获取；仅缩小尺寸。

想象一个程序要处理一串数字：先把第一个数字装进寄存器，完成乘法，再保存结果；接着处理第二个数字。即使两次乘法处理的是不同数字，程序也可能因为复用了同一个寄存器名字而产生等待。

等待并不意味着机器永远停住，也不代表所有部件都无法工作。但当昂贵的运算部件有能力继续工作、却因为这些名字冲突而闲置时，机器就浪费了本可利用的并行能力。

Tomasulo 要解决的问题是：能否让硬件记住每条指令真正需要哪个数据，而不是只盯着程序反复使用的寄存器名字？

给等待中的数据贴上标签

1967 年，Tomasulo 在《IBM Journal of Research and Development》发表了论文 《An Efficient Algorithm for Exploiting Multiple Arithmetic Units》，介绍 Model 91 浮点单元采用的方法。

他的办法可以分成三步。

第一，将暂时无法计算的指令放到运算部件前面的保留站（Reservation Station）。那里可以保存指令，也可以等待它所需的数据。Model 91 的加法单元前有三个保留站，乘除单元前有两个；后者共享一个乘除执行单元，不能同时执行两次乘除。

第二，给尚未算出的结果贴上标签。指令进入保留站时，如果所需数据已准备好，则保存该值；如果数据仍在计算中，则记录负责生成它的部件标签。

程序绘制的教学动画（Illustration）。F0 先指向生产者 A，随后被新指令改为指向 B；早先的消费者仍记得自己等待 A。A 的结果到达时，消费者接收它，但结果不能覆盖已改挂 B 标签的 F0。 三图均为基于 Tomasulo 原论文与 Thornton 原著的简化说明，不代表精确时序或完整硬件拓扑。

第三，结果算出后，通过通用数据总线（Common Data Bus，CDB） 发送结果和标签。等待该结果的部件在看到匹配的标签后接收数据；至于何时开始下一步运算，则取决于其他数据是否就绪、运算单元是否空闲。

程序绘制的教学动画（Illustration）。A 广播结果 6，两个等待 A 的消费者都能接收；等待 B 的消费者继续等待。收到结果并不保证立即开始计算。 三图均为基于 Tomasulo 原论文与 Thornton 原著的简化说明，不代表精确时序或完整硬件拓扑。

这样，即使后面的指令重新使用了同一个寄存器名字，先前的指令仍然知道自己等待的是哪一个结果。硬件把程序里有限的寄存器名字，与尚在计算中的不同结果区分开来。这就是寄存器重命名的核心思路。

需要强调的是，重命名不能消除所有等待：如果后一个计算确实需要前一个计算的结果，它仍然必须等。它消除的是寄存器名字重复使用带来的部分假相关，而硬件资源占用和数据传输也会造成等待。

Tomasulo 在论文里分析了一个内层循环。在论文的比较条件下，不使用 CDB 时，一轮需要 17 个时钟周期；使用 CDB 后只需要 11 个时钟周期。这是针对该例子的理论分析，不能直接作为所有程序的实测结果。

商业沉浮与微处理器时代的文艺复兴

然而，商业与工程制造的残酷现实并未给 Model 91 铺就坦途。

Model 91 采用 IBM 的 ASLT（Advanced Solid Logic Technology）高速逻辑电路，机器周期为 60 纳秒。设计还需处理存储器与处理器之间的速度差距。IBM 功能手册

与此同时，1968 年 CDC 对 IBM 提起了私人反垄断诉讼，诉讼最终于 1973 年和解；现有资料不足以证明该诉讼导致 Model 91 停产。Model 91 最终只生产了 15 台。这个数量没有形成广泛的装机基础。

这套写进论文的动态调度思路，后来也出现在微处理器设计中。

转机发生在摩尔定律狂飙的 1990 年代。

随着半导体工艺的进步，微处理器能够容纳更多的晶体管。设计者也在探索如何利用更多指令级并行，并应对运行时才能确定的依赖和延迟。

硬件动态调度成为处理器设计者采用的一条路径。

由 Robert Colwell 领导的 Intel P6 团队，在设计 1995 年问世的 Pentium Pro 时，也需要处理有限的寄存器数量和复杂的指令集：当时的 x86 架构提供 8 个通用寄存器。

P6 延续了动态调度和重命名的思路： 他们在前端设计了译码器，将复杂的 x86 CISC 指令切碎为精简的微操作（μops）；随后，这些微操作被送入拥有 20 项条目的保留站（Reservation Station）进行动态发射。P6 还使用 重排序缓冲区（Reorder Buffer, ROB），使微操作可以乱序执行，并按程序顺序退休（In-order Retirement）。P6 微架构论文

后来的处理器也采用了不同的组织方式。以 MIPS R10000 为例，它采用物理寄存器堆（Physical Register File, PRF）保存重命名结果，执行单元直接读写这些寄存器。设计者论文

许多现代高性能处理器仍使用动态重命名消除寄存器假相关，并根据数据就绪情况调度指令。它们的调度器、寄存器堆和结果转发网络，在具体实现上已经各不相同。

1997 年，IEEE 计算机学会与 ACM 将埃克特-莫克利奖（Eckert-Mauchly Award） 授予了 Robert Tomasulo，以表彰 Tomasulo 算法对乱序执行处理器设计的贡献。

虽然 Model 91 只造了 15 台，但它对操作数等待、结果广播和寄存器重命名的处理，为后来的处理器设计留下了一套可以继续发展的思路。