【计算机组成与体系结构Ⅱ】Tomasulo 算法模拟和分析（实验）

实验5：Tomasulo 算法模拟和分析

一、实验目的

1：加深对指令级并行性及开发的理解。

2：加深对 Tomasulo 算法的理解。

3：掌握 Tomasulo 算法在指令流出、执行、写结果各阶段对浮点操作指令以及 load 和 store 指令进行了什么处理。

4：掌握采用了 Tomasulo 算法的浮点处理部件的结构。

5：掌握保留站的结构。

6：给定被执行的程序片段，对于具体某个时钟周期，能够写出保留站、指令状态表以及浮点寄存器状态表内容的变化情况。

7：理解 Tomasulo 算法消除 WAR 冲突和 WAW 冲突的方法，理解并掌握了寄存器重命名的原理及过程。

二、实验平台

采用 Tomasulo 算法模拟器。

三、实验内容和步骤

3.1：掌握 Tomasulo 算法模拟器的使用方法

运行网络教学平台上的【Tomasulo算法模拟器】，设置浮点功能部件的延迟时间为：加减法 2 个时钟周期，乘法 10 个时钟周期，除法 40 个时钟周期，Load 部件 2 个时钟周期。

1：运行下列代码，给出当指令 MUL.D 写结果时，保留站、Load 缓冲器以及寄存器状态表中的内容。

当MULT.D指令写结果时，保留站、Load缓冲器和寄存器状态表中的内容如下所示：

由上图可知，MULT.D写结果时，保留站Mult1释放，并将其Busy置为No状态；寄存器F0的结果为M5，并在CDB中进行广播，其中M5=M2*R[F4]，即在计算F2*F4时，F4调用R[F4]的结果，而F2调用CDB中M2的结果。

2：按单步方式执行上述代码，利用模拟器的对比显示功能，观察每一个时钟周期前后各信息表中内容的变化情况。

    Cycle 1：L.D F6, 24(R2)进入IS阶段，Load1保留站占用且Busy设置为Yes，地址读入偏移量24，结果寄存器状态表中F6处填入占用的保留站Load1。

Cycle 2：L.D F6, 24(R2)进入EX阶段，地址修改为偏移量24加源寄存器R2指向的地址。L.D F2, 12(R3)进入IS阶段，Load2保留站占用且Busy设置为Yes，地址读入偏移量12，结果寄存器状态表中F2处填入占用的保留站Load2。

Cycle 3：L.D F6, 24(R2)继续停留在EX阶段，计算出偏移地址所存储值的结果，并写入到Load1保留站的值中。L.D F2, 12(R3)进入EX阶段，地址修改为偏移量12加源寄存器R3指向的地址。MULT.D F0, F2, F4进入IS阶段，Mult1保留站占用且Busy设置为Yes，操作码设置为浮点乘法，源寄存器F2未就绪，且应该来源于Load2保留站，源寄存器R4就绪，来源于R[F4]，结果寄存器状态表中F0处填入占用的保留站Mult1。

Cycle 4：L.D F6, 24(R2)进入WB阶段，保留站Load1释放且Busy置为No，结果寄存器状态表中F6填入其计算的结果值为M1并在CDB上广播。L.D F2, 12(R3)继续停留在EX阶段，计算出偏移地址所存储值的结果，并写入到Load2保留站的值中。MULT.D F0, F2, F4由于和L.D F2, 12(R3)存在RAW的数据冲突，且F2暂未计算出结果，因此等待。SUB.D F8, F6, F2进入IS阶段，Add1保留站占用且Busy设置为Yes，操作码设置为浮点减法，源寄存器R6就绪，来源于R[F6]（即M1），源寄存器F2未就绪，且应该来源于Load2保留站，结果寄存器状态表中F8处填入占用的保留站Add1。

Cycle 5：L.D F2, 12(R3)进入WB阶段，保留站Load2释放且Busy置为No，结果寄存器状态表中F2填入其计算的结果值为M2并在CDB上广播。MULT.D F0, F2, F4由于和L.D F2, 12(R3)存在RAW的数据冲突，且F2刚存入结果M2，因此等待。SUB.D F8, F6, F2由于和L.D F2, 12(R3)存在RAW的数据冲突，且F2刚存入结果M2，因此等待。DIV.D F10, F0, F6进入IS阶段，Mult2保留站占用且Busy设置为Yes，操作码设置为浮点除法，源寄存器R0就绪，来源于R[F0]，源寄存器F6就绪，来源于R[F6]，结果寄存器状态表中F10处填入占用的保留站Mult2。

