国家建筑网站,海南最新政策,站酷app,浏阳网页设计实验5#xff1a;Tomasulo 算法模拟和分析
一、实验目的
1#xff1a;加深对指令级并行性及开发的理解。
2#xff1a;加深对 Tomasulo 算法的理解。
3#xff1a;掌握 Tomasulo 算法在指令流出、执行、写结果各阶段对浮点操作指令以及 load 和 store 指令进行了什么处…实验5Tomasulo 算法模拟和分析
一、实验目的
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中进行广播其中M5M2*R[F4]即在计算F2*F4时F4调用R[F4]的结果而F2调用CDB中M2的结果。 2按单步方式执行上述代码利用模拟器的对比显示功能观察每一个时钟周期前后各信息表中内容的变化情况。 Cycle 1L.D F6, 24(R2)进入IS阶段Load1保留站占用且Busy设置为Yes地址读入偏移量24结果寄存器状态表中F6处填入占用的保留站Load1。 Cycle 2L.D F6, 24(R2)进入EX阶段地址修改为偏移量24加源寄存器R2指向的地址。L.D F2, 12(R3)进入IS阶段Load2保留站占用且Busy设置为Yes地址读入偏移量12结果寄存器状态表中F2处填入占用的保留站Load2。 Cycle 3L.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 4L.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 5L.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 6MULT.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 7MULT.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 8MULT.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 9MULT.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 10MULT.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 11MULT.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 12MULT.D F0, F2, F4进入EX阶段余下周期Time设置为3。DIV.D F10, F0, F6由于和MULT.D F0, F2, F4存在RAW的数据冲突且F0暂未计算出结果因此等待。
Cycle 13MULT.D F0, F2, F4进入EX阶段余下周期Time设置为2。DIV.D F10, F0, F6由于和MULT.D F0, F2, F4存在RAW的数据冲突且F0暂未计算出结果因此等待。
Cycle 14MULT.D F0, F2, F4进入EX阶段余下周期Time设置为1。DIV.D F10, F0, F6由于和MULT.D F0, F2, F4存在RAW的数据冲突且F0暂未计算出结果因此等待。 Cycle 15MULT.D F0, F2, F4继续停留在EX阶段计算出浮点乘法的结果并写入到Mult1保留站的值中。DIV.D F10, F0, F6由于和MULT.D F0, F2, F4存在RAW的数据冲突且F0暂未计算 出结果因此等待。 Cycle 16MULT.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 17DIV.D F10, F0, F6进入EX阶段余下周期Time设置为39源寄存器R0就绪来源于M5。 Cycle 18DIV.D F10, F0, F6进入EX阶段余下周期Time设置为38。
……
Cycle 55DIV.D F10, F0, F6进入EX阶段余下周期Time设置为1。 Cycle 56DIV.D F10, F0, F6继续停留在EX阶段计算出浮点除法的结果并写入到Mult2保留站的值中。 Cycle 57DIV.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 54DIV.D指令停留在EX阶段 Cycle 54 Cycle 55 至此整段代码的运行结束。
通过此项工作得出的结论
1性能影响。修改延迟时间会影响处理器执行指令的速度。延长延迟会减慢指令执行而缩短延迟可能加快执行但这也取决于其他因素如指令依赖性和资源利用率。
2资源冲突和调度。在Tomasulo算法中资源共享和动态调度是关键。改变延迟时间可能会影响功能单元的利用率和指令的调度顺序进而影响整体性能。 5习题4第6题模拟
由于本模拟器未设置Store指令和分支指令因此无法执行该题目的模拟。 3.2Tomasula 模拟器的算法分析和实现
1网络教学平台【Tomasulo-Simulator-java】为java编写的Tomasula算法模拟器分析该模拟器源代码要求 1写出设计思路模块划分设计流程。 2找出对应于发射、执行和写回的代码对其进行说明和分析。
1Tomasula 模拟器的设计思路 本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界面如下图所示 2IS、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冲突当连续写同一个寄存器时只有最后一次才能写入。
