计算机系统结构习题课(2011)

1、高级计算机系统结构习题课题目讲解2012-1-4第一章 计算机设计基本原理 Amdahl定律可改进比例：该部件的原执行时间在原系统总执行时间中所占的比例部件加速比可改进比例可改进比例）（总执行时间总执行时间系统加速比改进后改进前-11例题选讲（1）例例1 1 假设将某系统的某一部件的处理速度加快到10倍，但该系统的原处理时间仅为整个运行时间的40，则采用加快措施后能使整个系统的性能提高多少？方法一：依 Amdahl定律公式，已知：Fe=0.4，Se=10，求Sn。它说明局部（40%）的大幅度改进（10倍）对全局的作用要小得多（1.56倍）。111.560.40.6410.410nS 方法二：4

2、06044060例题选讲（2） 例例2：计算机系统中有三个部件可以改进，这三个部件的部件加速比如下： 部件加速比130； 部件加速比220； 部件加速比310；如果相对某个测试程序三个部件的可改进比例分别为20，20%，70%，要达到最好改进效果，仅对一个部件进行改进时，选择那个部件？如果运行两个部件，又如何选择？例题2的解答对于瓶颈部分进行改进可以获得最大的改进效果。（第一问）66. 5302 . 0107 . 02 . 07 . 011nS7.2107.07.011nS对于瓶颈部分进行改进可以获得最大的改进效果。（第二问）同样情况下使用改进加速比大的方法CPU的性能公式CPI是衡量CPU执

