托马苏洛算法

Tomasulo算法（托马苏洛算法）是IBM的Robert Tomasulo在1967年研发出来的一种用来改善处理器乱序执行的指令级并行性的硬件算法。

概述

在处理器中，先后执行的指令之间经常具有相关性（例如后一条指令用到前一条指令向寄存器写入的结果），因此早期简单的处理器使后续指令停顿，直到其所需的资源已经由前序指令准备就绪。Tomasulo算法则通过动态调度的方式，在不影响结果正确性的前提下，重新排列指令实际执行的顺序（乱序执行），提高时间利用效率。IBM System/360 Model 91处理器的浮点运算器中率先使用了这种算法。

该算法与之前同样用于实现指令流水线动态调度的计分板不同在于它使用了寄存器重命名机制。指令之间具有数据相关性（例如后条指令的源寄存器恰好是前条指令要写入的目标寄存器），进行动态调度时必须避免三类冒险：写后读（Read-after-Write, RAW）、写后写（Write-after-Write, WAW）、读后写（Write-after-Read, WAR）。第一种冒险也被称为真数据相关（true data dependence），而后两种冒险则并没有那么致命，它们可以由寄存器重命名来予以解决。Tomasulo算法使用了一个共享数据总线（common data bus, CDB）将已计算出的值广播给所有需要这个值作为指令源操作数的保留站。该算法尽可能降低了使用计分板技术导致的流水线停顿，从而改善了并行计算的效率。

具体流程

在指令的发射（issue）阶段，如果操作数和保留站都准备就绪，那么指令就可以直接发射并执行。如果操作数未就绪，则进入保留站的指令会跟踪即将产生这个所需操作数的那个功能单元。如果连可用的保留站功能单元都已经不够用，那么该指令必须被停顿。为了化解读后写（WAR）和写后写（WAW）冲突，需要在该阶段进行指令的寄存器重命名。从指令队列中取出下一条指令，如果其所用到的操作数目前位于寄存器中，那么如果与指令匹配的功能单元（这类处理器通常具有多个功能单元以发挥指令级并行的优势）当前可用，则发射该指令；否则，由于没有可用的功能单元，指令被停顿，直到保留站或缓存可用。尽管执行时可能并未按照指令代码的先后顺序，但是它们在发射过程还是按照原先的顺序。这是为了确保指令顺序执行时的一些现象，例如处理器异常，能够以顺序执行时的同样顺序出现。下一个阶段为执行阶段。在该阶段，指令对应的操作被执行。执行前需要保证所有操作数可用，同时写后读（RAW）冲突已经被化解。系统通过计算有效地址来避免存储区的冲突，从而保证程序的正确性。最后的阶段为写结果阶段，算术逻辑单元（ALU）的计算结果被写回到寄存器，以及任何正在等待该结果的保留站中，如果是存储（store）指令，则写回到存储器中。

相关条目

• 指令级并行
• 乱序执行
• 寄存器重命名
• 计分板 (处理器)
• 重排序缓冲区

外部链接

• Dynamic Scheduling - Tomasulo's Algorithm（页面存档备份，存于互联网档案馆）
• Web based Java demo of Tomasulo's algorithm

学术文献

• An Efficient Algorithm for Exploiting Multiple Arithmetic Units（页面存档备份，存于互联网档案馆）, IBM Journal of Research and Development, 11(1):25-33, January 1967.
• WebHASE: Tomasulo's Algorithm: HASE Java applet simulation of the Tomasulo's Algorithm（页面存档备份，存于互联网档案馆）, Institute for Computing Systems Architecture, Edinburgh University.
• TOMASULO'S ALGORITHM FOR DYNAMIC SCHEDULING（页面存档备份，存于互联网档案馆）
• Computer Architecture: A Quantitative Approach, John L. Hennessy & David A. Patterson