Cycle 6：MULT.D F0, F2, F4进入EX阶段，余下周期Time设置为9，源寄存器R2就绪，来源于M2。SUB.D F8, F6, F2进入EX阶段，余下周期Time设置为1，源寄存器R2就绪，来源于M2。DIV.D F10, F0, F6由于和MULT.D F0, F2, F4存在RAW的数据冲突，且F0暂未计算出结果，因此等待。ADD.D F6, F8, F2进入IS阶段，Add2保留站占用且Busy设置为Yes，操作码设置为浮点加法，源寄存器F8未就绪，且应该来源于Add1保留站，源寄存器R2就绪，来源于M2，结果寄存器状态表中F6处填入占用的保留站Add2。

 Cycle 7：MULT.D F0, F2, F4进入EX阶段，余下周期Time设置为8。SUB.D F8, F6, F2继续停留在EX阶段，计算出浮点减法的结果，并写入到Add1保留站的值中。DIV.D F10, F0, F6由于和MULT.D F0, F2, F4存在RAW的数据冲突，且F0暂未计算出结果，因此等待。ADD.D F6, F8, F2由于和SUB.D F8, F6, F2存在RAW的数据冲突，且F8暂未计算出结果，因此等待。

 Cycle 8：MULT.D F0, F2, F4进入EX阶段，余下周期Time设置为7。SUB.D F8, F6, F2进入WB阶段，保留站Add1释放且Busy置为No，结果寄存器状态表中F8填入其计算的结果值为M3并在CDB上广播。DIV.D F10, F0, F6由于和MULT.D F0, F2, F4存在RAW的数据冲突，且F0暂未计算出结果，因此等待。ADD.D F6, F8, F2由于和SUB.D F8, F6, F2存在RAW的数据冲突，且F8刚存入结果M3，因此等待。

 Cycle 9：MULT.D F0, F2, F4进入EX阶段，余下周期Time设置为6。DIV.D F10, F0, F6由于和MULT.D F0, F2, F4存在RAW的数据冲突，且F0暂未计算出结果，因此等待。ADD.D F6, F8, F2进入EX阶段，余下周期Time设置为1，源寄存器R8就绪，来源于M2。

 Cycle 10：MULT.D F0, F2, F4进入EX阶段，余下周期Time设置为5。DIV.D F10, F0, F6由于和MULT.D F0, F2, F4存在RAW的数据冲突，且F0暂未计算出结果，因此等待。ADD.D F6, F8, F2继续停留在EX阶段，计算出浮点加法的结果，并写入到Add2保留站的值中。

Cycle 11：MULT.D F0, F2, F4进入EX阶段，余下周期Time设置为4。DIV.D F10, F0, F6由于和MULT.D F0, F2, F4存在RAW的数据冲突，且F0暂未计算出结果，因此等待。ADD.D F6, F8, F2进入WB阶段，保留站Add2释放且Busy置为No，结果寄存器状态表中F6填入其计算的结果值为M4并在CDB上广播。

Cycle 12：MULT.D F0, F2, F4进入EX阶段，余下周期Time设置为3。DIV.D F10, F0, F6由于和MULT.D F0, F2, F4存在RAW的数据冲突，且F0暂未计算出结果，因此等待。

Cycle 13：MULT.D F0, F2, F4进入EX阶段，余下周期Time设置为2。DIV.D F10, F0, F6由于和MULT.D F0, F2, F4存在RAW的数据冲突，且F0暂未计算出结果，因此等待。

Cycle 14：MULT.D F0, F2, F4进入EX阶段，余下周期Time设置为1。DIV.D F10, F0, F6由于和MULT.D F0, F2, F4存在RAW的数据冲突，且F0暂未计算出结果，因此等待。

    Cycle 15：MULT.D F0, F2, F4继续停留在EX阶段，计算出浮点乘法的结果，并写入到Mult1保留站的值中。DIV.D F10, F0, F6由于和MULT.D F0, F2, F4存在RAW的数据冲突，且F0暂未计算​​​​​​​
出结果，因此等待。

 Cycle 16：MULT.D F0, F2, F4进入WB阶段，保留站Mult1释放且Busy置为No，结果寄存器状态表中F0填入其计算的结果值为M5并在CDB上广播。DIV.D F10, F0, F6由于和MULT.D F0, F2, F4存在RAW的数据冲突，且F0刚存入结果M5，因此等待。