3、行指令效率的重要指标。让我们先考虑一个标准测速程序的全部执行时间Te和其中所有第i种指令的累计时间Ti，易知的加权平均值。为所有，它表明 ）（ 或者写为）（ 的关系CPI与CPI一式，可以得到比较上面第一式与最后)()( 写另一方面，我们又可以 ， 1 其中： 11i1111iniiiniiiniiiniiiniieniiiiieCPICPICPIICICCPICPIICCPIICCYCLECPIICCYCLECPIICTTICICfCYCLECYCLECPIICTCYCLECPIICT例题选讲（3）Typical MixBase Machine (Reg / Reg)OpFreqCycles

4、CPI(i)(% Time)ALU50%1 .5(33%)Load20%2 .4(27%)Store10%2 .2(13%)Branch20%2 .4(27%) 1.5例题选讲（4）CPU能耗问题:CPU的动态功率为: unitsiiiidynfAVCkP2例例4 4 某8核CPU能够动态启动和关闭工作的核，假设某一程序80%部分可以并行执行，下面有两个调度方案，不考虑L1，L2$对于计算过程的影响，CPI在两种情况下都不变； T0为程序原来执行的时间，P0为单核执行不改变时的功率。请分别计算该程序运行在两种情况下的实际功耗实际功耗。（1）只使用一个核，其它核关闭，CPU电压增加10%，主频增

5、加20%；（2）使用全部8个核，CPU电压增加10%，主频不变解答 T0为程序原来执行的时间，P0为单核执行不改变时的功率，其执行程序的总能耗为W0= T0*P0（1）T1=T0/（1+0.2）=(5/6)T0； P1=（1+10%）2* （1+20% ）* P0 =1.452* P0 W1=T1* P1=1.167 W0（2） T2=(20%+80%/8)*T0=30%T0 P2=（1+10%）2* 8* P0 =9.68 W2=T2* P2=2.904 W0 流水段任何指令类型IFIF/ID.IR MemPC;IF/ID.NPC,PC (if EX/MEM.cond EX/MEM.NPC

6、else PC+4);IDID/EX.A RegsIF/ID.IR6.10; ID/EX.B RegsIF/ID.IR11.15;ID/EX.NPC IF/ID.NPC;ID/EX.IR IF/ID.IR;ID/EX.Imm (IR16)16#IR16.31;ALU指令Load/Store指令分支指令EXEX/MEM.IR ID/EX.IR;EX/MEM.IR ID/EX.IR; EX/MEM.ALUoutput ID/EX.A + ID/EX.Imm;EX/MEM.ALUoutput EX/MEM.ALUoutput ID/EX.NPC + D/EX.Imm;ID/EX.A op ID/EX

7、.BEX/MEM.cond 或(ID/EX.A op 0);EX/MEM.ALUoutput ID/EX.A op ID/EX.Imm;EX/MEM.cond 0;MEMMEM/WB.IR MEM/WB.IR EX/MEM.IR;EX/MEM.IR;MEM/WB.LMD MEM/WB.ALUoutput MemEX/MEM.ALUoutput;EX/MEM.ALUoutput;或MemEX/MEM.ALUoutput EX/MEM.B;WBRegsMEM/WB.IR16.20 MEM/WB.ALUoutput;RegsMEM/WB.IR11.15 MEM/WB.LMD;或例题选讲（5） 在DL

8、X流水线上运行如右代码序列。其中，R3的初值是R2396。假设，在整个代码序列的运行过程中，所有的存储器访问都是命中的，并且在一个时钟周期中对同一个寄存器的读操作和写操作可以通过寄存器文件定向。问： LOOP:LWR10(R2)ADDIR1R1#1SWR10(R2)ADDIR2R2#4SUBR4R3R2BNZR4LOOP1.在没有定向（或旁路）硬件的支持下，请画出该指令序列执行的流水线时空图。假设采用排空流水线的策略处理分支指令，且所有的存储器访问都可以命中Cache，那么执行上面循环需要多少时钟周期2.假设该DLX流水线有正常的定向路径，请画出该指令序列执行的流水线时空图。假设采用预测分支失

9、败的策略处理分支指令，其所有的存储器访问都可以命中Cache，那么执行上面循环需要多少时钟周期 123456789101112131415161718192021LOOP:LWR10(R2)IFIDEXMEMWBADDIR1R1#1IFIDSSEXMEMWBSW0(R2)R1IFSSIDSSEXMEMWBADDIR2R2#4SSIFSSIDEXMEMWBSUBR4R3R2SSIFIDSSEXMEMWBBNZR4LOOPIFSSIDSSEXMEMIF需要进行396/4=99次循环，由于每次分支都清空流水线。从上图可以看出每次循环需要16个时钟周期，因此总共需要的时钟周期数为99161584(或1

10、583)表3.5列出了在改进后的流水线数据通路上处理分支指令的一些操作123456789101112131415161718192021LOOP:LWR10(R2)IFIDEXMEMWBADDIR1R1#1IFIDSEXMEMWBSW0(R2)R1IFSIDEXMEMWBADDIR2R2#4SIFIDEXMEMWBSUBR4R3R2IFIDEXMEMWBBNZR4LOOPIFID-sIDEXMEMIFiiiLWR10(R2)IF需要进行396/4=99次循环，由于每次分支预测都失败，并且在ID段需要计算分支目标和分支条件。从上图可以看出每次循环需要9个时钟周期，因此总共需要的时钟周期数为989

11、+10892（或者891）例题选讲（6） 在下面Tomasulo结构上执行指令，分别计算每条指令写结果阶段的时间（时钟周期数），并画出相应的时空图。FP addersAdd1Add2Add3FP multipliersMult1Mult2From MemFP RegistersReservation StationsCommon Data Bus (CDB)To MemFP OpQueueLoad BuffersStore BuffersLoad1Load2Load3Load4Load5Load6LatencyLDF634+R21LDF245+R31MULTDF0F2F410SUBDF8F6F

12、22DIVDF10F0F640ADDD F6F8F22LDF634+R2IES EC WLDF245+R3IES EC WMULTDF0 F2 F4ISES EEEEEEEEEEC WSUBDF8 F6 F2IES EEC WDIVDF10F0 F6ISSSSSSSSSSES EEEEC WADD F6 F8 F2ISESEECWTomasulo ExampleInstruction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R2Load1NoLDF245+R3Load2NoMULTDF0F2F4Load3

