tomasulo算法

Tomasulo算法是由Robert Tomasulo 设计的，因而以他的名字命名。IBM360/91机器中的浮点部件首先采用了这种方法。其核心思想是：记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW（写后读）冲突的可能性减少到最少。通过寄存器换名来消除WAR（读后写）和WAW（写后写）冲突。

历史在CDC 6600三年之后(1966)，为IBM 360/91设计。

目标：即使在没有特殊编译支持的情况下，也能取得高性能。

IBM 360 和CDC 6600指令系统体系结构之间的差异：

IBM的每条指令有两个寄存器描述符(registerspecifiers),而CDC 6600有三个；IBM有四个浮点寄存器，而CDC 6600有八个。1

概述在处理器中，先后执行的指令之间经常具有相关性（例如后一条指令用到前一条指令向寄存器写入的结果），因此早期简单的处理器使后续指令停顿，直到其所需的资源已经由前序指令准备就绪。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）将已计算出的值广播给所有需要这个值作为指令源操作数的保留站。该算法尽可能降低了使用计分板技术导致的流水线停顿，从而改善了并行计算的效率。2

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

保留站控制及缓冲器分布于运算单元(FU) 与Scoreboard；功能部件缓冲器称为"保留站(reservationstations)"; 存放未决的操作数。指令中的寄存器被数值或者指向保留站的指针代替；这一过程称为寄存器换名(register renaming)；消除WAR,WAW冒险保留站比实际寄存器多，因而可以完成优化编译器所不能完成的一些工作。2

结构图Tomasulo算法的三段

1.Issue―从FP Op Queue中取出指令

如果保留站空闲(无结构冒险),

控制机制发射指令&发送操作数(对寄存器进行换名).

2.Execution―对操作数执行操作(EX)

如果两个操作数都已就绪,就执行;

如果没有就绪,就观测公共数据总线等待所需结果

3.Write result―完成执行(WB)

通过公共数据总线将结果写入到所有等待的部件;1

本词条内容贡献者为:

杨晓红 - 副教授 - 西南大学