Cycle 17：DIV.D F10, F0, F6进入EX阶段，余下周期Time设置为39，源寄存器R0就绪，来源于M5。

 Cycle 18：DIV.D F10, F0, F6进入EX阶段，余下周期Time设置为38。

……

Cycle 55：DIV.D F10, F0, F6进入EX阶段，余下周期Time设置为1。

Cycle 56：DIV.D F10, F0, F6继续停留在EX阶段，计算出浮点除法的结果，并写入到Mult2保留站的值中。

Cycle 57：DIV.D F10, F0, F6进入WB阶段，保留站Mult2释放且Busy置为No，结果寄存器状态表中F10填入其计算的结果值为M6并在CDB上广播。

至此，整段代码的运行结束。

3：对于上面相同的延迟时间和代码段：

（1）给出在第3个时钟周期时，保留站、Load缓冲器以及寄存器状态表中的内容。

（2）步进5个时钟周期，给出此时保留站、Load缓冲器以及寄存器状态表中的内容。

（3）再步进10个时钟周期，给出此时保留站、Load缓冲器以及寄存器状态表中的内容。

（1）步进3个周期到Cycle 3时，保留站、Load缓冲器以及寄存器状态表中的内容

（2）前进5个周期到Cycle 8时，保留站、Load缓冲器以及寄存器状态表中的内容

（3）前进10个周期到Cycle 18时，保留站、Load缓冲器以及寄存器状态表中的内容

4：假设浮点功能部件的延迟时间为：加减法3个时钟周期，乘法8个时钟周期，除法40个时钟周期，自己编写一段程序，重复上述步骤（2）的工作，并给出通过此项工作，得出什么结论？

（1）设置指令

（2）设置浮点功能部件延迟时间

（3）执行Tomasula算法

Cycle 1：

Cycle 2：

Cycle 3：

Cycle 4：

Cycle 5：

Cycle 6：

Cycle 7：

Cycle 8：

Cycle 9：

Cycle 10：

Cycle 11：

Cycle 12：

Cycle 13：

Cycle 14：

Cycle 15：

Cycle 15——Cycle 54：DIV.D指令停留在EX阶段

Cycle 54：

Cycle 55：

至此，整段代码的运行结束。

通过此项工作得出的结论：

（1）性能影响。修改延迟时间会影响处理器执行指令的速度。延长延迟会减慢指令执行，而缩短延迟可能加快执行，但这也取决于其他因素，如指令依赖性和资源利用率。

（2）资源冲突和调度。在Tomasulo算法中，资源共享和动态调度是关键。改变延迟时间可能会影响功能单元的利用率和指令的调度顺序，进而影响整体性能。

5：习题4第6题模拟

由于本模拟器未设置Store指令和分支指令，因此无法执行该题目的模拟。

3.2：Tomasula 模拟器的算法分析和实现

1：网络教学平台【Tomasulo-Simulator-java】为java编写的Tomasula算法模拟器，分析该模拟器源代码，要求：

   （1）写出设计思路（模块划分，设计流程）。

   （2）找出对应于发射、执行和写回的代码，对其进行说明和分析。

（1）Tomasula 模拟器的设计思路

    本Tomasula算法模拟器的设计思路如下表所示：

模块划分	设计流程
UI设计	界面面板UI设计与实现，向容器中添加下拉框、按钮等部件，实现页面跳转功能以及面板放置。
指令设置	设置指令选择框（操作码，操作数，立即数等）的default选择，并设置界面默认指令。其中ins_set_panel用于指令设置，EX_time_set_panel用于执行时间设置，ins_state_panel用于指令状态设置，RS_panel用于保留站状态设置，Load_panel用于Load部件设置，Registers_state_panel用于寄存器状态设置。
监听器	监测连接执行不同按钮对应的操作，点击按钮后监听器工作，根据指令初始化其他面板。
Tomasula算法	实现Tomasulo算法，首先对六组指令循环遍历，之后根据发射、执行、写回的流程编写相应的逻辑。包括指令发射操作、保留站的设置、指令执行判断、寄存器操作、保留站操作、Load操作、指令写回操作、计算执行时间操作等。

本Tomasula算法模拟器的UI界面如下图所示：

（2）IS、EX、WB的代码段及其说明分析

IS阶段说明：发射阶段，首先判断指令的流出和执行情况，调用instIssue()方法对空闲的保留站进行遍历并发射指令，若未流出则发射指令。