13、NoSUBDF8F6F2DIVDF10F0F6ADDDF6F8F2Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1NoAdd2NoAdd3NoMult1NoMult2NoRegister result status:ClockF0F2F4F6F8F10F12.F300FUTomasulo Example Cycle 1Instruction status:ExecWriteInstructionjkIssueComp ResultBusyAddressLDF634+R21Load1Yes34+R2LDF245+R3Load2NoM

14、ULTDF0F2F4Load3NoSUBDF8F6F2DIVDF10F0F6ADDDF6F8F2Reservation Stations:S1S2RSRSTimeNameBusyOpVjVkQjQkAdd1NoAdd2NoAdd3NoMult1NoMult2NoRegister result status:ClockF0F2F4F6F8F10F12.F301FULoad1Tomasulo Example Cycle 2Instruction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R21Load1Yes3

15、4+R2LDF245+R32Load2Yes45+R3MULTDF0F2F4Load3NoSUBDF8F6F2DIVDF10F0F6ADDDF6F8F2Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1NoAdd2NoAdd3NoMult1NoMult2NoRegister result status:ClockF0F2F4F6F8F10F12.F302FULoad2Load1Tomasulo Example Cycle 3Instruction status:ExecWriteInstructionjkIssue Comp Res

16、ultBusy AddressLDF634+R213Load1Yes34+R2LDF245+R32Load2Yes45+R3MULTDF0F2F43Load3NoSUBDF8F6F2DIVDF10F0F6ADDDF6F8F2Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1NoAdd2NoAdd3NoMult1Yes MULTDR(F4) Load2Mult2NoRegister result status:ClockF0F2F4F6F8F10F12.F303FUMult1Load2Load1Tomasulo Example Cyc

17、le 4Instruction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R2134Load1NoLDF245+R324Load2Yes45+R3MULTDF0F2F43Load3NoSUBDF8F6F24DIVDF10F0F6ADDDF6F8F2Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1YesSUBD M(A1)Load2Add2NoAdd3NoMult1Yes MULTDR(F4) Load2Mult2NoRegister resul

18、t status:ClockF0F2F4F6F8F10F12.F304FUMult1Load2M(A1) Add1Tomasulo Example Cycle 5Instruction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F43Load3NoSUBDF8F6F24DIVDF10F0F65ADDDF6F8F2Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQk2 Add1Y

19、esSUBD M(A1) M(A2)Add2NoAdd3No10 Mult1Yes MULTDM(A2) R(F4)Mult2YesDIVDM(A1) Mult1Register result status:ClockF0F2F4F6F8F10F12.F305FUMult1 M(A2)M(A1) Add1Mult2Tomasulo Example Cycle 6Instruction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F

20、43Load3NoSUBDF8F6F24DIVDF10F0F65ADDDF6F8F26Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQk1 Add1YesSUBD M(A1) M(A2)Add2Yes ADDD M(A2) Add1Add3No9 Mult1Yes MULTDM(A2) R(F4)Mult2YesDIVDM(A1) Mult1Register result status:ClockF0F2F4F6F8F10F12.F306FUMult1 M(A2)Add2Add1Mult2Tomasulo Example Cycle 7In

21、struction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F43Load3NoSUBDF8F6F247DIVDF10F0F65ADDDF6F8F26Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQk0 Add1YesSUBD M(A1) M(A2)Add2Yes ADDD M(A2) Add1Add3No8 Mult1Yes MULTDM(A2) R(F4)Mult2Ye

22、sDIVDM(A1) Mult1Register result status:ClockF0F2F4F6F8F10F12.F307FUMult1 M(A2)Add2Add1Mult2Tomasulo Example Cycle 8Instruction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F43Load3NoSUBDF8F6F2478DIVDF10F0F65ADDDF6F8F26Reservation Stations:S

23、1S2RSRSTime NameBusyOpVjVkQjQkAdd1No2 Add2Yes ADDD (M-M) M(A2)Add3No7 Mult1Yes MULTDM(A2) R(F4)Mult2YesDIVDM(A1) Mult1Register result status:ClockF0F2F4F6F8F10F12.F308FUMult1 M(A2)Add2 (M-M) Mult2Tomasulo Example Cycle 9Instruction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R21

