CPI = 1+20%*(60%*2 + 40%*0) +5%*1 = 1.29 加速比S=CPI/1 = 1.29
3.18 在CRAY-1机器上，按照链接方式执行下述4条向量指令（括号中给出了相应功能部件的执行时间），如果向量寄存器和功能部件之间的数据传送需要1拍，试求此链接流水线的通过时间是多少拍？如果向量长度为64，则需多少拍才能得到全部结果？
V0←存储器 （从存储器中取数：7拍） V2←V0+V1 （向量加：3拍）
V3←V2 解：通过时间就是每条向量指令的第一个操作数执行完毕需要的时间，也就是各功能流水线由空到满的时间，具体过程如下图所示。要得到全部结果，在流水线充满之后，向量中后继操作数继续以流水方式执行，直到整组向量执行完毕。 访存存储器V0V1V2V3V4V5向量加左移向量逻辑乘A3 T通过＝（7＋1）＋（1＋3＋1）＋（1＋4＋1）＋（1＋2＋1）＝23（拍）T总共?T通过＋（64－1）＝23＋63＝86（拍） 3.19 某向量处理机有16个向量寄存器，其中V0~V5中分别放有向量A、B、C、D、E、F，向量长度均为8，向量各元素均为浮点数；处理部件采用两条单功能流水线，加法功能部件时间为2拍，乘法功能部件时间为3拍。采用类似于CARY-1的链接技术，先计算（A+B）*C，在流水线不停流的情况下，接着计算（D+E）*F。 （1） 求此链接流水线的通过时间？（设寄存器入、出各需1拍） （2） 假如每拍时间为50ns，完成这些计算并把结果存进相应寄存器，此处理部件的实际吞吐率为多少MFLOPS？ 解：（1）我们在这里假设A＋B的中间结果放在V6中，（A＋B）×C地最后结果放在V7中，D＋E地中间结果放在V8中，（D＋E）×F的最后结果放在V9中。具体实现参考下图： V0AV1BV6V2CV7向量加向量乘V3DV4EV8V5FV9 通过时间应该为前者（（A＋B）×C）通过的时间： T通过= (1+2+1)+(1+3+1) =9（拍） （2）在做完（A＋B）×C之后，作（C＋D）×E就不需要通过时间了。 V6←A＋B V7←V6×C 16 V8←D＋E V9←V8×F T?T通过＋（8－1）?8?24（拍）?1200(ns)32TP??26.67MFLOPST 第4章 指令级并行 4.1解释下列术语 指令级并行：简称ILP。是指指令之间存在的一种并行性，利用它，计算机可以并行执行两条或两条以上的指令。 指令调度：通过在编译时让编译器重新组织指令顺序或通过硬件在执行时调整指令顺序来消除冲突。 指令的动态调度：是指在保持数据流和异常行为的情况下，通过硬件对指令执行顺序进行重新安排，以提高流水线的利用率且减少停顿现象。是由硬件在程序实际运行时实施的。 指令的静态调度：是指依靠编译器对代码进行静态调度，以减少相关和冲突。它不是在程序执行的过程中、而是在编译期间进行代码调度和优化的。 保留站：在采用Tomasulo算法的MIPS处理器浮点部件中，在运算部件的入口设置的用来保存一条已经流出并等待到本功能部件执行的指令（相关信息）。 CDB：公共数据总线。 动态分支预测技术：是用硬件动态地进行分支处理的方法。在程序运行时，根据分支指令过去的表现来预测其将来的行为。如果分支行为发生了变化，预测结果也跟着改变。 BHT：分支历史表。用来记录相关分支指令最近一次或几次的执行情况是成功还是失败，并据此进行预测。 分支目标缓冲：是一种动态分支预测技术。将执行过的成功分支指令的地址以及预测的分支目标地址记录在一张硬件表中。在每次取指令的同时，用该指令的地址与表中所有项目的相应字段进行比较，以便尽早知道分支是否成功，尽早知道分支目标地址，达到减少分支开销的目的。 前瞻执行：解决控制相关的方法，它对分支指令的结果进行猜测，然后按这个猜测结果继续取指、流出和执行后续的指令。只是指令执行的结果不是写回到寄存器或存储器，而是放到一个称为ROB的缓冲器中。等到相应的指令得到“确认”（即确实是应该执行的）后，才将结果写入寄存器或存储器。 ROB：ReOrder Buffer。前瞻执行缓冲器。 超标量：一种多指令流出技术。它在每个时钟周期流出的指令条数不固定，依代码的具体情况而定，但有个上限。 超流水：在一个时钟周期内分时流出多条指令。 超长指令字：一种多指令流出技术。VLIW处理机在每个时钟周期流出的指令条数是固定的，这些指令构成一条长指令或者一个指令包，在这个指令包中，指令之间的并行性是通过指令显式地表示出来的。 循环展开：是一种增加指令间并行性最简单和最常用的方法。它将循环展开若干遍后，通过重命名和指令调度来开发更多的并行性。 17 4.2 简述Tomasulo算法的基本思想。 答：核心思想是：① 记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减小到最少；② 通过寄存器换名来消除WAR冲突和WAW冲突。寄存器换名是通过保留站来实现，它保存等待流出和正在流出指令所需要的操作数。 基本思想：只要操作数有效，就将其取到保留站，避免指令流出时才到寄存器中取数据，这就使得即将执行的指令从相应的保留站中取得操作数，而不是从寄存器中。指令的执行结果也是直接送到等待数据的其它保留站中去。因而，对于连续的寄存器写，只有最后一个才真正更新寄存器中的内容。一条指令流出时，存放操作数的寄存器名被换成为对应于该寄存器保留站的名称（编号）。 4.3 根据需要展开下面的循环并进行指令调度，直到没有任何延迟。指令的延迟如表4.4。 LOOP: L.D F0,0(R1) MUL.D F0,F0,F2 L.D F4,0(R2) ADD.D F0,F0,F4 S.D F0,0(R2) DSUBI R1,R1,#8 DSUBI R2,R2,#8 BNEZ R1,LOOP 解：将循环展开两次，进行指令调度，即可以消除延迟，代码如下： LOOP： L.D F0，0（R1） L.D F10，-8（R1） MUL.D F0，F0，F2 MUL.D F10，F10，F2 L.D F4，0（R2） L.D F14，-8（R2） ADD.D F0，F0，F4 ADD.D F10，F10，F14 DSUBI R1，R1，16 S.D 0（R2），F0 DSUBI R2，R2，16 BNEZ R1，LOOP S.D 8（R2），F10 4.4 假设有一条长流水线，仅仅对条件转移指令使用分支目标缓冲。假设分支预测错误的开销为4个时钟周期，缓冲不命中的开销为3个时钟周期。假设：命中率为90%，预测精度为90%，分支频率为15%，没有分支的基本CPI为1。 （1） 求程序执行的CPI。 （2） 相对于采用固定的2个时钟周期延迟的分支处理，哪种方法程序执行速度更快？ 解：（1）程序执行的CPI = 没有分支的基本CPI（1） + 分支带来的额外开销 分支带来的额外开销是指在分支指令中，缓冲命中但预测错误带来的开销与缓冲没有命中带来的开销之和。 分支带来的额外开销= 15% * (90%命中×10%预测错误×4 + 10％没命中×3)= 0.099 所以，程序执行的CPI ＝ 1 ＋ 0.099 = 1.099 （2）采用固定的2 个时钟周期延迟的分支处理CPI = 1 + 15%×2 = 1.3 由（1）（2）可知分支目标缓冲方法执行速度快。 4.5 假设分支目标缓冲的命中率为90%，程序中无条件转移指令的比例为5%，没有无条件转移指令的程序CPI值为1。假设分支目标缓冲中包含分支目标指令，允许无条件转移指令进入分支目标缓冲，则程序的CPI值为多少？ 18 解：设每条无条件转移指令的延迟为x，则有： 1＋5%×x＝1.1 x＝2 当分支目标缓冲命中时，无条件转移指令的延迟为0。 所以 程序的CPI ＝ 1 ＋ 2 × 5% ×(1 －90%) ＝1.01 4.6 下面的一段MIPS汇编程序是计算高斯消去法中的关键一步，用于完成下面公式的计算： Y = a ? X + Y 其浮点指令延迟如表4.3所示，整数指令均为1个时钟周期完成，浮点和整数部件均采用流水。整数操作之间以及与其它所有浮点操作之间的延迟为0，转移指令的延迟为0。X中的最后一个元素存放在存储器中的地址为DONE。 FOO: L.D F2,0(R1) MUT.D F4,F2,F0 L.D F6,0(R2) ADD.D F6,F4,F6 S.D F6,0[R2] DADDIU R1,R1,#8 DADDIU R2,R2,#8 DSUBIU R3,R1,#DONE BNEZ R3, FOO (1) 对于标准的MIPS单流水线，上述循环计算一个Y值需要多少时间？其中有多少空转周期？ (2) 对于标准的MIPS单流水线，将上述循环顺序展开4次，不进行任何指令调度，计算一个Y值平均需要多少时间？ 加速比是多少？其加速是如何获得的？ (3) 对于标准的MIPS单流水线，将上述循环顺序展开4次，优化和调度指令，使循环处理时间达到最优，计算一个 Y值平均需要多少时间？加速比是多少？ (1) 对于采用如图4.8前瞻执行机制的MIPS处理器（只有一个整数部件）。当循环第二次执行到 BNEZ R3,FOO 时，写出前面所有指令的状态，包括指令使用的保留站、指令起始节拍、执行节拍和写结果节拍，并写出处理器当前的状态。 (2) 对于2路超标量的MIPS流水线，设有两个指令流出部件，可以流出任意组合的指令，系统中的功能部件数量不 受限制。将上述循环展开4次，优化和调度指令，使循环处理时间达到最优。计算一个Y值平均需要多少时间？加速比是多少？ (3) 对于如图4.13结构的超长指令字MIPS处理器，将上述循环展开4次，优化和调度指令，使循环处理时间达到最 优。计算一个Y值平均需要多少时间？加速比是多少？ 解：（1） L.D F2, 0(R1) 1 Stall MUT.D F4, F2, F0 2 L.D F6, 0(R2) 3 Stall Stall ADD.D F6, F4, F6 4 Stall Stall S.D F6, 0[R2] 5 DADDIU R1, R1, #8 6 DADDIU R2, R2, #8 7 DSUBIU R3, R1, #DONE 8 19 BNEZ R3, FOO 9 所以，共有14 个时钟周期，其中有5 个空转周期。 （2）循环顺序展开4 次，不进行任何指令调度，则指令1～5 及其间的stall 都是必要的，只是指令6～9 只需执行一次，因此，共有 10 × 4 ＋ 4 ＝ 44 个时钟周期，计算出4 个Y 值，所以计算一个Y 值需要11 个时钟周期，加速比为：14/11 = 1.27 。加速主要是来自减少控制开销，即减少对R1、R2 的整数操作以及比较、分支指令而来的。 （3）循环顺序展开4 次，优化和调度指令，如下： L.D F2, 0(R1) L.D F8, 8(R1) L.D F14, 16(R1) L.D F20, 24(R1) MUT.D F4, F2, F0 MUT.D F10, F8, F0 MUT.D F16, F14, F0 MUT.D F22, F20, F0 L.D F6, 0(R2) L.D F12, 8(R2) L.D F18, 16(R2) L.D F24, 24(R2) ADD.D F6, F4, F6 ADD.D F12, F10, F12 ADD.D F18, F16, F18 ADD.D F24, F22, F24 S.D F6, 0[R2] S.D F12, 8[R2] S.D F18, 16[R2] S.D F24, 24[R2] DADDIU R1, R1, #32 DADDIU R2, R2, #32 DSUBIU R3, R1, #DONE BNEZ R3, FOO 共用了24 个时钟周期，则计算一个Y 值平均需要 24/4 = 6 个时钟周期， 加速比：14/6 = 2.33 （4） 指令 指令执行时钟 流出 执行 写结果 确认 L.D F2, 0（R1） 1 2 3 4 MUL.D F4, F2, F0 2 4 5 6 L.D F6, 0（R2） 3 4 6 7 ADD.D F6, F4, F6 4 8 9 10 S.D F6, 0（R2） 5 11 12 13 DADDIU R1, R1, #8 6 7 8 DADDIU R2, R2, #8 7 8 9 DSUBIU R3,R1,#DONE 8 9 10 BNEZ R3, FOO 9 10 L.D F2, 0（R1） 10 11 13 14 MUL.D F4, F2, F0 11 13 14 15 20