Tomasulo算法

为IBM 360/91设计的,在CDC 6600三年之后(1966)

目标:即使在没有特殊编译支持的情况下,也能取

得高性能

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

IBM的每条指令有两个寄存器描述符(register

specifiers),而CDC 6600有三个;

IBM有四个浮点寄存器,而CDC 6600有八个.

Tomasulo算法与记分板

控制&缓冲器分布于功能部件(FU) 与集中于记分板;

功能部件缓冲器称为"保留站(reservation

stations)"; 存放未决的操作数

指令中的寄存器被数值或者指向保留站的指针代替;

这一过程称为寄存器换名(register renaming);

消除WAR,WAW冒险

保留站比实际寄存器多,因而可以完成优化编译

器所不能完成的一些工作

*WAR和WAW：

WAR,WAW实质是命名冲突，而不存在数据依赖，因此通过“换名”即可消除。

例如：S1:MULTD　 　 　 　 F4,F2,F2

S2:ADDD　 　 　 　 F2,F0,F6

看似ADDD的输出因与MULTD输入共用F2，需要等待S1Read后S2才能Write.（WAR）

但如果改为：

S1:MULTD　 　 　 　 F4,F2,F2

S2: ADDD　 　 　 　 F8,F0,F6

即可。

对于WAW,例如

S1: addd F0,F2,F4

S2: multd F2,F6,F8

S3: multd F10,F0,F2

S4: addd F0,F12,F14

S1,S4都写入F0,而中间S3将F0作为输入。

那么S4先运算完后，写入F0，而S3的输入由S1的输出（存于保留站中）提供即可。

结果从RS 直接到FU,无需通过寄存器, 而是通过公

共数据总线(Common Data Bus)把结果广播到所有FU

装入(Load)和存储(Stores)也象其他功能部件一

样使用保留站

Tomasulo的结构图

Tomasulo算法的三段

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

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

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

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

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

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

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

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

标记保留站可用

正常的数据总线:数据+ 目的("去向"总线)

公共数据总线: 数据+ 源("来源"总线)

64位数据+ 4位功能部件源地址

如果与期望的功能部件匹配,就"写"(产生结果)

进行广播

保留站的组成

Op―该部件将完成的具体操作(例如, + or -)

Vj, Vk―源操作数的实际数值

存储缓冲器(Store buffers)设有V域,存放将存储的结果

Qj, Qk―将产生源寄存器值(将写的值)的保留站

注意:没有记分板中的就绪(READY)标志;Qj,Qk=0 ready

存储缓冲器(Store buffers)中只有存放RS产生结果的Qi

Busy―指明保留站或FU 处于忙状态

Register result status―指明哪个功能部件将写到哪

个寄存器(Qi);如果没有将写入寄存器的未决指令,该

域为空