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冒险
保留站比实际寄存器多,因而可以完成优化编译
器所不能完成的一些工作
结果从RS 直接到FU,无需通过寄存器, 而是通过公
共数据总线(Common Data Bus)把结果广播到所有FU
装入(Load)和存储(Stores)也象其他功能部件一
样使用保留站
Tomasulo的结构图
Load
Buffer
FP
Registers
FP Op Queue
Store
Buffer
FP Add
Res.
Station
FP Mul
Res.
Station
Common
Data
Bus
From
MemoryFrom Instruction Unit
Common Data Bus(CDB)
To Memory
Reservation
Station
Operation
Bus
1
2
3
4
5
6
1
2
3
1
2
3
1
1
2
Adders
Multers
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);如果没有将写入寄存器的未决指令,该
域为空