Tomasulo算法原理是什么

Tomasulo算法

　　为IBM360/91设计的,在CDC6600三年之后(1966)

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

　　得高性能

　　IBM360和CDC6600指令系统体系结构之间的差异

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

　　specifiers),而CDC6600有三个;

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

　　Tomasulo算法与记分板

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

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

　　stations);存放未决的操作数

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

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

　　消除WAR,WAW冒险

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

　　器所不能完成的一些工作

　　*WAR和WAW：

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

　　例如：S1:MULTDF4,F2,F2

　　S2:ADDDF2,F0,F6

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

　　但如果改为：

　　S1:MULTDF4,F2,F2

　　S2:ADDDF8,F0,F6

　　即可。

　　对于WAW,例如

　　S1:adddF0,F2,F4

　　S2:multdF2,F6,F8

　　S3:multdF10,F0,F2

　　S4:adddF0,F12,F14

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

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

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

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

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

　　样使用保留站

　　Tomasulo的结构图

Tomasulo

Tomasulo算法的三段

　　1.Issue―从FPOpQueue中取出指令

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

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

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

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

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

　　3.Writeresult―完成执行(WB)

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

　　标记保留站可用

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

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

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

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

　　进行广播

　　保留站的组成

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

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

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

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

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

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

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

　　Registerresultstatus―指明哪个功能部件将写到哪

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

　　域为空