计算机体系结构习题三及答案专升本高升专计算机高本下学期

1、计算机体系结构习题三一、(10分)某台主频为400MHz的计算机执行标准测试程序，程序中指令类型、执行数量和平均时钟周期数如下：指令类型指令执行数量平均时钟周期数整数450001数据传送750002浮点80004分支15002求该计算机的有效CPI、MIPS和程序CPU时间二、(10分)计算机系统中有三个部件可以改进，这三个部件的改进加速比为：部件加速比1=30;部件加速比2=20;部件加速比3=10(1) 如果部件1和部件2在整个系统运行时间中所占的比例均为30%,那么当部件3的比例为多少时，系统加速比才可以达到10?(2) 如果三个部件的所占比例分别为30%、30%和20%,三个部件同时改

2、进，那么系统中不可加速部分的执行时间在总执行时间中占的比例是多少？三、(5分)根据CPU中保存操作数的存储器类型，可以把指令集结构分为哪些类型？四、(10分)在MIPS流水线上运行如下代码序列：LOOP:LWR1,0(R2)DADDIUR1,R1,#1SWR1,0(R2)DADDIUR2,R2,#4DSUBR4,R3,R2BNEZR4,LOOP其中：R3的初值是R2+396。假设：在整个代码序列的运行过程中，所有的存储器访问都是命中的，并且在一个时钟周期中可对同一个寄存器在前半周期写，而在后半周期读。那么：(1) 在没有任何其它定向(或旁路)硬件的支持下，请画出该指令序歹U执行的流水线时空图。

3、假设采用暂停流水线的策略处理分支指令，且所有的存储器访问都命中Cach那么执行上述循环需要多少个时钟周期？(2) 假设该流水线有通常的定向路径，请画出该指令序歹U执行的流水线时空图。假设采用预测分支失败的策略处理分支指令，且所有的存储器访问都命中Caches那么执行上述循环需要多少个时钟周期？(3) 假设该流水线有通常的定向路径和一个时钟周期的延迟分支，请对该循环中的指令进行调度，你可以重新组织指令的顺序，也可以修改指令的操作数，但是注意不能增加指令的条数。请画出该指令序列执行的流水线时空图，并计算执行上述循环所需要的时钟周期数。五、（10分）假设某程序各种分支指令数占所有指令数的白分比如下：

4、条件分支20%（其中的60%是分支成功的）跳转和调用5%现有一条段数为4的流水线，无条件分支在第2个时钟周期结束时就被解析出来，而条件分支要到第3个时钟周期结束时才能够被解析出来。第一个流水段是完全独立丁指令类型的，即所有类型的指令都必须经过第一个流水段的处理。请问在没有任何控制相关的情况下，该流水线相对丁存在上述控制相关情况下的加速比是多少？六、（10分）假设有一条长流水线，仅仅对条件分支指令使用分支目标缓冲。其中分支预测错误的开销为4个时钟周期，分支目标缓冲不命中的开销为3个时钟周期。分支目标缓冲命中率为90%，预测正确率为90%,分支指令占所有指令的比例为15%，没有分支的基本CPI为1

5、。（1）求程序执行的CPI。（2）相对丁采用固定的2个时钟周期延迟的分支处理，哪种方法程序执行速度更快？七、（10分）设指令流水线由取指令、分析指令和执行指令3个部件构成，每个部件经过的时间为t,连续流入12条指令，假设没有停顿。请分别画出标量流水处理机以及ILP均为4的超标量处理机、超长指令字处理机、超流水处理机的时空图，并分别计算它们相对丁标量流水处理机的加速比。八、（10分）假设对指令Cache的访问占全部访问的75%;而对数据Cache的访问占全部访问的25%。Cache的命中时间为1个时钟周期，失效开销为50个时钟周期，在混合Cache中一次load或store操作访问Cache的命

