体系结构13_Tomasulo算法

产生背景

1.IBM 360/91比CDC6600晚三年推出

  -商业计算机使用Cache技术之前

2.整个360系列仅一个指令系统和编译器（公司在上面花了巨大的财力，所以不希望指令系统一直改）

  -要求具有很高的浮点性能，但不是通过高端机器的专用的编译器实现

  -只有四个双精度浮点寄存器，编译器调度的有效性受到很大限制

  -访存时间和浮点计算时间都很长

  -可支持循环的多次迭代重叠执行

Tomasulo算法与记分牌

1.采用了许多记分牌中的理念

2.两个较大的差异

  -Tomasulo算法中，冲突检测和执行控制是分布的，利用保留站实现

  -Tomasulo算法不检查WAR和WAW相关，它们通过算法本身消除掉了

Tomasulo算法在MIPS上实现（改进的MIPS）

1.360/91浮点功能单元

  -3个加法单元

  -2个乘法单元

  -6个读单元

  -3个写单元

2.MIPS和360/91的浮点单元的区别

  360/91：支持 寄存器-存储器指令  MIPS：只支持寄存器-寄存器的指令，对于存储器的访问使用Load/Store来完成

  360/91：采用流水化功能单元，不采用多个功能单元  MIPS：为了简化处理，没有让全部部件流水化，采用多个功能单元的办法

3.每个功能单元都有保留站：缓冲

对于指令，从指令队列中流出后进入各个功能部件。

我们说他有3个加法部件，而实际上只有1个加法器和3个缓冲器。右边的乘法部件也一样，实际上只有1个乘法器和2个缓冲器。左边的3个缓冲器和2个缓冲器构成保留站，分别称之为3个加法保留站和2个乘法保留站。对于指令，从指令队列中流出以后进入加法保留站，就相当于一条加法指令已经流出了。从指令队列角度来看，流出队列进入保留站相当于有3条支路，3个保留站对于指令队列来说相当于有3个加法器，两个保留站相当于2个乘法器，6个Load缓冲相当于6个Load部件，3个Store缓冲，相当于3个Store部件，这些保留站（缓冲）相当于使我们获得了更多的功能部件，这些功能部件并不是真实存在的，所以我们技术上又管这些缓冲器叫做虚拟功能部件。

MIPS浮点单元在Tomasulo算法下执行过程是这样的：一条指令出来之后可能为加法、乘法或者是Store、Load，这些指令出来后被分配到相应的功能部件，这条指令就相当于进入了执行阶段，在每一个保留站中保留指令的操作类型是加法还是减法，

他的两个源操作数将从浮点寄存器中去取，如果就绪了就取过来，没有就绪将记录谁产生这个操作数，一旦取到，寄存器对于加法部件就没有意义了，相当于我们把寄存器释放了。运算完成后会送到一条总线上，这条总线是Tomasulo算法的枢纽，称之为公共数据总线。把数据放在这条总线上后，所有需要这个数据的地方将同时获得这个数据。对于每条指令来说，他的相关检测实在相关保留站中 进行的。他的数据和指针的调整，使得寄存器完成了一次换名的操作。由原来的从寄存器读数改成了从它产生数据的源部件读数。这就完成了一次换名的操作。

MIPS五阶段的流水线的改造

ID和EX阶段被以下三个阶段代替

1.流出（Issue）

2.执行（Execute）

3.结果写回（Write result）

流出

   a. 从浮点指令队列中取出一条指令

   b.如果存在一个空的保留站，就流出这条指令

   c.如果操作数在寄存器中，就送到该指令对应的保留站

   d.存储器取/存指令只要有空闲的缓存就可以流出

   e.如果没有空闲的保留站或者缓存，就存在结构相关，指令暂停，直到有空闲的保留站或者缓存

执行和结果写回

    执行

      1.如果缺少一个或者多个操作数，就监听CBD(公用数据总线)

          这个阶段实际是检测和自动维护RAW（写后读）相关

      2.如果两个操作数都就绪，这条指令就可以执行

   结果写回

       1.如果结果已经产生，将其写到CBD上

       2.通过CDB，把这个结果写到目标寄存器和等待这个结果的所有功能单元的保留站

保留站的六个域

Op:对源操作数S1和S2进行的操作

Qj,Qk:产生本条指令所需要的源操作数的保留站

          如果值为0，意味着源操作数已就绪

Vj,Vk:源操作数的值

           V域和Q域不同时有效

Busy：这个保留站被占用了

寄存器文件和存缓冲都有Qi域

Qi：保留站的编号

    编号所对应产生结果的保留站

    如果Qi为空，就是当前没有指令的结果要写到这个寄存器或者缓冲

Load缓冲和Store缓冲都有

    busy位、地址域、Store域还有V域

实例

整个相关的寻找，编译器首先要完成一个搜索的过程或者由硬件完成，在Tomasulo算法中这个过程是由硬件自动完成的。

有序流出，乱序执行，乱序写回

Tomasulo算法的优点

1.利用分布式硬件冲突检测

2.利用寄存器换名，彻底消除WAW和WAR这两种名相关

3.如果多个保留站等待同一操作数，当操作数在CDB上广播时，它们可以同时获得所需的数据

动态调度方法评价

1.动态方法能够达到很高的性能

2.主要缺陷

    高复杂性：需要大量硬件

    存在瓶颈：单个公共数据总线（CDB）引发竞争（乱序结束的，可能在同一时间同时结束）

          额外的CDB：在每个保留站上需要为每条CDB设置重复的硬件接口

现在的机器上一般有三条CDB，两条局部的，一条全局的，所谓局部数据总线，像浮点有一条（像刚才的MIPS的Tomasulo方法实现的），整数有一条，浮点和整数之间有一条。