计算机系统结构习题课-10级

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

2、044060例题选讲（2） 计算机系统中有三个部件可以改进，这三个部件的部件加速比如下： 部件加速比130； 部件加速比220； 部件加速比310；如果某个测试程序在三个部件上的比例分别为20，20%，70%，要达到最好改进效果，仅对一个部件进行改进时，选择那个部件？如果运行两个部件，又如何选择？例题2的解答对于瓶颈部分进行改进可以获得最大的改进效果。（第一问）66. 5302 . 0107 . 02 . 07 . 011nS7.2107.07.011nSCPU的性能公式CPI是衡量CPU执行指令效率的重要指标。让我们先考虑一个标准测速程序的全部执行时间Te和其中所有第i种指令的累计时间Ti，

3、易知的加权平均值。为所有，它表明）（或者写为）（的关系与一式，可以得到比较上面第一式与最后写另一方面，我们又可以，iniiiniiiniiiniiiniieniiiiieCPICPICPIICICCPICPIICCPIICCYCLECPIICCYCLECPIICTTICICfCYCLECYCLECPIICTCYCLECPIICT CPICPI)()( 1 其中： 11i1111例题选讲（3）Typical MixBase Machine (Reg / Reg)OpFreqCyclesCPI(i)(% Time)ALU50%1 .5(33%)Load20%2 .4(27%)Store10%2 .

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

5、； 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 例题选讲（5） 在DLX流水线上运行如右代码序列。其中，R3的初值是R2396。假设，在整个代码序列的运行过程中，所有的存储器访问都是命中的，并且在一个时钟周期中对同一个寄存器的读操作和写操作可以通过寄存器文件定向。问： 表3.5列出了在改进后的流水线数据通路上处理分支指令的一些操作例题选讲（6） 在下面Tomasulo结构上执行指令，分别

6、计算每条指令写结果阶段的时间（时钟周期数），并画出相应的时空图。FP addersAdd1Add2Add3FP multipliersMult1Mult2From MemFP RegistersReservation StationsCommon Data Bus (CDB)To MemFP OpQueueLoad BuffersStore BuffersLoad1Load2Load3Load4Load5Load6LatencyLDF634+R21LDF245+R31MULTDF0F2F410SUBDF8F6F22DIVDF10F0F640ADDD F6F8F22LDF634+R2IES EC

7、 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+R3Load2NoMULTDF0F2F4Load3NoSUBDF8F6F2DIVDF10F0F6ADDDF6F8F2Reservati

8、on Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1NoAdd2NoAdd3NoMult1NoMult2NoRegister result status:ClockF0F2F4F6F8F10F12.F300FUTomasulo Example Cycle 1Instruction status:ExecWriteInstructionjkIssueComp ResultBusyAddressLDF634+R21Load1Yes34+R2LDF245+R3Load2NoMULTDF0F2F4Load3NoSUBDF8F6F2DIVDF10F0F6ADDD

9、F6F8F2Reservation Stations:S1S2RSRSTimeNameBusyOpVjVkQjQkAdd1NoAdd2NoAdd3NoMult1NoMult2NoRegister result status:ClockF0F2F4F6F8F10F12.F301FULoad1Tomasulo Example Cycle 2Instruction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R21Load1Yes34+R2LDF245+R32Load2Yes45+R3MULTDF0F2F4Load

10、3NoSUBDF8F6F2DIVDF10F0F6ADDDF6F8F2Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1NoAdd2NoAdd3NoMult1NoMult2NoRegister result status:ClockF0F2F4F6F8F10F12.F302FULoad2Load1Tomasulo Example Cycle 3Instruction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R213Load1Yes34+R2LDF

11、245+R32Load2Yes45+R3MULTDF0F2F43Load3NoSUBDF8F6F2DIVDF10F0F6ADDDF6F8F2Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1NoAdd2NoAdd3NoMult1Yes MULTDR(F4) Load2Mult2NoRegister result status:ClockF0F2F4F6F8F10F12.F303FUMult1Load2Load1Tomasulo Example Cycle 4Instruction status:ExecWriteInstructio

12、njkIssue Comp ResultBusy AddressLDF634+R2134Load1NoLDF245+R324Load2Yes45+R3MULTDF0F2F43Load3NoSUBDF8F6F24DIVDF10F0F6ADDDF6F8F2Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1YesSUBD M(A1)Load2Add2NoAdd3NoMult1Yes MULTDR(F4) Load2Mult2NoRegister result status:ClockF0F2F4F6F8F10F12.F304FUMult1

13、Load2M(A1) Add1Tomasulo Example Cycle 5Instruction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F43Load3NoSUBDF8F6F24DIVDF10F0F65ADDDF6F8F2Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQk2 Add1YesSUBD M(A1) M(A2)Add2NoAdd3No10 Mult1Yes

14、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+R3245Load2NoMULTDF0F2F43Load3NoSUBDF8F6F24DIVDF10F0F65ADDDF6F8F2

15、6Reservation 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 7Instruction status:ExecWriteInstructionjkIss

16、ue Comp ResultBusy AddressLDF634+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F43Load3NoSUBDF8F6F247DIVDF10F0F65ADDDF6F8F26Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQk0 Add1YesSUBD M(A1) M(A2)Add2Yes ADDD M(A2) Add1Add3No8 Mult1Yes MULTDM(A2) R(F4)Mult2YesDIVDM(A1) Mult1Register result status:Clo

17、ckF0F2F4F6F8F10F12.F307FUMult1 M(A2)Add2Add1Mult2Tomasulo Example Cycle 8Instruction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F43Load3NoSUBDF8F6F2478DIVDF10F0F65ADDDF6F8F26Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1No2 Add2

18、Yes 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+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F43Lo

19、ad3NoSUBDF8F6F2478DIVDF10F0F65ADDDF6F8F26Reservation 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) Mult2Tomasulo Example Cycle 10Instruction stat