6、中时间都要增加一个时钟周期，32KB的指令Cache的失效率为0.39%,32KB的数据Cache的失效率为4.82%,64KB的混合Cache的失效率为1.35%。乂假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。试问指令Cache和数据Cache容量均为32KB的分离Cache和容量为64KB的混合Cache相比，（1）哪种Cache的失效率更低？（2）两种情况下平均访存时间各是多少？九、（10分）假设一台计算机具有以下特性：（1）95%的访存在Cache中命中；（2）块大小为两个字，且失效时整个块被调入；（3）CPU发出访存请求的速率为109字/s；（4）25%的访存为

7、写访问；（5）存储器的最大流量为109字/s（包括读和写）；（6）主存每次只能读或写一个字；(7) 在任何时候,Cache中有30%的块被修改过；(8) 写失效时，Cache采用按写分配法。现欲给该计算机增添一台外设，为此首先想知道主存的带宽已用了多少。试对于以下两种情况计算主存频带的平均使用比例。(1) 写直达Cache；(2) 写回法Cach&十、(10分)假设采用理想存储器系统时的基本CPI是1.5,主存访问的延迟是40个时钟周期，传输速率为4字节/时钟周期。Cache中50%的块是修改过的，每个块有32字节，20%的指令是数据访存指令，25%的访存为写访问。同时假设没有写缓存，在TLB

8、失效的情况下开销为20时钟周期，TLB不会降低Cache命中率。CPU产生的指令地址或数据地址有0.2%没有在TLB中命中。(1) 在理想TLB情况下，计算均采用写回法16KB直接映象混合Cacha16KB两路组相联混合Cache和32KB直接映象混合Cache机器的实际CPI;(2) 在实际TLB情况下，用(1)的结果，计算均采用写回法16KB直接映象混合Cacha16KB两路组相联混合Cache和32KB直接映象混合Cache机器的实际CPI;另夕卜，假设16KB直接映象混合Cach816KB两路组相联混合Cache和32KB直接映象混合Cache的失效率分别为2.9%、2.2册日2.0%

