实验2 CPU动态指令调度Tomasulo

一、实验目的

熟悉Tomasulo模拟器同时加深对Tomasulo算法的理解，从而理解指令级并行的一种方式-动态指令调度。

掌握Tomasulo算法在指令流出、执行、写结果各阶段对浮点操作指令以及load和store指令进行什么处理；给定被执行代码片段，对于具体某个时钟周期，能够写出保留站、指令状态表以及浮点寄存器状态表内容的变化情况。

二、实验说明

学习ScoreBoard和Tomasulo算法，并且进行Tomasulo算法的模拟实验，同时熟悉动态指令调度相关知识

三、实验内容

Tomasulo算法模拟器

使用模拟器进行以下指令流的执行并对模拟器截图、回答问题

L.D   F6, 21（R2）
L.D   F2, 0 （R3）
MUL.D  F0, F2, F4
SUB.D  F8, F6, F2
DIV.D  F10,F0, F6
ADD.D  F6, F8, F2

假设浮点功能部件的延迟时间：加减法2个周期，乘法10个周期，load/store2个周期，除法40个周期

问题1：

分别截图（当前周期2和当前周期3），请简要说明load部件做了什么改动

答：

周期2：占用Load2部件，Busy置位；R2就绪，将地址 R[R2]+21 保存在Load1部件的地址寄存器

周期3：第一条LD指令执行完毕，地址 M[R[R2]+21] 计算完成，Load1部件将从存储器读到的值保存在Load1部件寄存器；R3就绪，将地址 R[R3]+0 保存在Load2部件地址寄存器

寄存器重命名：一个新的指令流出，进入保留站之后，它首先就要检查操作数，在寄存器中查看对应的操作数有没有，如果有的话自然万事大吉直接读取就可以，如果是基于其他运算指令得到的，并且还没有完成，寄存器中此时就没有数值，此时对这个操作数进行标记，标记这个计算指令对应的保留站编号，对于源操作数，也需要改写成这个指令的保留站编号，这时就完成了寄存器的重命名。

寄存器重命名的好处在于它允许多个指令并行地使用同一个物理寄存器的多个重命名副本，避免了数据相关性的延迟和资源竞争。这可以提高指令级并行性，并允许更多的指令同时执行，从而提高整体性能。

问题2：

请截图（MUL.D刚开始执行时系统状态），并说明该周期相比上一周期整个系统发生了哪些改动（指令状态、保留站、寄存器和Load部件）

答：

MUL.D刚开始执行时是第六个周期：

其上一个周期为第五个周期：

主要变化如下：

• 指令状态：发射第六条ADD指令，同时第三条、第四条指令进入执行状态
• 保留站：新发射的ADD.D指令占用Add2保留站，进入执行的指令MUL.D和SUB.D开始执行，时间开始倒计时
• 寄存器：新发射的指令ADD.D指令等待F8寄存器，F6的状态变成Busy, 原因是新发射的ADD.D指令写入F6
• Load部件：无变化

Tomasulo算法采用了保守的策略，确保结果先写入寄存器文件或数据存储器，然后在下一个周期才允许其他指令读取这个结果。这样可以确保后续指令读取到的是正确的、已经更新的值，保持数据的一致性。

问题3：

简要说明是什么相关导致MUL.D流出后没有立即执行

答：

因为其所需要的一个操作数F2还没有写回，即与L.D F2 0(R3)之间的RAW相关

Tomasulo算法通过动态调度的方式，将指令按照其操作数的可用性进行调度。当一个指令需要等待一个操作数时，它会被放置在调度队列中，直到所有操作数都可用。这种方式可以有效地隐藏RAW依赖的延迟，因为指令可以在操作数就绪后立即被调度执行。

问题4：

请分别截图（15周期和16周期的系统状态），并分析系统发生了哪些变化

答：

第十五周期：

第十六周期：

主要变化如下：

• 指令状态：
  • 第十五个周期时MULT指令刚执行完毕
  • 第十六个周期时将MULT指令的执行结果写回到F0寄存器中
• 保留站：
  • 第十五个周期时仍在执行MULT指令
  • 第十六个周期时释放保留站，CBD将结果广播到指令DIV.D对应的保留站
• 寄存器：
  • 第十五个周期时F0结果还未写回
  • 第十六个周期时释放保留站，CBD将结果广播到寄存器
• Load部件：无变化

问题5：

回答所有指令刚刚执行完毕时是第多少周期，同时请截图（最后一条指令写CBD时认为指令流执行结束）

答：

所有指令执行完毕是第57个周期，DIV.D是执行的最后一条指令, 在第56个周期执行完毕，在第57个周期开始写结果

四、思考题

问题1：

Tomasulo算法相比Score Board算法有什么异同？（简要回答两点：1.分别解决了什么相关问题，2.两者分别是分布式还是集中式）

答：

Tomasulo

• 特点：分布式；指令状态、相关控制和操作数缓存分布在各个部件中(保留站)
• WAR相关：使用RS的寄存器或指向RS的指针代替指令中的寄存器-寄存器重命名
• WAW相关：使用RS中的寄存器值或指向RS的指针代替指令中的寄存器
• RAW相关：检测到寄存器就绪即没有冲突再读取操作数，进入执行阶段
• 结构相关：有结构冲突不发射
• 结果Forward：从FU广播结果到RS和寄存器

Score Board

• 特点：集中式；指令状态和相关控制都在记分牌处理
• WAR相关：对操作排队，仅在读操作数阶段读寄存器
• WAW相关：检测到相关后，停止发射前一条指令，直到前一条指令完成
• RAW相关：检测到没有冲突(寄存器就绪)再读取操作数，进入执行阶段
• 结构相关：有结构相关不发射
• 结果Forward：写回寄存器接触等待