IS代码段：

//Excute方法中所调用的instIssue指令发射方法     void instIssue(String op, String rd, String rs, String rt)     {         int remain = -1;         //选择空闲的保留站         if (op.equals("ADD") || op.equals("SUB"))         {             for (int i = 1; i < 4; i++)     //对Add1,2,3三个保留站遍历             {                 if (my_rs[i][2].equals("no"))   //空闲                 {                     remain = i;                     break;                 }             }         }         else         {             for (int i = 4; i < 6; i++)     //对Mult1,2两个保留站遍历             {                 if(my_rs[i][2].equals("no"))                 {                     remain = i;                     break;                 }             }         }                 if (remain > 0)     //找到空闲保留站         {             String r = my_rs[remain][1];    //保留站名称             for (int i = 1; i < 17; i++)             {                 //检查第一个操作数是否就绪                 if (my_regsters[0][i].equals(rs)){                     if (my_regsters[1][i].equals("0"))                     {                         //第一个操作数就绪，把寄存器rs中的操作数取到当前保留站Vj                         if(my_regsters[2][i].equals(""))                             my_rs[remain][4] = "R[" + my_regsters[0][i] + "]";                         else                             my_rs[remain][4] = my_regsters[2][i];                         my_rs[remain][6] = "0";     //Qj 置为0                     }                     else    //未就绪                     {                         //寄存器换名，把将产生该操作数的保留站的编号放入当前保留站的Qj中                         my_rs[remain][6] = my_regsters[1][i];                     }                 }                 //检查第二个操作数是否就绪                 if (my_regsters[0][i].equals(rt))                 {                     if (my_regsters[1][i].equals("0"))                     {                         //第二个操作数就绪，把寄存器rt中的操作数取到当前保留站Vk                         if(my_regsters[2][i].equals(""))                             my_rs[remain][5] = "R[" + my_regsters[0][i] + "]";                         else                             my_rs[remain][5] = my_regsters[2][i];                         my_rs[remain][7] = "0";     //Qk 置为0                     }                     else    //未就绪                     {                         //寄存器换名，把将产生该操作数的保留站的编号放入当前保留站的Qk中                         my_rs[remain][7] = my_regsters[1][i];                     }                 }             }                         my_rs[remain][2] = "Yes";   //修改状态为忙碌             my_rs[remain][3] = op;             for (int i = 1; i < 17; i++)             {                 if (my_regsters[0][i].equals(rd))                     my_regsters[1][i] = r;      //目的寄存器状态置为保留站名称             }                     } //      else    //未找到空闲运算保留站 //      { //          System.out.println("未找到空闲保留站。"); //      } //      if (done > 0) //          return true; //      else //          return false;     }

 

EX阶段说明：执行阶段，首先判断是否符合执行的条件，如果符合执行条件则视为准备就绪，此时判断指令类型，并添加时间并计算执行时间。

EX代码段：

//Excute方法中所调用的instExcute指令执行方法，计算执行时间     boolean instExcute(String op, String rd, String rs, String rt)     {         int line = -1;         for (int i = 1; i < 6; i++)             if (my_rs[i][3].equals(op))                 line = i;         //若Time为空，判断运算是否符合执行条件: Qj = Qk == 0         if(my_rs[line][6].equals("0") && my_rs[line][7].equals("0") && ready == 1)         {             //准备就绪，判断指令类型，添加时间             if (op == "ADD")                 my_rs[line][0] = Integer.toString(time[1]-1);             else if (op == "SUB")                 my_rs[line][0] = Integer.toString(time[1]-1);             else if (op == "MULT")                 my_rs[line][0] = Integer.toString(time[2]-1);             else if (op == "DIV")                 my_rs[line][0] = Integer.toString(time[3]-1);             return true;         }         else             return false;     }

WB阶段说明：写回阶段，需要调用instWB指令写回方法，首先遍历等待写回该结果的寄存器，向该寄存器中写入结果，并把该寄存器的状态值置为就绪状态。

WB代码段：

