标准流水线检测测试试题.doc

第五章 标量处理机与流水线1 选择题1. 假设一条指令的执行过程可以分为“取指令”、“分析”和“执行”三段，每一段的执行时间分别为、和，顺序执行n条指令至少需要花费的时间为：A. B. 生产流水线C. 装配流水线D. 苏州流水线答案：C2. 假设一条指令的执行过程可以分为“取指令”、“分析”和“执行”三段，每一段的执行时间均为，连续执行n条指令所需要花费的最短时间约为（假设仅有“取指令”和“执行”可重叠并假设n足够大）：A. 流水线设备B. 上海流水线C. 无锡流水线D. 杭州流水线答案B3. 假设一条指令的执行过程可以分为“取指令”、“分析”和“执行”三段，每一段的执行时间均为，连续执行n条指令所需要花费的最短时间约为（假设仅有“取指令”和“分析”可重叠并假设n足够大）：A. B. C. D. 答案B4. 假设一条指令的执行过程可以分为“取指令”、“分析”和“执行”三段，每一段的执行时间分别为、和，连续执行n条指令所需要花费的最短时间约为（假设仅有“取指令”和“执行”可重叠并假设n足够大）：A. B. C. D. 答案B5. 假设一条指令的执行过程可以分为“取指令”、“分析”和“执行”三段，每一段分别只有一个部件可供使用并且执行时间分别为、和，连续执行n条指令所需要花费的最短时间约为（假设“取指令”、“分析”和“执行”可重叠并假设n足够大）：A. B. C. D. 答案C6. 看下述程序段：k：R0=R1R4k+1：R6=R51k+2：R2=R0R3k+3：R3=R4-1k+4：R2=R5K+5：下列哪个数据相关没有在上述程序段中发生A. 先写后读相关B. 写-写相关C. 先读后写相关D. 以上都不对答案：D7. 看下述程序段：k：R5=R2k+1：R0=R1R4k+2：R2=R51k+3：R4=R0R3k+4：R3=R4-1K+5：k和k+2之间发生的是什么数据相关I. 先写后读相关II.写-写相关III. 先读后写相关A. 只有IB. 只有I、IIC. 只有I、IIID. 以上都不对答案：C8. 一条流水线可分为k段，各段执行时间都是，共向该流水线输入n个任务，第n个任务结束于：A.B.C. D.答案：D9. 一条流水线的可分为k段，各段的执行时间都是，共向该流水线输入n个任务，求该流水线实际吞吐率为：A. B. C. D. 答案：D10. 一条流水线可以由以下时空图来表示，求该流水线的实际吞吐率（假设n=100）43210时间(s)4ns0空间时间(snn-1321nn-1321nn-1n-1321n321A. B. C. D. 答案：C11. 一条4段的流水线可以由以下时空图来表示，求该流水线的实际吞吐率（假设n=100）时间(s)0543216空间321n321nn321321nA. B. C. D. 答案：D420空间时间nn-1321nn-1321nn-1n-131n32112. 一条流水线可以由以下时空图来表示，求该流水线的加速比A. 2B. 3C. 4D. 6答案：C13. 一条4段流水线，每段执行时间为1ns，求该流水线执行100条指令最大效率为：A. 100%B. 96.2%C. 97.1%D. 388%答案：C14. 如下图所示的浮点加法流水部件，计算，流水线经过多少时钟后排空（假设时钟长度为）3tS2S2S1S4S3ttt输入输出S2A. 16B. 15C. 14D. 13答案：B15. 一台标量处理机，具有一条5级指令流水线，每级均耗时1个时钟周期，执行一个具有20条指令的代码序列。现将此标量处理机改为超流水线处理机，采用同样基准的指令流水线，不同的是每隔1/4个时钟周期发射1条指令，执行相同的代码序列。问前后两次执行的加速比。A. 2.4B. 2.46C. 2.67D. 2.75答案：B16. 一条4个功能段的加乘静态流水线，四个功能段如下所示，计算，最少需要经过多少时间，假设运算的结果有专门的输出通路连接到输入端。并且只有当一个流水线排空后流水线才可以发生另一种运算。（1）取指（2）译码、取数（3）运算（4）写结果A. 16B. 22C. 25D. 27答案：B17. 下图所示的时空图对应的处理机为：43212143时钟周期I6I5I3I2I1指令4321432143214321A. 标量处理机B. 超标量处理机C. 超流水处理机D. 超标量超流水处理机答案：C18. 一台度的超标量超流水线处理机的指令并行度为A. mB. m(n-1)C. (m-1)(n-1)D. mn答案：D19. 连续执行100条指令时，一台2度的超标量处理机的最大效率是多少（假设这里的每条流水线是4段标准流水线的流水线）A. 100%B. 97.1%C. 94.3%D. 92.6%答案：C（公式见演算题13）20. 连续执行100条指令时，一台2度的超流水线处理机的最大效率是多少（假设这里的流水线是4段标准流水线）A. 100%B. 96.1%C. 94.3%D. 93.4%答案：D21. 连续执行100条指令时，一台5度的超标量处理机的最大效率是多少（假设这里的每条流水线是基于4段标准流水线的超标量流水线）A. 100%B. 97.09%C. 87%D. 96.15%答案：C 87 22. 在超标量，超流水线，超标量超流水线等不同结构的指令级并行处理机上运行矩阵乘法CAB（假设A是mn阶的矩阵，B是nl阶的矩阵），最少需要进行多少次乘法和多少次加法？A. mn, nlB. mnl, ml(n-1)C. mnl, mn(l-1)D. mnl, mnl答案：B（乘法，加法的次数不变）23. 试比较在指令并行度较低的情况下，具有相同指令并行度的超标量处理机a和超流水线处理机b的效率A. abB. a=bC. abD. 不能确定（和指令数有关）答案：A24. 一条4个功能段的加乘静态流水线，四个功能段如下所示，计算，最少需要经过多少时间，假设运算的结果必须先写入到缓冲存储器才能供输入端使用。并且只有当一个流水线排空后流水线才可以发生另一种运算。（1）取指（2）译码、取数（3）运算（4）写结果A. 19B. 23C. 24D. 27答案：C(提示：画出时空图，注意在第二个流水段取数)2 问答题1. 简述流水线技术的特点答：流水线技术具有以下特点：流水过程由多个相联系的子过程组成，每个过程称为流水线的“级”或“段”。流水技术适合于大量重复的时序过程。2. 请写出2种数据相关方式，并举例说明分别在什么情况下发生（采用设计程序段的方式来说明）答：写读相关：例如程序段R0=R1R4; R2=R0R3若第二条指令在第一条指令前执行则最终的结果与正确结果不同，此时发生写读相关读写相关例如程序段R2=R0R3; R3=R4-1若第二条指令在第一条指令前执行则最终的结果与正确结果不同，此时发生读写数据相关写写相关例如程序段R2=R0R3; R3=R4-1; R2=R5若指令三在指令一前发生则最终的结果与正确结果不同，此时发生写写数据相关3. 在流水线处理机当中，可能有哪几种操作数据相关？这几种相关分别发生在什么情况下？解决操作数相关的基本方法有哪几种？答：a. 写读相关（先写后读）例如程序段R0=R1R4; R2=R0R3若第二条指令在第一条指令前执行则最终的结果与正确结果不同，此时发生写读相关b. 写写相关例如程序段R2=R0R3; R3=R4-1; R2=R5若指令三在指令一前发生则最终的结果与正确结果不同，此时发生写写数据相关c. 读写相关（先读后写）例如程序段R2=R0R3; R3=R4-1若第二条指令在第一条指令前执行则最终的结果与正确结果不同，此时发生读写数据相关解决数据相关的方法可以分为2大类：延迟执行、建立专用路径4. 请写出两种解决流水线结构相关的方法。答：(1) 流水化功能单元(2) 资源重复5. 降低流水线分支转移损失的方法有哪些？答：(1) 在流水线中尽早判断出分支转移是否成功(2) 尽早计算出分支转移成功时的PC值（即分支的目标地址）“冻结”“排空”流水线的方法：l 预测分支转移失败l 预测分支转移成功l 延迟分支转移6. 试写出延迟转移的3种调度策略，并对其进行评价答：(1) 从前调动（将转移指令前的那条指令调度到延迟槽）转移指令必须不与被调度的指令相关，总是可以有效提高流水线的性能(2) 从目标处调度）（将转移目标处的那条指令调度到延迟槽）若分支转移失败，必须保证被调度的指令对程序的执行没有影响，可能需要复制调度指令。分支转移成功时，可提高流水线性能。但由于复制指令，可能加大程序空间(3) 从失败处调度（将转移不发生时该执行的那条指令调度到延迟槽）若分支转移成功，必须保证被调度的指令对程序的执行无影响。分支转移失败时，可提高流水线性能7. 简述单流水线标量处理机、超标量处理机、超流水线处理机、超标量超流水线处理机的特点答：具有标量数据表示和标量指令系统的处理机称为标量处理机，通常只有一条流水线，一个时钟周期内可以完成一条指令。超标量处理机一般具有多于一条的流水线，一台m度的超标量处理机可同时发射m条指令，指令的发射等待时间为1个时钟，指令的并行度为m。超流水线处理机一般具有一条k段的超流水线，一台n度的超流水处理机可以同时发射一条指令，指令的发射等待时间为1/n个时钟周期，每个时钟周期共发射n条指令。指令的并行度为n。超标量超流水处理机一般具有多于1条的超流水线，一台度的超标量超流水处理机可以同时发射m条指令，指令的发射等待时间为1/n个时钟周期，每个时钟周期共发射mn条指令，指令的并行度为mn。8. 画图说明什么是流水线“瓶颈”，简述解决流水线瓶颈的方法。答：S1S4S3t=tt=tt=3tt=t输入输出S2上图中的S3段就是流水线瓶颈A. 将流水线的“瓶颈”部分再细分B. 重复设置瓶颈流水段，让多个瓶颈流水段并行工作9. 什么是静态流水线？什么是动态流水线答：静态流水线：在同一时间内，多功能流水线中的各个功能段只能按照一种固定的方式连接，实现一种固定的功能。只有当按照这种连接方式工作的所有任务都流出流水线之后，多功能流水线才能重新连接，以实现其他功能。动态流水线：在同一时间内，多功能流水线的各段可以按照不同的方式连接，同时执行多种功能。其中流水线中各个功能部件不能发生冲突。10. 程序中有哪两类相关，分别可以采取什么方法来解决？答：程序中可能出现下两类相关(1) 数据相关数据相关指在执行本条指令的过程中，如果用到的指令、操作数、变址偏移量等是前面指令的执行结果，则必须等待前面的指令执行完成，并把结果写到主存或通用寄存器中之后，本条指令才能开始执行。可以采取设置专用数据通路、延迟执行等方法来解决数据相关。(2) 控制相关控制相关指由条件分支指令、转子程序指令、中断等引起的相关。可以采取静态分支预测技术、动态分支预测技术、提前形成条件码等来解决控制相关。3 演算题1一条流水线连接图如下所示，画出100条指令连续通过该流水线的时空图，并计算该流水线的吞吐率和最大吞吐率。（其中）解：6543210时间(ns)空间n321nnn321321321TP=100/(3*100+6-3)=330MIPS（分母是305，300都不对）TPmax=1/3=333.333MIPS2一条流水线连接图如下所示，画出100条指令连续通过该流水线的时空图，并计算该流水线的加速比。（其中）S1S4S3t=tt=tt=tt=3t输入输出S2解：0543216空间时间(ns)321n321nn321321n顺序执行的时间为T06100600ns采用流水方式执行的时间为T1310061305ns加速比ST0/T1=600/305=1.973连续执行100条指令时，一台2度的超标量超流水线处理机的最大效率是多少（假设这里的每条流水线是基于5段标准流水线的超标量流水线），画出时空图来说明空间n321n321n321T3210n321n123n321nn321321n321n321时间(ns)解：一台2度的超标量处理机完成100条指令需要时间T=5+100/2-1=54效率由以下方法计算100*5/(54*5*2)=93%4用1条5个功能段的浮点加法器流水线计算。每个功能段的延时均相等，流水线的输出端与输入端之间有直接的数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算工作，画出流水线时空图，计算流水线的实际吞吐率、加速比和效率解：假设每个功能段的延迟时间为，则上式中加法右下侧的座标表示这是第几个加法时空图略吞吐率为：加速比为：效率为：E=45/(20*5)=45%5设有一个15000条指令的程序在一台时钟频率为25MHz的线性处理机上执行。假设该指令流水线有5段，并且每个时钟周期发射一条指令。忽略由于转移指令和无序执行造成的损失。(a) 用该流水线执行这一程序，并用通过延迟时间与其相等的一个等效非流水线处理机执行同一程序，将两者加以比较，并计算其加速比。(b) 该流水线处理机的效率和吞吐率是多少？解：(a) 等效的非流水处理机执行一条指令需要的时间是5个时钟周期。按照加速比定义，应有(b) 效率为(c) 吞吐率为6设有图3.5所示的浮点加法流水部件，其中第2功能段的延迟时间是，其余功能段都是S1S4S3t=tt=tt=tt=3t输入输出S2试提出改进这条流水线的2种方法，并计算改进后的效率（针对100个任务）。解：改进方案1：将S2细分为3个功能段Z1，Z2，Z3，分别有的延迟时间，则现在流水线有6个功能段，效率为改进方案2：另外补充与S2相同的2个功能段，如下图所示t1=3tS2S2S1S4S3t1=tt1=tt1=t输入输出S2这样，任务可以连续进入流水线，不存在瓶颈问题，效率为7下列汇编代码在一台3段流水线处理机上执行，每一段都有（相关）检测和分解。这3段是取指令、取操作数（根据要求取一个或多个）和执行（包括写回操作）。试说明在代码执行中所有可能的相关情况。k:INCR0k+1:MULACC, R0k+2:STORER1, ACCk+3:ADDACC, R0k+4:STOREM, ACC其中，双操作数指令，第1个操作数是目的寄存器，第2个操作数是源寄存器。答：1234567IFINCMULSTOREADDSTOREOFR0ACC,R0ACCACC,R0ACCEXR0ACCR1ACCM由此可以看出在t3时刻，发生先写后读相关在t4时刻，发生先写后读相关在t6时刻，发生先写后读相关。8在不同结构的处理机上运行88的矩阵乘法CAB，计算所需要的最短时间。只计算乘法指令和加法指令的执行时间，不计算取操作数、数据传送和程序控制等指令的执行时间。加法部件和乘法部件的延迟时间都是3个时钟周期，另外，加法指令和乘法指令还要经过一个“取指令”和“指令译码”的时钟周期，每个时钟周期为20ns，C的初始值为0。各操作部件的输出段有直接数据通路连接到有关操作部件的输入端，在操作部件的输出端设置有足够容量的缓冲寄存器。求：（a）处理机只有一个通用操作部件，采用顺序方式执行指令的时间（b）单流水线标量处理机，有一条2个功能的静态流水线，流水线每个功能段的延迟时间均为1个时钟周期，加法操作和乘法操作各经过3个功能段解：(a)共需要进行512次乘法和448次加法，需要时间(512+448)*20*(3+1+1)=96000ns(b)先进行所有的乘法，512次乘法，需要51251516个时钟周期。再进行所有的加法，每出一个C矩阵中的结果需要考虑时钟相关，即8个数连加需要18个时钟周期，出64个数就需要16641152个时钟周期，则共需要516+1152=1668个时钟周期，则需要166800ns9某RISC机有8个通用寄存器，有一条4级流水线（1）取指（2）译码、取数（3）运算（4）写结果试编写出8个通用寄存器那所存的数据之和的程序，要求此程序的执行时间最短，并计算出时间（假设，每级流水线的周期为50ns，加法运算的结果只能送回寄存器，而不能在传送途中被截取，另外假设运算的结果可以直接送到输出端）解：程序如下：ADD R1, R2ADD R3, R4ADD R5, R6ADD R7, R8ADD R1, R3ADD R5, R7ADD R1, R5指令的执行周期数为13，共需要1350650ns10某RISC机有16个通用寄存器A1A8，B1B8，有一条如下所示的加乘双功能静态