20、us:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F43Load3NoSUBDF8F6F2478DIVDF10F0F65ADDDF6F8F2610Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1No0 Add2Yes ADDD (M-M) M(A2)Add3No5 Mult1Yes MULTDM(A2) R(F4)Mult2YesDIVDM(A1) Mult1Register re

21、sult status:ClockF0F2F4F6F8F10F12.F3010FUMult1 M(A2)Add2 (M-M) Mult2Tomasulo Example Cycle 11Instruction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F43Load3NoSUBDF8F6F2478DIVDF10F0F65ADDDF6F8F261011Reservation Stations:S1S2RSRSTime NameBu

22、syOpVjVkQjQkAdd1NoAdd2NoAdd3No4 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 AddressLDF634+R2134Load1NoLDF245+R3245Load2NoMULTD

23、F0F2F43Load3NoSUBDF8F6F2478DIVDF10F0F65ADDDF6F8F261011Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1NoAdd2NoAdd3No3 Mult1Yes MULTDM(A2) R(F4)Mult2YesDIVDM(A1) Mult1Register result status:ClockF0F2F4F6F8F10F12.F3012FUMult1 M(A2)(M-M+M) (M-M) Mult2Tomasulo Example Cycle 13Instruction status:

24、ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F43Load3NoSUBDF8F6F2478DIVDF10F0F65ADDDF6F8F261011Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1NoAdd2NoAdd3No2 Mult1Yes MULTDM(A2) R(F4)Mult2YesDIVDM(A1) Mult1Register result status:ClockF0F2

25、F4F6F8F10F12.F3013FUMult1 M(A2)(M-M+M) (M-M) Mult2Tomasulo Example Cycle 14Instruction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F43Load3NoSUBDF8F6F2478DIVDF10F0F65ADDDF6F8F261011Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1No

26、Add2NoAdd3No1 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 ResultBusy AddressLDF634+R2134Load1NoLDF245+R3245

27、Load2NoMULTDF0F2F4315Load3NoSUBDF8F6F2478DIVDF10F0F65ADDDF6F8F261011Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1NoAdd2NoAdd3No0 Mult1Yes MULTDM(A2) R(F4)Mult2YesDIVDM(A1) Mult1Register result status:ClockF0F2F4F6F8F10F12.F3015FUMult1 M(A2)(M-M+M) (M-M) Mult2Tomasulo Example Cycle 16Instr

28、uction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F431516Load3NoSUBDF8F6F2478DIVDF10F0F65ADDDF6F8F261011Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQkAdd1NoAdd2NoAdd3NoMult1No40 Mult2YesDIVDM*F4 M(A1)Register result status:ClockF0F2

29、F4F6F8F10F12.F3016FUM*F4 M(A2)(M-M+M) (M-M) Mult2Tomasulo Example Cycle 57Instruction status:ExecWriteInstructionjkIssue Comp ResultBusy AddressLDF634+R2134Load1NoLDF245+R3245Load2NoMULTDF0F2F431516Load3NoSUBDF8F6F2478DIVDF10F0F655657ADDDF6F8F261011Reservation Stations:S1S2RSRSTime NameBusyOpVjVkQjQ

30、kAdd1NoAdd2NoAdd3NoMult1NoMult2YesDIVDM*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之间存在何种相关关系？这个循环程序是否可以并行，若可以，如何使其并行？解：S1中使用的值是上次循环S2计算的结果，即S2和S1之间存在循环体间相关；但S

31、2并不相关于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段顺序发射流水线，增加指令和数据cache存取阶段到2个时钟周期，如上图所示。并且流水线

32、不具有任何分支预测机制。并且分支计算比较简单，不需要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,P3,P3,P2,P1,P5 画FIFO，LRU替换方法的调度过程图, 若调入和命

33、中都算命中, 标出两种方法的命中率.时间123456789101112131415块地址流P1P2P3P4P2P3P5P5P4P6P3P3P2P1P5FIFO算法P1P1*P1*P4P4P4P4P4P4P4*P3P3P3P3*P5P2P2P2*P2*P2*P5P5P5P5P5*P5*P2P2P2*P3P3P3P3P3*P3*P3*P6P6P6P6*P1P1入入入替中中替中中替替中替替替时间123456789101112131415块地址流P1P2P3P4P2P3P5P5P4P6P3P3P2P1P5LRU算法P1P1*P1*P4P4P4*P5P5P5P5*P3P3P3P3*P5P2P2P2*P2

34、P2P2*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也就是映射到ca