Tomasulo方法实验姓名：王宇航学号：09283020
Tomasulo方法实验
一、实验目的：
通过本实验，理解指令流水化过程中乱序执行和寄存器重命名方法。
二、实验内容：
1、用dlxView模拟器或Tomasulo算法模拟器执行浮点指令程序段。
2、指出指令乱序执行和寄存器重命名过程。
三、实验环境
操作系统：Windows 7 旗舰版
处理器：Intel(R) Core(TM) i3 双核
内存：2.00GB
软件：Tomasulo算法模拟器
四、实验过程：
1、设置Tomasulo算法模拟器参数
其中Load部件的执行时间不能
设置为1，至少为2，故不作修改；
加/减法部件的执行时间为4个时钟
周期，乘法部件的执行时间为7个
时钟周期，除法部件的执行时间为
15个时钟周期。
2、分析Tomasulo算法模拟器中指令乱序执行过程
Tomasulo算法模拟器中默认设置的指令下图所示：
执行该指令序列，重点观察指令状态的写结果一栏，便会发现执行过程中存在乱序执行现象，共有两处乱序执行，分别如下列图所示：
图中显示，在第10周期时，位于MULT.D指令之后的SUB.D指令经过4个周期已经执行完成并已经将结果写回寄存器，而MULT.D指令仍在执行中。
在第13周期时，MULT.D指令经过7个周期执行完毕，才将结果写回。
此外，还可以看到，位于DIV.D指令之后的ADD.D指令在第11周期时就已经开始执行，而DIV.D指令直至现在都未开始执行。
在第15周期时，ADD.D指令经过4个周期执行完毕，先于DIV.D指令写回结果；而DIV.D 指令仍在执行中。
在第29周期时，DIV.D指令经过15个周期终于执行完毕，将结果写回寄存器。
以上分析证明，在Tomasulo算法中存在乱序执行并且不会影响执行结果的正确性。
这是因为，Tomasulo算法采用分布的保留站，冲突检测和指令执行控制是分布的。
3、分析Tomasulo算法模拟器中寄存器重命名过程
在Tomasulo算法中通过寄存器重命名来消除WAR冲突，这一过程是通过保留站来完成的。
当指令流出到保留站时，若其操作数已经就绪，则将该指令中相应的寄存器号换为该数据本身；若其操作数还未计算出来，则将该指令中相应的寄存器号重命名为将产生这个操作数的保留站的标识，从而使得该指令与此寄存器不再有关系，后面指令对此寄存器的写入操作也不可能对该指令造成WAR冲突了。
（1）将指令中相应的寄存器号换为数据本身
执行Tomasulo算法模拟器中默认设置的指令序列，容易看出最后一条指令ADD.D和前一条指令DIV.D之间存在一个WAR冲突，即DIV.D指令要读寄存器F8中的值，ADD.D要写寄存器F8中的值，由于乱序执行，ADD.D指令会先于DIV.D指令完成；但是执行结果却不会发生错误，是因为Tomasulo算法通过寄存器重命名将这一冲突消除了。
可以看到在第5周期时，DIV.D指令流出到保留站中，此时F8中的值已经由前面的L.D 指令得出，为M1，但是模拟器并没有将相应的寄存器号R[F8]写入Vk字段中，而是将其换为了F8中数据本身M1，从而使得该指令与寄存器F8不再有关联，无论后面指令怎样改写F8也都不会影响该指令的正确执行了。
此外，由于前面的MULT.D指令还未得出F2的值，故DIV.D指令将寄存器F2重命名为MULT.D指令的保留站标识Mult1，写入Qj字段中。
如下图所示：
在这个周期中，ADD.D指令已经执行完毕，并且已经将寄存器F8中的值由M1改写成了M5，但此时DIV.D指令仍在正确执行着，并没有发生任何错误，并且经过15个执行周期可以正确完成执行过程，第15周期如下图所示：
由此说明了将指令中相应的寄存器号换为数据本身这一寄存器重命名的方法成功地消除了WAR冲突。
（2）将指令中相应的寄存器号重命名为将产生该操作数的保留站的标识
对Tomasulo算法模拟器中默认设置的指令进行重排，将第一条L.D指令后移两个位置，重排后的指令如下图所示：
可以看到，在该指令序列中，最后一条指令ADD.D和前一条指令DIV.D之间仍然存在一个WAR冲突。
执行该指令序列，观察执行过程。
可以发现在第5周期时，DIV.D指令流出到保留站中，而此时前面的L.D指令还未得出F8的值，但是模拟器并没有将相应的寄存器号R[F8]写入Vk字段中，而是将其换为了L.D指令的保留站标识Load2写入了Qk中，从而使得该指令与寄存器F8不再有关联，无论后面指令怎样改写F8也都不会影响该指令的正确执行了，如下图所示：
对寄存器F2的处理和前一种情况的相同。
在第6周期时，保留站Load2完成计算，得出F8的值M2，就会通过CBD将F8的值直接传送到DIV.D指令的保留站Mult2的Vk字段中，如下图所示：
在第12周期时，MULT.D指令得出F2的值后也会通过CDB将其直接送到DIV.D指令的保留站中，DIV.D指令便可以开始执行了。
（3）分析WAW冲突的消除方法
寄存器重命名方法不仅可以消除WAR冲突，还可以配合使用对目标寄存器的预约方法消除WAW冲突。
这一方法的思想是，在一条指令流出到保留站时，将结果寄存器的Qi字段设置为该指令的保留站标识，表示结果寄存器将要接收该指令的结果，这样其实相当于提前完成了写操作。
由于指令是按程序顺序流出的，当出现多条指令写同一个结果寄存器时，最后留下的预约结果必定是最后一条指令的，因此能够消除WAW冲突。
为了演示消除WAW冲突的过程，改写上述指令的最后一条指令，将目标寄存器由F8改为F12，如下图所示：
在该指令序列中，DIV.D指令和最后的ADD.D指令之间存在WAW冲突，即DIV.D指令要写寄存器F12，ADD.D指令也要写寄存器F12，由于乱序执行，ADD.D指令会先于DIV.D指令完成，写结果至寄存器F12。
若没有任何防范措施，当DIV.D指令完成后又会写其执行结果至寄存器F12，修改刚才的ADD.D指令的执行结果，导致结果错误。
但Tomasulo算法通过寄存器重命名和对目标寄存器的预约方法将这一冲突消除了。
执行修改后的指令序列，观察执行过程。
可以看到，在第5周期时，DIV.D指令流出到保留站中，同时将寄存器F12的Qi字段中设为DIV.D指令保留站的标识Mult2，完成预约工作。
如下图所示：
在第6周期时，ADD.D指令流出到保留站中，同时将寄存器F12的Qi字段中改写为该指令保留站的标识Add2，这样就表示寄存器F12最后接收的是ADD.D指令的执行结果，即使DIV.D指令在ADD.D指令之后执行完，也无法再改写寄存器F12了，从而保证了F12中结果的正确性。
如下图所示：
为了验证这一方法的有效性，可以看一下第16周期和第28周期。
在第16周期，ADD.D 指令先于DIV.D指令完成执行过程，将结果写入寄存器F12中，值为M5；在第29周期，DIV.D 指令也完成执行过程，但是再也无法写寄存器F12了，F12中的值仍然为ADD.D指令的执行结果M5，如下图所示：
第16周期
第28周期
由此说明寄存器重命名和对目标寄存器的预约方法成功地消除了WAW冲突。
五、实验总结：
本次实验主要是借助Tomasulo算法模拟器理解指令流水化过程中乱序执行和寄存器重命名方法。
通过在Tomasulo算法模拟器执行存在WAR冲突或者WAW冲突的浮点指令程序段，分析其中的乱序执行现象和寄存器重命名过程，我理解了Tomasulo算法消除WAR冲突和WAW冲突的方法，理解并掌握了寄存器重命名的原理及过程。