24、34Load1NoLDF245+R3245Load2NoMULTDF0F2F43Load3NoSUBDF8F6F2478DIVDF10F0F65ADDDF6F8F26Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1No1 Add2Yes ADDD (M-M) M(A2)Add3No6 Mult1Yes MULTDM(A2) R(F4)Mult2YesDIVDM(A1) Mult1Register result status:ClockF0F2F4F6F8F10F12.F309FUMult1 M(A2)Add2 (M-M) Mult

25、2Tomasulo Example Cycle 10Instruction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F43Load3NoSUBDF8F6F2478DIVDF10F0F65ADDDF6F8F2610Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1No0 Add2Yes ADDD (M-M) M(A2)Add3No5 Mult1Yes MULTDM(A

26、2) R(F4)Mult2YesDIVDM(A1) Mult1Register result status:ClockF0F2F4F6F8F10F12.F3010FUMult1 M(A2)Add2 (M-M) Mult2Tomasulo Example Cycle 11Instruction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F43Load3NoSUBDF8F6F2478DIVDF10F0F65ADDDF6F8F2610

27、11Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1NoAdd2NoAdd3No4 Mult1Yes MULTDM(A2) R(F4)Mult2YesDIVDM(A1) Mult1Register result status:ClockF0F2F4F6F8F10F12.F3011FUMult1 M(A2)(M-M+M) (M-M) Mult2Tomasulo Example Cycle 12Instruction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressL

28、DF634+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F43Load3NoSUBDF8F6F2478DIVDF10F0F65ADDDF6F8F261011Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1NoAdd2NoAdd3No3 Mult1Yes MULTDM(A2) R(F4)Mult2YesDIVDM(A1) Mult1Register result status:ClockF0F2F4F6F8F10F12.F3012FUMult1 M(A2)(M-M+M) (M-M) Mult2To

29、masulo Example Cycle 13Instruction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F43Load3NoSUBDF8F6F2478DIVDF10F0F65ADDDF6F8F261011Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1NoAdd2NoAdd3No2 Mult1Yes MULTDM(A2) R(F4)Mult2YesDIVDM

30、(A1) Mult1Register result status:ClockF0F2F4F6F8F10F12.F3013FUMult1 M(A2)(M-M+M) (M-M) Mult2Tomasulo Example Cycle 14Instruction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F43Load3NoSUBDF8F6F2478DIVDF10F0F65ADDDF6F8F261011Reservation Stat

31、ions:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1NoAdd2NoAdd3No1 Mult1Yes MULTDM(A2) R(F4)Mult2YesDIVDM(A1) Mult1Register result status:ClockF0F2F4F6F8F10F12.F3014FUMult1 M(A2)(M-M+M) (M-M) Mult2Tomasulo Example Cycle 152/9/2009CS252-S09, Lecture 634Instruction status:ExecWriteInstructionjkIssue Comp ResultB

32、usy AddressLDF634+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F4315Load3NoSUBDF8F6F2478DIVDF10F0F65ADDDF6F8F261011Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1NoAdd2NoAdd3No0 Mult1Yes MULTDM(A2) R(F4)Mult2YesDIVDM(A1) Mult1Register result status:ClockF0F2F4F6F8F10F12.F3015FUMult1 M(A2)(M-M+M)

33、 (M-M) Mult2Tomasulo Example Cycle 16Instruction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F431516Load3NoSUBDF8F6F2478DIVDF10F0F65ADDDF6F8F261011Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1NoAdd2NoAdd3NoMult1No40 Mult2YesDIVD

34、M*F4 M(A1)Register result status:ClockF0F2F4F6F8F10F12.F3016FUM*F4 M(A2)(M-M+M) (M-M) Mult2Tomasulo Example Cycle 57Instruction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F431516Load3NoSUBDF8F6F2478DIVDF10F0F655657ADDDF6F8F261011Reservati

