计算机体系结构第四次实验Tomasulo方法实验.doc

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，如下图所示：

在该指令序列中，DIVD指令和最后的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冲突的方法，理解并掌握了寄存器重命名的原理及过程。