计算机体系结构张晨曦版本第四章解答-new.doc

第四章 习题四4.1解释下列术语：指令级并行：指令序列中存在的潜在的并行性称为指令级并行。指令调度：指令调度是一种用以避免冲突的方法，但并不改变相关。通过改变指令在程序中的位置，将相关指令间的距离加大到不小于指令执行延迟的时钟数，以此消除相关指令造成的流水线冲突。指令的动态调度：在程序执行过程中，依靠专门的硬件对代码进行调度，重新安排指令的执行顺序，来调整相关指令实际执行时的关系，减少可能的冲突。指令的静态调度：在程序的编译期间，由编译器进行代码调度和优化，重新安排指令的执行顺序，把相关的指令拉开距离，以减少可能产生的冲突。保留站：在Tomasulo算法实现结构中，保留站设置在运算部件的入口，每个保留站中保存一条已经流出并等待到本功能部件执行的指令的相关信息，包括操作码、操作数以及用于检测和解决冲突的信息。在一条指令流出到保留站的时候，如果该指令的操作数已经在寄存器中就绪，则将之取到该保留站中。如果操作数还没有计算出来，则在该保留站中记录将产生这个操作数的保留站的标识。CDB：公共数据总线，是Tomasulo算法实现结构中的一条重要的数据通路，所有功能部件的计算结果都要送到CDB上，由它把这些结果直接送到各个需要该结果的地方。动态分支预测技术：用硬件动态地进行分支处理的方法。这些方法是在程序运行时，根据分支指令过去的表现来预测其将来的行为。如果分支行为发生了变化，预测结果也随之改变。其目的有两个：预测分支是否成功和尽快找到分支目标地址（或指令），从而避免控制相关造成流水线停顿。BHT：分支历史表，也称之为分支预测缓冲器，用来记录分支指令最近一次或几次的执行情况（成功或不成功），并根据此进行预测。分支目标缓冲：将分支成功的分支指令的地址和它的分支目标地址都放到一个缓冲区中保存起来，缓冲区以分支指令的地址作为标识，取指令阶段，所有指令地址都与保存的标示作比较，一旦相同，就认为本指令是分支指令，且认为它转移成功，并且它的分支目标地址就是保存在缓冲区的分支目标地址。前瞻执行：基于硬件的前瞻执行结合了以下三种思想：（1） 动态分支预测。用来选择后续执行的指令。（2） 在控制相关的结果尚未出来之前，前瞻地执行后续指令。（3） 用动态调度方法对基本块的各种组合进行跨基本块的调度。ROB：再定序缓冲，前瞻执行允许指令乱序执行，但要求按程序顺序确认，为此设置ROB，用以保存指令执行完毕到指令得到确认间的所有指令及其结果。超标量：超标量处理机的典型结构是有多个操作部件，每个时钟周期流出的指令数不定，但有上限。可通过多个独立的操作部件实现多指令的并行，使CPI的值小于1。超流水：将流水段进一步化，在一个时钟周期内能够分时流出多条指令，使CPI的值小于1。超长指令字：这种指令字很长，被分割成多个字段，每个字段称为一个指令槽，直接独立控制一个功能部件。每个时钟周期流出的指令数是固定的，它们构成一条长指令，或说是一个混合指令包，只能通过编译静态调度。循环展开：通过多次复制循环体并改变结束条件来相对增加有效操作时间，用于指令调度的一种方式。4.2 简述Tomasulo算法的基本思想。（1）记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减少到最小；（2）通过寄存器换名来消除WAR和WAW冲突。4.3 根据需要展开下面的循环并进行指令调度，直到没有任何延迟。指令的延迟如表4.3。表4.3 本章使用的浮点流水线的延迟产生结果指令使用结果指令延迟时钟周期数浮点计算另外的浮点计算 3浮点计算浮点存操作（SD） 2浮点取操作（LD）浮点计算 1浮点取操作（LD）浮点存操作（SD） 0 LOOP: L.D F0, 0(R1) （一次空转） MULT.D F0, F0, F2 L.D F4, 0(R2) （二次空转） ADD.DF0, F0, F4 （二次空转） S.D0(R2), F0 DSUBI R1, R1, #8 DSUBI R2, R2, #8 BNEQZ R1, LOOP （一次空转）循环展开三次： LOOP: LD F0, 0(R1) LD F3, -8(R1) LD F6, -16(R1)MULTD F0, F0, F2MULTD F3, F3, F2MULTD F6, F6, F2LD F4, 0(R2)LD F5, -8(R2)LD F7, -16(R2)ADDD F0, F0, F4ADDD F3, F3, F5ADDD F6, F6, F7SD 0(R2), F0SD -8(R2), F3SD -16(R2), F6SUBI R1, R1, #24BNEQZ R1, LOOPSUBI R2, R2, #24展开二次也可。4.4 假设有一个长流水线，仅仅对条件转移指令使用分支目标缓冲。假设分支预测错误的开销为4个时钟周期，缓冲不命中的开销为3个时钟周期。假设：命中率为90%，预测精度为90%，分支频率为15%，没有分支的基本CPI为1。（1） 求程序执行的CPI（2） 相对于采用固定的2个时钟周期延迟的分支处理，哪种方法程序执行速度更快？解答：（1） CPI=1+命中率预测错误率4+不命中率3 分支频率=1+0.90.14+0.13 0.15=1+0.36+0.3 0.15=1+0.660.15=1.099(2) 采用固定2时钟延迟CPI=1+15%2=1.3由CPI比较可知前一种方式更快4.5 假设分支目标缓冲的命中率为90%，程序中无条件转移指令的比例为5%，没有无条件转移指令的程序CPI值为1。假设分支目标缓冲中包含分支目标指令，允许无条件转移指令进入分支目标缓冲，则程序的CPI值为多少？解答：CPI=1+5%(1-90%)3=1.00154 6 下面一段MIPS汇编程序是计算高斯消去法中的关键一步，用于完成下面公式的计算： Y=a X +Y其浮点指令延迟如表4.3所示，整数指令均为1个时钟周期完成，浮点和整数部件均为流水。整数操作之间以及与其他所有浮点操作之间的延迟为0，转移指令的延迟为0。X中的最后一个元素存放在存储器中的地址为DONE。FOO:L.DF2 ,0(R1)MULT.D F4 ,F2 ,F0L.DF6 ,0(R2)ADD.DF6 ,F4 ,F6S.D 0(R2), F6 DADDIU R1 , R1, #8 DADDIU R2 , R2, #8 DSUBIU R3 , R1 , DONE BEQZ R3 , FOO (1) 对于标准的MIPS单流水线，上述循环计算一个Y值需要多少时间？其中有多少空转周期？(2) 对于标准的MIPS单流水线，将上述循环顺序展开4次，不进行任何指令调度，计算一个Y值需要多少时间？加速比是多少？其加速是如何获得的？(3) 对于标准的MIPS单流水线，将上述循环顺序展开4次，优化和调度指令，使循环处理时间达到最优，计算一个Y值平均需要多少时间，加速比是多少？解答：（1）易知循环计算一个Y值需要15个时钟周期，其中有6个空转周期。 FOO:L.DF2 ,0(R1); load Xi（一次空转）MULT.D F4 ,F2 ,F0; mutliply a* XiL.DF6 ,0(R2); load Yi（二次空转）ADD.DF6 ,F4 ,F6; add a* Xi+ Yi（二次空转）S.D 0(R2), F6 ; store YiDADDIU R1 , R1, #8 ;increment X indexDADDIU R2 , R2, #8 ; increment Y indexDSUBIU R3 , R1 , DONE ; test if doneBEQZ R3 , FOO ; loop if not done（一次空转） （2）FOO:L.DF2 ,0(R1); load Xi（一次空转）MULT.D F4 ,F2 ,F0; mutliply a* XiL.DF6 ,0(R2); load Yi（二次空转）ADD.DF6 ,F4 ,F6; add a* Xi+ Yi（二次空转）S.D 0(R2), F6 ; store YiDADDIU R1 , R1, #8 ;increment X indexDADDIU R2 , R2, #8 ; increment Y indexDSUBIU R3 , R1 , DONE ; test if doneBEQZ R3 , FOO ; loop if not done（一次空转）FOO:L.DF2 ,8(R1); load Xi（一次空转）MULT.D F4 ,F2 ,F0; mutliply a* XiL.DF6 ,8(R2); load Yi（二次空转）ADD.DF6 ,F4 ,F6; add a* Xi+ Yi（二次空转）S.D 8(R2), F6 ; store YiDADDIU R1 , R1, #8 ;increment X indexDADDIU R2 , R2, #8 ; increment Y indexDSUBIU R3 , R1 , DONE ; test if doneBEQZ R3 , FOO ; loop if not done（一次空转）FOO:L.DF2 ,16(R1); load Xi（一次空转）MULT.D F4 ,F2 ,F0; mutliply a* XiL.DF6 ,16(R2); load Yi（二次空转）ADD.DF6 ,F4 ,F6; add a* Xi+ Yi（二次空转）S.D 16(R2), F6 ; store YiDADDIU R1 , R1, #8 ;increment X indexDADDIU R2 , R2, #8 ; increment Y indexDSUBIU R3 , R1 , DONE ; test if doneBEQZ R3 , FOO ; loop if not done（一次空转）FOO:L.DF2 ,24(R1); load Xi（一次空转）MULT.D F4 ,F2 ,F0; mutliply a* XiL.DF6 ,24(R2); load Yi（二次空转）ADD.DF6 ,F4 ,F6; add a* Xi+ Yi（二次空转）S.D 24(R2), F6 ; store YiDADDIU R1 , R1, #32 ;increment X indexDADDIU R2 , R2, #32 ; increment Y indexDSUBIU R3 , R1 , DONE ; test if doneBEQZ R3 , FOO ; loop if not done（一次空转）计算一个Y值平均需要：45/4=11.25个时钟周期加速比：15/11.25=1.33通过循环展开使得指令减少、分支减少。（3） FOO: LD F2 , 0(R1) LD F1, 0(R1) LD F7, 0(R1) LD F8, 0(R1)MULTD F4 , F2 , F0MULTD F3, F1, F0 MULTD F9 F7, F0 MULTD F10 F8 F0LD F6 , 0(R2) LD F5, 0(R2) LD F11