35、on Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1NoAdd2NoAdd3NoMult1NoMult2YesDIVDM*F4 M(A1)Register result status:ClockF0F2F4F6F8F10F12.F3056FUM*F4 M(A2)(M-M+M) (M-M) Result例题选讲（7） 考察如下循环程序 for (i=1; i=100; i=i+1) Ai = Ai + Bi; /* S1 */Bi+1 = Ci + Di+1; /* S2 */S1与S2之间存在何种相关关系？这个循环程序是否可以并行，若可以，如何使其并行

36、？解：S1中使用的值是上次循环S2计算的结果，即S2和S1之间存在循环体间相关；但S2并不相关于S1。只要相关关系不形成环状，循环程序就可以并行。1.不存在S1到S2的相关路径，因此可以把S1和S2对调不影响S2的执行；2.在第一次循环中，S1中使用初始值B1，是在循环初始化之前就已经计算出来A1=A1+B1;for (i=1; i=100; i=i+1) Bi+1 = Ci + Di+1; Ai+1 = Ai+1 + Bi+1; B101 = C100 + D100现在这两条语句之间不再存在循环体间的相关关系，从而可以让不同循环体的语句重叠执行。例题选讲（8）某人按照标准五段流失线设计7段顺

37、序发射流水线，增加指令和数据cache存取阶段到2个时钟周期，如上图所示。并且流水线不具有任何分支预测机制。并且分支计算比较简单，不需要ALU操作。请问：（1）在此流水线中分支目标最早在那个段获得；（2）分支产生多少时钟的延迟（3）假设1/6的指令是分支指令，并且3/5分支成功，并且CPI为1，请问此流水线CPI是多少答（1）Decode （2）2 （3）1+1/6*3/5*2=1.2例题选讲（9）一个程序放在6个内存块中, 运行时分给该程序的Cache块为3个块, 每个内存块都可以放在这3个Cache块中的任意位置，执行的顺序如下: P1,P2,P3,P4,P2,P3,P5,P5,P4,P6

38、,P3,P3,P2,P1,P5 画FIFO，LRU替换方法的调度过程图, 若调入和命中都算命中, 标出两种方法的命中率.时间123456789101112131415块地址流P1P2P3P4P2P3P5P5P4P6P3P3P2P1P5FIFO算法P1P1*P1*P4P4P4P4P4P4P4*P3P3P3P3*P5P2P2P2*P2*P2*P5P5P5P5P5*P5*P2P2P2*P3P3P3P3P3*P3*P3*P6P6P6P6*P1P1入入入替中中替中中替替中替替替时间123456789101112131415块地址流P1P2P3P4P2P3P5P5P4P6P3P3P2P1P5LRU算法P1

39、P1*P1*P4P4P4*P5P5P5P5*P3P3P3P3*P5P2P2P2*P2P2P2*P2*P4P4P4*P4*P2P2P2P3P3P3*P3P3P3P3*P6P6P6P6*P1P1入入入替中中替中替替替中替替替例题选讲（10）在某个Cache 中, 主存有32块(0-31), Cache 有8块(0-7), 分为4组, 每块的大小为32 个字节1. 写出主存地址格式, 并标出各字段长度;2. 在一个采用组相连映像方式下，写出Cache 地址格式, 并标出各字段长度;3. 主存27块单元的数据可能会放Cache 中的那些块?4. 若Cache 2, 7块被占用,主存123H(16进制)单元的数据可能会放Cache 中的那些块? 43 Cache01234567Memory 1111111111222222222233012345678901234567890123456789012-Way Assoc(12 mod 4) = 0解答1.主存的地址为10位（32个块，每块32个字节）2.Cache的地址为8位（8个块，每块32个字节）3.27MOD43，也就是映射到第四组内，也就是Cache中的6,7两块中4.127H/20H9，也就是内存中第9块中， 9MOD41也就是映射到cache中的第二组内，第2块被占用，所以放在cac