体系结构学习笔记---白话理解Tomasulo算法

乱序执行

1.1 影响流水线性能的因素

       单位时间执行的指令数目是衡量CPU的一项重要指标，为了让各个部件尽量处于工作状态，于是提出了指令流水，但是随之而来的问题就是因为程序之间的相关性，从而引起的流水线堵塞，影响了流水线性能。

       为了进一步提高流水线性能，就提出了乱序执行，也就是部分程序不需按照原先的顺序执行。可以试想，若有一指令执行时间非常长，而后边执行时间短而且操作数都准备就绪的指令和本条指令之间无数据流动，那为何不让后边的提前执行以便更进一步的执行随后的工作呢。这只是一个例子，这种根据组件状态以及判断是否可提前执行的技术就是乱序执行。

1.2 指令相关

•  结构相关：不同指令争用同一功能部件从而引发了冲突。最常用的解决方案就是让产生冲突的指令停顿一个时钟周期，或者直接从硬件上做提升。
•  数据相关：流水线的因为指令重叠，可能改变了对操作数的读写访问顺序，比如以下指令

ADD R1,R2,R3
SUB R4,R1,R5

        ADD指令的写入操作，迟于SUB的读取操作，从而SUB读了错数据。而数据相关就是今天要讨论的重点。

• 控制相关：这个是因为转移指令造成的。 比如以下这段代码，指令流水会同时处理loop和mov指令，但是当loop执行结束，mov指令即使快执行完了也会被撤销掉。这就需要提前判断转移。

mov ax,2	
mov cx,11	
s:add ax,ax
  loop s
mov ax,2

   1.3 数据冲突

    以下讨论几种乱序执行造成的数据冲突。

•   WAR（Write-After-Read）读后写冲突。

SUB F0,F1,F2
ADD F1,F4,F5  //乱序之后SUB指令的F1会读到ADD的结果

• WAW（Write-After-Write）写后写冲突。

SUB F1,F2,F3
ADD F1,F2,F3  //乱序之后，F1存了SUB的运算结果

• RAW（Read-After-Write）写后读冲突。

SUB F1,F2,F3
ADD F4,F1,F5  //乱序之后ADD指令读取的是SUB运算之前的F1

Tomasulo算法

（这里借用一下别人的图片）

简述一下思想的话就是，待执行的指令分为三个阶段，发射，执行，写回。

• 发射：分析指令之后，如果执行该指令的保留站还有空位置，送入相应的保留站，送入的过程中判断一下操作数可不可以读取，如果可以就顺便提前读取（这个读取的过程其实就是相当于给寄存器换了个名字，改真实寄存器为保留站st标号）。
• 执行：如果需要的全部操作数都满足条件了，就执行，否则就继续监听，等待 “写回操作” 的该寄存器的释放信号。
• 写回：通过CDB写回寄存器，顺便发出“广播信号”，告诉别人，我占用的这个寄存器你们可以用了。

1.1 Tomasulo算法的硬件结构

                                                      

• 浮点寄存器：浮点寄存器即是我们指令中要用到的F0,F1,F2,F3。与以往不同的是我们在前边加了一个st。如果他是空的话，表示这个寄存器是可读的，如果里边有数字的话，说明要等待这个数字对应的指令写回才能用。这个数字就对应着乘法保留站或加法保留站前边的1，2，3，4，5，6。
• 保留站：相当于一个“停车场” ，执行前要看下自己的操作数是不是都可用了，如果不可用记录一下要等待谁释放。

1. OP : 操作码
2. $Q_{j}$和$Q_{k}$ : 如果是0的话表示，这个操作数就绪了，如果不是0，里边的数字代表着需要等待谁释放，这个“谁”就是保留站每条记录的编号。
3. $V_{j}$ 和$V_{k}$：表示读到的操作数。

• 结果总线：图中红色的线就是结果总线，可以发现每次运算结束后，不仅要把数据存回寄存器中，还要把结果广播给各个保留站，告诉他们，我这个st编号的保留站占用的数据你们可以用了。

1.2 举个栗子

      还是上边的硬件结构，假设各个寄存器初始的值均为1.0，我们要执行以下代码。

DIV F0,F1,F2  //F0 <- F1 / F2
MUL F3,F0,F2  //F3 <- F0 * F2
ADD F0,F1,F2  //F0 <- F1 + F2
MUL F3,F0,F2  //F3 <- F0 * F2

1. DIV指令发射，发现F1,F2都准备好了。所以乘法保留站会更新为酱事儿的。div表示操作类型，两个0表示数据准备好了，1.0        表示操作数（其实这个过程相当于寄存器重命名了，在数据没准备好的时候“重命名”的意义会体现的更明显）。

    浮点寄存器更新，F0的st标号为3，表示"目前我这个F0大家是不能读取的哈，要等3号保留站记录信号"。

                                            

2. MUL1发射，发现F0需要等待，F2准备好了。所以乘法保留站更新，3表示要等待保留站编号为3的（他上边那一条记录）结果，浮点寄存器同上。

                                                

3. ADD发射，重点来了，他发现F1,F2都准备好了而且加法操作的部件空闲，所以无需等待，可以乱序执行。加法保留栈更新，这时候发现浮点计数器中F0还在等待3的写回，这就是这个算法的灵魂所在，我要覆盖掉之前的st标号，也就是说在真正写回寄存器之前我还得按顺序写回，反正随后3还会广播通知别人更新，那我直接覆盖掉不就完事了嘛，这样就消除了WAW，WAR：

                                                

4. MUL2发射发现，F0要等待加法保留站6号保留站记录的结果，F2直接读取，另外，浮点寄存器F3的等待st标号也要更新为最新的。

                                     

5. 考虑ADD要比DIV快太多了，ADD先写回，通过数据线（红线）广播给浮点寄存器和各个保留站，“兄弟们！你们st号为6的已经被我更新了，你们可以用了！！！”

                                      

6. DIV写回，广播  “兄弟们！你们st号为3的也已经被我更新了，你们可以用了”  。

这时就是“重命名”思想体现的最明显的时候，无论是DIV指令之前的读取还是之后的读取都会得到正确的值。如果是DIV指令之前读F0，那么保留站中记录的是该寄存器准备好了。如果是DIV指令之后读F0，就需要被DIV的广播信号更新。感觉很巧妙^_^