//Excute方法中所调用的instWB指令写回方法     void instWB(String op, String rd, String rs, String rt)     {         int line = -1;         for (int i = 1; i < 6; i++)             if (my_rs[i][3] == op)                 line = i;                 String r = my_rs[line][1];      //保留站名称         for(int i = 1; i < 17; i++)         {             //遍历等待写回该结果的寄存器             if(my_regsters[1][i].equals(r))             {                 //向该寄存器写入结果                 if (op == "ADD")                     my_regsters[2][i] = my_rs[line][4] + "+" + my_rs[line][5];                 else if (op == "SUB")                     my_regsters[2][i] = my_rs[line][4] + "-" + my_rs[line][5];                 else if (op == "MULT")                     my_regsters[2][i] = my_rs[line][4] + "*" + my_rs[line][5];                 else if (op == "DIV")                     my_regsters[2][i] = my_rs[line][4] + "/" + my_rs[line][5];                 my_regsters[1][i] = "0";    //把该寄存器的状态值置为就绪             }           }                 for (int i = 1; i < 6; i++)         {             //遍历等待该结果作为第一个操作数的保留站             if (my_rs[i][6].equals(r))             {                 //向该保留站的Vj写入结果                 if (op == "ADD")                     my_rs[i][4] = my_rs[line][4] + "+" + my_rs[line][5];                 else if (op == "SUB")                     my_rs[i][4] = my_rs[line][4] + "-" + my_rs[line][5];                 else if (op == "MULT")                     my_rs[i][4] = my_rs[line][4] + "*" + my_rs[line][5];                 else if (op == "DIV")                     my_rs[i][4] = my_rs[line][4] + "/" + my_rs[line][5];                 //置Qj为0                 my_rs[i][6] = "0";             }         }                 for (int i = 1; i < 6; i++)         {             //遍历等待该结果作为第二个操作数的保留站             if (my_rs[i][7].equals(r))             {                 //向该保留站的Vk写入结果                 if (op == "ADD")                     my_rs[i][5] = my_rs[line][4] + "+" + my_rs[line][5];                 else if (op == "SUB")                     my_rs[i][5] = my_rs[line][4] + "-" + my_rs[line][5];                 else if (op == "MULT")                     my_rs[i][5] = my_rs[line][4] + "*" + my_rs[line][5];                 else if (op == "DIV")                     my_rs[i][5] = my_rs[line][4] + "/" + my_rs[line][5];                 //置Qk为0                 my_rs[i][7] = "0";             }         }         //释放当前保留站，设置为空闲状态         my_rs[line][0] = "";         my_rs[line][2] = "no";         my_rs[line][3] = "";         my_rs[line][4] = "";         my_rs[line][5] = "";         my_rs[line][6] = "";         my_rs[line][7] = "";     }

2：修改源代码，使其不受代码行数的限制。

首先需要修改指令设置ins_set_panel和指令状态ins_state_panel的长度，并顺带修改core()、Execute()、instIsse()、instExcute()、instWB()等方法的阈值。修改inst_typebox数组的长度为4N-1，指令范围为0至4N-1。最后修改相关for循环的次数为N。

四、实验分析和总结

1：保留站是硬件实现的吗？主要作用是什么？

Tomasulo方法是一种计算机硬件架构的算法，用于动态调度指令的执行，允许乱序执行以及更有效率的使用多个执行单元。因此，保留站是硬件实现的。

保留站的主要作用是保存等待流出和正在流出所需要的操作数，实现了寄存器换名的功能，消除了WAR和WAW冲突。

2：记分牌和Tomasula算法的主要区别一个是集中控制，一个是分布控制。请问Tomasula中是如何实现分布控制的？

在Tomasulo算法中，冲突检测和执行控制是分布的。保留站进行执行控制，每个功能部件的保留站中的信息决定了何时指令可以在该部件中执行，计算结果则通过CDB直接从产生它的保留站传送到所有需要它的功能部件，不需要通过寄存器，从而实现分布控制。

3：寄存器重命名是什么意思？如何实现的？怎样确定要换成哪个寄存器？

寄存器重命名是指用一组临时寄存器来代替原来的寄存器名字，从而让每个指令都有自己独立的目标寄存器。这样就可以避免两个指令之间因为使用同一个寄存器名字而产生的假依赖。

通过使用保留站来提供寄存器重命名，从而消除假依赖和避免WAR和WAW冒险。

如果有一个操作数没有准备好，就一直跟踪生成该操作数的功能单元，监视CDB（公共数据总线），一旦有效则放入等待的保留站，开始执行。写回也是写到CDB中，当等待此结果的功能单元跟踪到之后，即刻写入。

4：乱序完成后会带来什么后果？

    乱序完成会造成WAW冲突，当连续写同一个寄存器时，只有最后一次才能写入。