9、。H一、(5分)请简述Tomasul。算法的基本思想。计算机体系结构习题三答案十二、(10分)某台主频为400MHz的计算机执行标准测试程序，程序中指令类型、执行数量和平均时钟周期数如下：指令类型指令执行数量平均时钟周期数整数450001数据传送750002浮点80004分支15002求该计算机的有效CPI、MIPS和程序CPU时间。答：(1)CPI=(45000X1+75000X2+8000X4+1500X2)/129500=1.776(或460)259(2) MIPS速率=f/CPI=400M/1.776=225.225MIPS(或180MIPS)259(3) 程序CPU时间=(45000

10、X1+75000X2+8000X4+1500X2)/400M=575s十三、(10分)计算机系统中有三个部件可以改进，这三个部件的改进加速比为：部件加速比1=30;部件加速比2=20;部件加速比3=10(3) 如果部件1和部件2在整个系统运行时间中所占的比例均为30%,那么当部件3的比例为多少时，系统加速比才可以达到10?(4)进,少？如果三个部件的所占比例分别为30%、30%和20%,三个部件同时改那么系统中不可加速部分的执行时间在总执行时间中占的比例是多答：(1)在多个部件可改进情况下，Amdahl定理的扩展：Sn(1GST已知Si=30,S2=20,S3=10,Sn=10,Fi=0.3,

11、F2=0.3,得:1011-(0.30.3F3)(0.3/300.3/20F3/10)得F3=0.36，即部件3的比例为36%。(2)设系统改进前的执行时间为T,则3个部件改进前的执行时间为：(0.3+0.3+0.2)T=0.8T,不可改进部分的执行时间为0.2T。已知3个部件的改进加速比分别为Si=30,S2=20,S3=10,因此3个部件改进后的执行时间为：0.3T0.2T0.045T2010Tn=0.045T+0.2T=0.245T0.3TTn30改进后整个系统的执行时间为：那么系统中不可改进部分的执行时间在总执行时间中占的比例是:0.2T0.245T0.82十四、(5分)根据CPU中保

12、存操作数的存储器类型，可以把指令集结构分为哪些类型？答：可以分为堆栈型、累加器型、通用寄存器型3种。堆栈型：CPU中存储操作数的单元是堆栈的指令集结构。累加器型：CPU中存储操作数的单元是累加器的指令集结构。通用寄存器型：CPU中存储操作数的单元是通用寄存器的指令集结构。十五、(10分)在MIPS流水线上运行如下代码序列：LOOP:LWR1,0(R2)DADDIUR1,R1,#1SWR1,0(R2)DADDIUR2,R2,#4DSUBR4,R3,R2BNEZR4,LOOP其中：R3的初值是R2+396。假设：在整个代码序列的运行过程中，所有的存储器访问都是命中的，并且在一个时钟周期中可对同一个

13、寄存器在前半周期写，而在后半周期读。那么：(4) 在没有任何其它定向(或旁路)硬件的支持下，请画出该指令序歹0执行的流水线时空图。假设采用暂停流水线的策略处理分支指令，且所有的存储器访问都命中Cach那么执行上述循环需要多少个时钟周期？(5) 假设该流水线有通常的定向路径，请画出该指令序歹U执行的流水线时空图。假设采用预测分支失败的策略处理分支指令，且所有的存储器访问都命中Caches那么执行上述循环需要多少个时钟周期？(6) 假设该流水线有通常的定向路径和一个时钟周期的延迟分支，请对该循环中的指令进行调度，你可以重新组织指令的顺序，也可以修改指令的操作数，但是注意不能增加指令的条数。请画出该

14、指令序列执行的流水线时空图，并计算执行上述循环所需要的时钟周期数。(1)无定向(旁路)硬件支持。暂停流水线处理分支指令12345678910111213141516171819202122LWIFIDEXMWBDADDIUIFSSIDEXMWBSWIFSSIDEXMWBDADDIUIFIDEXMWBDSUBIFSSIDEXMWBBNEZIFSSIDEXMWBLWIFSSIFIDEXMWB(2)第i次迭代（i=0.98）开始周期：1+（ix17）总的时钟周期数：（98X17）+18=1684有通常定向路径，预测分支失败。指令123LWIFIDEXDADDIUIFIDSWIFDADDIUDSUBB

15、NEZLW45678910111131415MWBSEXMWBSIDEXMWBIFIDEXMWBIFIDEXMWBIFIDEXMWBIFmissmissIFIDEXMWB(3)1第i次迭代(i=0.98)开始周期：1+(ix10)总的时钟周期数：(98X10)+11=991有通常定向路径。单周期延迟分支。LOOP:LWR1,0(R2)DADDIUR2,R2,#4DADDIUR1,R1,#1DSUBR4,R3,R2BNEZR4,LOOPSWR1,-4(R2)第i次迭代(i=0.98)开始周期：1+(ix6)总的时钟周期数：(98X6)+10=598指令1234567891011LWIFIDEXM

16、WBDADDIUIFIDEXMWBDADDIUIFIDEXMWBDSUBIFIDEXMWBBNEZIFIDEXMWBSWIFIDEXMWBLWIFIDEXMWB十六、（10分）假设某程序各种分支指令数占所有指令数的白分比如下:条件分支20%（其中的60%是分支成功的）1跳转和调用5%现有一条段数为4的流水线，无条件分支在第2个时钟周期结束时就被解析出来，而条件分支要到第3个时钟周期结束时才能够被解析出来。第一个流水段是完全独立丁指令类型的，即所有类型的指令都必须经过第一个流水段的处理。请问在没有任何控制相关的情况下，该流水线相对丁存在上述控制相关情况下的加速比是多少？答：没有控制相关时流水线的

17、平均CPI=1存在控制相关时：无条件分支在第2个时钟周期结束时就被解析出来，而条件分支要到第3个时钟周期结束时才能被解析出来，这意味着分支目标地址可以在第2个时钟周期计算出来(因为无条件分支只需要知道分支目标即可)，而分支条件要到第3个时钟周期才能判断出来。因为题目未指定控制相关的解决方法，故假设采用暂停流水线、预测分支成功、预测分支失败这3种方法。每种方法的分析如下：(1) 若使用暂停流水线的策略，则对于条件分支，有2个额外的stall,对无条件分支，有1个额外的stall:CPI=1+20%*2+5%*1=1.45加速比S=CPI/1=1.45(2) 若使用预测分支成功策略，则对于不成功的

18、条件分支，有2个额外的stall，对无条件分支和成功的条件分支，有1个额外的stall1：CPI=1+20%*(60%*1+40%*2)+5%*1=1.33加速比S=CPI/1=1.33(3) 若使用预测分支失败策略，则对于成功的条件分支，有2个额外的stall;对无条件分支，有1个额外的stall；对不成功的条件分支，其目标地址已经由PC值给出，不必等待，所以无延迟：CPI=1+20%*(60%*2+40%*0)+5%*1=1.29加速比S=CPI/1=1.29十七、(10分)假设有一条长流水线，仅仅对条件分支指令使用分支目标缓冲。其中分支预测错误的开销为4个时钟周期，分支目标缓冲不命中的开

19、销为3个时钟周期。分支目标缓冲命中率为90%，预测正确率为90%,分支指令占所有指令的比例为15%，没有分支的基本CPI为1。(3) 求程序执行的CPI。(4) 相对于采用固定的2个时钟周期延迟的分支处理，哪种方法程序执行速度更快？答：(1)程序执行的CPI=没有分支的基本CPI(1)+分支带来的额外开销分支带来的额外开销是指在分支指令中，缓冲命中但预测错误带来的开销与缓冲没有命中带来的开销之和。(通常，在采用了分支目标缓冲时，如果发生了分支目标缓冲命中，那么会直接利用缓冲中的分支目标地址进行取指，即预测分支转移，所以如果分支预测正确，那就没有开销。如果分支实际未发生转移，那么就出现了预测错误

20、，需要取消已取来的分支目标处指令，重新从分支失败处取指。根据题意，这种情况的开销为4个时钟周期。另一方面，如果分支目标缓冲不命中，那么根据题意，开销为3个时钟周期)分支带来的额外开销=15%*(90%命中X10%预测错误X4+10%没命中X3)=0.099所以，程序执行的CPI=1+0.099=1.099(2)采用固定的2个时钟周期延迟的分支处理CPI=1+15%X2=1.3由(1)(2)可知分支目标缓冲方法执行速度快。十八、(10分)设指令流水线由取指令、分析指令和执行指令3个部件构成,每个部件经过的时间为久t,连续流入12条指令，假设没有停顿。请分别画出标量流水处理机以及ILP均为4的超标

21、量处理机、超长指令字处理机、超流水处理机的时空图，并分别计算它们相对丁标量流水处理机的加速比。答：标量流水处理机的时空图：执行完12条指令需Ti=14Ato超标量流水处理机与超长指令字处理机的时空图:超标量处理机时空图超长指令字处理机时空图超标量流水处理机中，每一个时钟周期同时启动4条指令。执行完12条指令需T2=5At,相对丁标量流水处理机的加速比为：T114tT35t52 二2.8T25t超长指令字处理机中，每4条指令组成一条长指令，共形成3条长指令。执行完12条指令需T3=5At,相对丁标量流水处理机的加速比为：cT114tCC53 2.8超流水处理机的时空图:执行分析取指I:455.7

22、5时间超流水处理机中，每1/4个时钟周期启动一条指令。执行完12条指令需T4=5.75At,(第1条指令通过时间为3*t,其余11条指令每隔1/4*t完成1条，共2.75*t)相对丁标量流水处理机的加速比为：2.435L14ts44T45.75t十九、(10分)假设对指令Cache的访问占全部访问的75%;而对数据Cache的访问占全部访问的25%。Cache的命中时间为1个时钟周期，失效开销为50个时钟周期，在混合Cache中一次load或store操作访问Cache的命中时间都要增加一个时钟周期(即数据访问命中要比指令读取命中多1个时钟周期，这是结构相关导致的)，32KB的指令Cache的

23、失效率为0.39%,32KB的数据Cache的失效率为4.82%,64KB的混合Cache的失效率为1.35%。乂假设采用写直达策略，且有一个写缓冲器，并且忽略写缓冲器引起的等待。试问指令Cache和数据Cache容量均为32KB的分离Cache和容量为64KB的混合Cache相比，(1)哪种Cache的失效率更低？(2)两种情况下平均访存时间各是多少？答：(1)根据题意，约75%的访存为取指令。因此，分离Cache的总体失效率为：(75%x0.39%)+(25%x4.82%)=1.498%;容量为64KB的混合Cache的失效率略低一些，只有1.35%。(2)平均访存时间公式可以分为指令访问

24、和数据访问两部分：平均访存时间=指令所占的白分比X(读命中时间+读失效率X失效开销)+数据所占的白分比X(数据命中时间+数据失效率X失效开销)所以，两种结构的平均访存时间分别为：分离Cache的平均访存时间=75%X(1+0.39%x50)+25%x(1+4.82%X50)=(75%X1.195)+(25%X3.41)=1.7488混合Cache的平均访存时间=75%x(1+1.35%x50)+25%x(1+1+1.35%X50)=(75%X1.675)+(25%X2.675)=1.925因此，尽管分离Cache的实际失效率比混合Cache的高，但其平均访存时间反而较低。分离Cache提供了两

25、个端口，消除了结构相关。二十、(10分)假设一台计算机具有以下特性：(9) 95%的访存在Cache中命中；(10) 块大小为两个字，且失效时整个块被调入；(11) CPU发出访存请求的速率为109字/s；(12) 25%的访存为写访问；(13) 存储器的最大流量为109字/s(包括读和写)；(14) 主存每次只能读或写一个字；(15) 在任何时候，Cache中有30%的块被修改过；(16) 写失效时，Cache采用按写分配法。现欲给该计算机增添一台外设，为此首先想知道主存的带宽已用了多少。试对丁以下两种情况计算主存频带的平均使用比例。(3) 写直达Cache；(4) 写回法Cach&答：采用

26、按写分配(1)写直达cache访问命中，有两种情况：读命中，不访问主存；写命中，更新cache和主存，访问主存1次。访问失效，有两种情况：读失效，将主存中的块调入cache中，访问主存2次；写失效，将要写的块调入cache,访问主存2次，再将修改的数据写入cache和主存，访问主存1次，共3次。上述分析如下表所示。访问命中访问类型频率访存次数Y读95%*75%=71.3%0Y写95%*25%=23.8%1N读5%*75%=3.8%2N写5%*25%=1.3%3一次访存请求的平均访存次数=(71.3%*0)+(23.8%*1)+(3.8%*2)+(1.3%*3)=0.35已用带宽=0.35X10

27、9/109=35.0%(2)写回法cache访问命中，有两种情况：读命中，不访问主存；写命中，不访问主存。采用写回法，只有当修改的cache块被换出时，才写入主存；访问失效,有一个块将被换出，这也有两种情况：如果被替换的块没有修改过，将主存中的块调入cache块中，访问主存2次；如果被替换的块修改过，则首先将修改的块写入主存，需要访问主存2次；然后将主存中的块调入cache块中，需要访问主存2次，共4次访问主存。访问命中块为脏频率访存次数YN95%*70%=66.5%0YY95%*30%=28.5%0NN5%*70%=3.5%2NY5%*30%=1.5%4所以：一次访存请求的平均访存次数=66

28、.5%*0+28.5%*0+3.5%*2+1.5%*4=0.13已用带宽=0.13X109/109=13%二十一、（10分）假设采用理想存储器系统时的基本CPI是1.5,主存访问的延迟是40个时钟周期，传输速率为4字节/时钟周期（此处暗示对丁主存访问时间的计算需要根据数据大小和传输速率来计算，即主存访问时间=主存延迟+数据大小/传输速率）。Cache中50%的块是修改过的，每个块有32字节，20%的指令是数据访存指令，25%的访存为写访问。同时假设没有写缓存，在TLB失效的情况下开销为20时钟周期，TLB不会降低Cache命中率。CPU产生的指令地址或数据地址有0.2%没有在TLB中命中。（3

29、）在理想TLB情况下，计算均采用写回法16KB直接映象混合Cacha16KB两路组相联混合Cache和32KB直接映象混合Cache机器的实际CPI;（4）在实际TLB情况下，用（1）的结果，计算均采用写回法16KB直接映象混合Cacha16KB两路组相联混合Cache和32KB直接映象混合Cache机器的实际CPI;另夕卜，假设16KB直接映象混合Cach816KB两路组相联混合Cache和32KB直接映象混合Cache的失效率分别为2.9%、2.2册日2.0%。答：CPI=CPI执行+存储停顿周期总数/指令总数存储停顿由下列原因引起：TLB失效，从主存中读取贞表项取指令Cache失效，从主

30、存中取指load和store指令访问数据Cache失效，从主存中读写数据（注意：采用TLB意味着访存的过程需要进行虚拟-物理内存地址转换。我们假设Cache使用的是物理内存地址，那么访存过程是：首先，CPU发出的虚拟地址去查找TLB,如果TLB命中，则直接取得贞表项，进行地址转换，获得物理地址。否则需要从主存载入贞表项，然后转换得到物理地址。然后，利用转换得到的物理地址去访问Cache,如果Cache命中，则直接返回。如果Cache缺失，则从主存载入数据或指令。因此，存储停顿发生在TLB失效，取指Cache失效，访问数据Cache失效这三种情况。）以Mem_Stalls表示存储停顿周期总数，以

31、IC表示指令总数，以Inst_Stalls表示取指停成期总数，以Data_Stalls表示数据访问停顿周期总数，以TLB_Stalls表小TLB失效引起的停顿周期总数。MemStallsInstStallsDataStallsTLBStallsICICICICInstStallsICAnstMPnstMmstPInst其中，AInst是取指总数。由丁每条指令都要取指一次，因此AInst=IC。MInst和PInst分别是取指时Cache缺失率和缺失开销。11ADataMDataPDataADataICIVIDataPDataICICAData其中，是数据访I可总数除以指令总数，即平均每指令数据

32、访I可次数。根据ICAData题意，指令中有20%是数据项可指令，因此，=20%0MData和PData分别是ICPData分别要根据读/写TLBStalls（1）对丁理想TLB,TLB无失效。因此，90IC样的。数据访问时Cache缺失率和缺失开销。在后面，可以看到操作来计算。IC对丁混合Cache,取指令和数据读/写的Cache缺失率是PInst=主存延迟+传输1个Cache数据块需要使用的时间=40+32/4=48（周期）若为读失效，失效开销PReadF主存延迟+传输1个Cache数据块需要使用的时间=40+32/4=48（周期）若为写失效，且块是干净的，失效开销为PWrite_clean=主存延迟+传输1个Cache数据块需要使用的时间=40+32/4=48（周期）若为写失效，且块是修改过的，需要先把修改过的块写到主存，再载入新数据块，失效开销为PWrite_dirty=主存延迟