问题2：

Tomasulo算法是如何解决结构冒险、RAW、WAR和WAW相关的数据冒险？

答：

• 结构相关: 所有功能部件都完全流水化, 功能部件有序访问存储器，有结构冲突不发射
• RAW相关：Tomasulo通过监测Common Data Bus跟踪每个源操作数当前是否可用，仅当所有源操作数可用时才允许指令进入执行阶段
• WAR，WAW相关：Tomasulo使用硬件寄存器重命名技术, 以及在发射阶段时, RS空闲才发射指令和操作数

WAW相关：

Tomasulo算法可以避免WAW相关，原理是前一个指令先进功能单元，紧接着对应的目标寄存器的标识就修改为了这个保留站的编号，接下来，第二个指令进入功能单元，目的寄存器的标识再次修改成第二个，这时即便是第二个指令先完成并写回，前一个指令再算好了也不会改变寄存器了，因为在CDB通知各个功能单元的时候，对应的寄存器只会响应第二个指令完成时传递发出的CDB信号。
举例说明：修改模拟器中的默认指令，将最后的加法指令的目的寄存器调整为F12，此时最后两条指令之间就产生了WAW相关，因为除法指令的执行时间会更长，如果不进行处理的话，就会出现除法指令执行——加法指令执行——加法指令完成写回——除法指令完成写回的情况，那么最后F12的结果就会是除法指令的结果，但是这显然和程序想表达的意思不一致。

而通过使用tomasulo算法，我们可以看到在第五个周期的时候，除法指令流出，进入保留站，F12寄存器保留了除法指令的保留站编号：

在第六个周期的时候，加法指令流出，此时F12的寄存器更改标识为加法指令对应的保留站编号：

那么此时第一条指令什么时候完成就已经不重要了，F12对应的寄存器只会在加法指令完成之后，响应CDB信号读取数据，可以看到在加法指令完成的第十一个周期，寄存器F12中就获取了数据：

而继续执行程序到最后除法指令完成，可以看到最后的除法运算完成之后，F12的寄存器数据也没有改变，说明Tomasulo算法可以处理WAW相关。

WAR相关：

前一个读指令先进保留站，有数据的话是直接从寄存器取，没有的话就是标记上对应的指令的保留站编号，这样一来，后续的写操作的目的寄存器和前一个读的已经不同名了，自然没有影响。

举例说明：添加了两个加法指令，其中第一个指令要读F12寄存器，第二个指令要写F12寄存器，如果没有处理WAR相关，指令乱序执行，就可能会出现因为加法指令完成更快，写回到F12的位置，第一个加法指令读到的是第二个指令的结果，但是实际指令的目的是让它读除法指令的结果，导致WAR相关。

而在Tomasulo算法中，我们可以看到在第五个周期的时候，除法指令流出，目的寄存器F12此时标记的就是这个除法指令的保留站编号，在这里实现了寄存器的重命名：

接下来第七个周期的时候，添加的第一个加法指令流出，此时检查操作数，F4在寄存器中已经有了，所以可以直接读取，F12此时还没有，所以读取的是对应指令的保留站编号并存在保留站中：

在之后是第八个周期，添加的第二个写F12的指令流出，此时因为刚好第四个指令sub指令完成，所以不会存在结构相关的问题，指令直接存放在保留站的第一个位置，并且此时，F12的对应的保留站指令修改为添加的第二个指令：

此时，继续执行到添加的F12写回指令完成：

此时F12也已经有了自己的数据了：

如果没有使用Tomasulo算法，那么可能这个时候添加的第一条指令就会读取走这个F12的数据并且开始执行，但是因为Tomasulo算法的寄存器重命名规则，他的保留站里存的用的操作数是保留站编号为Mult2的指令的结果数据，所以此时不执行，继续等待。

继续执行到除法指令完成：

此时查看保留站，可以看到对应的保留站编号域变更为具体数值域：

接下来开始执行：

这里后面的写指令没有对前面的读指令造成影响，说明Tomasulo算法可以处理WAR相关。

五、实验总结

在进行这个实验的过程中，我深入学习和研究了Tomasulo算法和指令级并行的动态指令调度方法，并通过Tomasulo模拟器进行了实际操作和观察。以下是我在这个实验中的心得体会和收获：

1. 对Tomasulo算法的理解加深：通过实验，我对Tomasulo算法的原理和实现方式有了更深入的理解。我了解了如何使用寄存器重命名、乱序执行和指令调度等技术来实现指令级并行，提高处理器的性能。这个算法的核心思想和设计对于理解现代处理器的工作原理非常重要。
2. 实践操作的重要性：通过使用Tomasulo模拟器，我能够亲身操作和观察指令级并行的过程，这对于加深理论知识的理解非常有帮助。通过在模拟器上进行实验，我能够看到指令之间的依赖关系、执行时间和调度策略对性能的影响，从而更好地理解并行执行的原理。
3. 学以致用：这个实验不仅仅是理论学习，更是将理论知识应用于实际情境的实践。通过实验，我能够更好地将Tomasulo算法应用于指令级并行的场景，并理解其在提高处理器性能方面的作用。这种将理论知识转化为实际应用的能力对于我今后在计算机体系结构和并行计算领域的学习和研究都具有重要意义。

综上所述，通过这个实验，我不仅熟悉了Tomasulo模拟器和动态指令调度的实践操作，还加深了对Tomasulo算法和指令级并行的理解。这个实验为我今后在计算机体系结构和并行计算领域的学习和研究打下了坚实的基础，并培养了我动手实践和团队合作的能力。