计算机系统结构教程课后答案

....1.7400MHz和平均时钟周期数如下：指令类型指令执行数量平均时钟周期数整数450001数据传送750002浮点80004分支15002CPI、MIPS解：CPIi1

(CPIIC/IC)i i（1）CPI＝(45000×1＋75000×2＋8000×4＋1500×2)/129500＝1.776（2）MIPS速率＝f/CPI＝400/1.776＝225.225MIPS（3）程序执行时间=(45000×1＋75000×2＋8000×4＋1500×2)／400=575s1040%，则采用此增强功能方法后，能使整个系统的性能提高多少？解：由题可知：可改进比例Fe=40%=0.4 部件加速比Se=10T 1 1S 0 1.5625nTn根据

FeSe

(10.4)0.4/10计算机系统中有三个部件可以改进，这三个部件的部件加速比为部件加速比1=30； 部件加速比2=20；部件加速比3=1012310？如果三个部件的可改进比例分别为30%30%和进，那么系统中不可加速部分的执行时间在总执行时间中占的比例是多少？（）在多个部件可改进情况下，Amdahl定理的扩展：T 1nS 0nn T Fe1Fe2Fe3

Fe2

Fe3Se2 Se3已知S1＝30，S2＝20，S3＝10，Sn＝10，F1＝0.3，F2＝0.3，得：得F3＝0.36，即部件3的可改进比例为36%。（2）设系统改进前的执行时间为 T，则3 个部件改进前的执行时间为：（0.3+0.3+0.2）T=0.8T，不可改进部分的执行时间为1Fe1Fe2Fe3=0.2T。3S1＝30，S2＝20，S3＝103改进后的执行时间为：改进后整个系统的执行时间为：TnFe1Fe2Fe3

Fe2

Fe3Se2 Se3=0.045T+0.2T=0.245T那么系统中不可改进部分的执行时间在总执行时间中占的比例是：0.2/0.245=81.6%FPFPSQR4%，FPCPI5，FPSQRCPI20，其他指令CPI1.25。解：CPIi1

(CPIIC/IC)i i11010.570.35100.22111010.570.35100.22100.09100.0410.020.13设除FPSQR外其余指令的平均CPI为X则2.375=20×4%+(14%)XX=1.640625方案1：CPI1=3×4%+1.640625×(1-4%)=1.695方案2：CPI2=3×30%+1.25×(1-30%)=1.7752.11解：1000100.010.010.020.050.060.070.130.22043SHRSTPCILSTOJOMJMPSUBCLAADD..ADD0.430 . 1CLA0.22102SUB0.131103JMP0.07111005JOM0.06111015STO0.05111105CIL0.021111106SHR0.0111111107STP0.0111111117指令p操作码长度i操作码使用哈夫曼编码指令p操作码长度i操作码使用哈夫曼编码liiii1

=0.43x1+0.22x2+0.13x3+0.07x5+0.06x5+0.05x5+0.02x6+0.01x7+0.01x7=2.422.12．解：二地址指令的结构是（4OP），（6A1），（6位地址码A2）。（10OP），（6A）16条二地址指令。26所以一地址指令最多有（16-A）*26条指令译码需要一个时钟周期，MOVE、ADDMUL2个、3个4个时钟周期，每个操作都在第一个时钟周期从通用寄存器中读操作数，在最后一个时钟周期把运算结果写到通用寄存器中。k：MOVER1，R0；R1←(R0)k+1：MULR0，R2，R1；R0←(R2)×(R1)k+2：ADDR0，R2，R3；R0←(R2)+(R3)画出指令执行过程的流水线时空图，并计算完成这3时钟周期？解：相关，kR1的写在程序执行开始后的第四个时钟；k+1R1的读k+1k指令晚一个时钟进入流水线，则在R1....k+1R0的写对指令本身是第六个时钟，而要求该指令进入流水线R0的写是在程序执行开始后的第八k+2R0k+2k+1指令晚一个时钟进入流水线，则在程序执行开始后的第四个时钟，所以对R0的写是在程序执行开始后的第八个时钟。不能在同一时钟周期内写写同一寄存器，因k+2则程序指令执行过程的流水线时空图如下图所示。若3条指令顺序流动，共需9个时钟周期。空间K空间K存数K+1存数K+2存数时间运二K+1运二运一K+1运一K+2运一取数K取数K+1取数 K+2取数译码K译码K+1译码K+2译码取指 K取K+1取指K+2取指012345 6 78 9有一指令流水线如下所示入1234出50ns50ns100ns200ns10条指令，该流水线的实际吞吐率和效率；“瓶颈”在哪一段？请采取两种不同的措施消除此“颈”10条指令时，其实际吞吐率和效率各是多少？（）kT tk i1

(n

max(5050100200)92002200(ns)TPnTk

1220(ns1)ink tiE i1kk tii1i

(n1)max(t1

,t,,,t)km ti

400 5=TP

i1k

TP4

11（2）瓶颈在3、4段。变成八级流水线（细分）入出123_13_24_14_450ns入出123_13_24_14_450ns50ns50ns50ns50ns50nski1imaxk

(n1)t508950850(ns)TPnTk185(ns1)ETP

mi1

ti

TP

4001058.82%m 8 17重复设置部件4-14-13-14-2123-24-34-4..TPnTk185(ns1)段4_4484_3374_226104_11593_22468103_113579212345678 9101123456789850ns时间E400108508101758.82%434，问：时间输入任务时，该流水线会发生什么情况？2t10个任务时的实际吞吐率和效率是多少？10任务时，其吞吐率提高多少？S1 S2S3S3S4S1S2stallS3S3S4S1 S2S3S3S4S1S2stallS3S3S4S1S2stallstallS3S3S4S1S2stallstallstallS3 S3 S4务2务3务4务（2）时间段时间121234567891011223344556677889910101122334455667788991010321. 23t..TPmax

12tTpipelineTp

nTpipelinenT

1023tETP5t4509254.35%（3）重复设置部件3_113_11243_2Δt段121234567891022446688101011335577991234567891012345678910t3_23_121 时间TP

10 tnT14nT14

t57575757t1023t55、532△t，其余各段的时间均为△t，而且流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中。现要在该流水线上计算i1

(AB) ，画出其时空图，并计算其吞吐率、加速比和效率。i i2△2△t△t△t12345△t △t 乘法...解：首先，应选择适合于流水线工作的算法。对于本题，应先计算A1＋B1、A2＋B2A3＋B3(A1＋B1×(A2＋B2)和(A3＋B3×(A4＋B4)；然后求总的结果。其次，画出完成该计算的时空图，如图所示，图中阴影部分表示该段在工A=A＋B1 1B=A＋B2 2C=A＋B3 3D=A＋BA=A＋B1 1B=A＋B2 2C=A＋B3 3D=A＋B4 4段54321入输0 1 2 3A A A 入1 2 3

4 5 6 7 8

10 1112 13 14 15 1617 18 时间A C A×BB B B B1 2 3 4作。

B D C×D由图可见，它在18个△t时间中，给出了7个结果。所以吞吐率为：TP 718t3△t7结果共需（4×5+3×3）△t=29△t。所以加速比为：S29t18t

1.61该流水线的效率可由阴影区的面积和5个段总时空区的面积的比值求得：E45330.3225183.8有一条动态多功能流水线由5段组成，加法用1、3、4、5段，乘法用1、2、5段，第2段的时间为2△t，其余各段时间均为△t，而且流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中。若在该流水线上计算:

(Ai

B)i试计算其吞吐率、加速比和效率。

i1ABABCDA＋BC＋DA＋B＋C＋段543A=B=C=D=21输入010CD1112 13 14 15 161718时A1B1A＋BC＋D1 231 23456789A2A3A4AB2B3B4B..由图可见，它在18个△t时间中，给出了7个结果。所以吞吐率为：TP 718t4△t7结果共需（4×4+3×4）△t=28△t。所以加速比为：S28t18t

1.56该流水线的效率可由阴影区的面积和5个段总时空区的面积的比值求得：E 28518

0.3114.5在CRAY-14（括号中给出了相应功能部件的执行时间），如果向量寄存器和功能部件之间的数据传送需要试求此链接流水线的通过时间是多少拍？如果向量长度为64，则需多少拍才能得到全部结果？V0←存储器（从存储器中取数：7拍）V2←V0+V1（向量加：3拍）V3←V2<A3（按（A3）左移：4拍）V5←V3∧V4（向量逻辑乘：2拍）流水方式执行，直到整组向量执行完毕。a存储器a存储器dV0…dV11234567123…cVf2g…1jV3…j234Vi4…12lV5…向量加流水线左移流水线. 向量与流水线..(2)实际吞吐率为2*8*2(2)实际吞吐率为2*8*29(8*21) 501000=26.7MFLOPS4.8三条指令三个编队TnMVLT)mnstartloopT200=4x(15+Tstart)+200x3=660+(4xTstart)T通过＝（1+7+1）+(1+3+1)+(1+4+1)+(1+2+1)=24(拍T总共＝T通过+(64-1)=24+63＝87拍4.6 T通过＝（1+7+1）+(1+3+1)+(1+5+1)+(1+2+1)+(1+7+1)=34(拍T总共＝T通过+(64-1)=63+34＝97拍4.7某机有16V0～4.7某机有16V0～V5中分别放有向量ABCDE、F，向量长度均为8，向量各元素均为浮点数；处理部件采用二个单功能流水线，加法功能部件时间为拍，乘法功能部件时间为3拍。用类似Cray先计算(A+B)*C,在流水线不停流的情况下，接着计算(D+E)*F。解答：(1)(A+B)*C可用以下2条指令完成：V0←A+BV1←V0*C流水线流过时间为(1+2+1)+(1+3+1)=9拍分段开采LVV1，Rb;取向量BMULTVSV2，V1，Fs;向量和标量相乘SVRa，V2;存向量....Tstart=12+7+12=31Tstart=12+7+12=31T200=660+4x31=7844.9解：Rlim向量指令序列中浮点运算次数时钟频率n向量指令序列执行所需的时钟周期数CrayY-MP/8(1+1)×8/(6x10-3162667MFLOPS假设有一条长流水线，仅仅对条件转移指令使用分支目标缓冲。假设分支4390%90%15%CPI1。①求程序执行的CPI。2更快？（）程序执行的CPI=没有分支的基本CP（1）+分支带来的额外开销与缓冲没有命中带来的开销之和。分支带来的额外开销=15%*(90%命中×10%预测错误×4+10％不命中×3)=0.099所以，程序执行的CPI＝1＋0.099=1.099（2）采用固定的2个时钟周期延迟的分支处理CPI=1+15%×2=1.3由（（2）可知分支目标缓冲方法执行速度快。90%CPICPI值为多少？CPI=1.1参考答案：x1＋5%×x＝1.1x＝2当分支目标缓冲命中时，无条件转移指令的延迟为0。所以程序的CPI＝1＋2×5%×(1－90%)＝1.017.8.Cache75%；而对数据Cache的访问占全25%Cache150个时钟周CacheloadstoreCache的命中时间都要增加一CacheCache的Cache0.95%Cache和数据Cache32KB的分离Cache64KB的混合CacheCache的不命中率更低？两种情况下平均访存时间各是多少？参考答案：（）根据题意，约75%的访存为取指令，25的访存为数据。因此，分离Cache（75×0.15%）＋25%×3.77）＝1.055%；容量为64KB的混合Cache的不命中率略低一些，只有0.95%。（2）平均访存时间公式可以分为指令访问和数据访问两部分：平均访存时间＝指令所占的百分比×（读命中时间＋读不命中率×不命中开销）＋数据所占的百分比×（数据命中时间＋数据不命中率×不命中开销）所以，两种结构的平均访存时间分别为：分离Cache的平均访存时间＝75%×（1＋0.15%×50）＋25%×（1＋3.77%×50）＝（75%×1.075）＋（25%×2.885）＝1.5275因为混合Cache读数据的都要增加1个时钟周期所以混合Cache的平均访存时间＝75%×（1＋0.95%×50）＋25%×（1＋1＋0.95%×50）＝（75%×1.475）＋（25%×2.475）＝1.725CacheCacheCache提供了两个端口，消除了结构相关。3000Cache110Cache55Cache解：局部不命中率=该级Cache的不命中次数/到达该级Cache的访存次数。局部不命中率L1=110/3000=0.0367，不命中率L2=55/110=0.50。全局不命中率L1=不命中率L1=0.0367，全局不命中率L2=L1L2。给定以下的假设，试计算直接映象CacheCacheCPU的性能。由计算结果能得出什么结论？(1)CacheCPI1.2(2)Cache64KB32字节；(3)CacheCPU(4)Cache80ns；1个时钟周期；64KBCache1.4％，64KBCache1.0％。解：平均访问时间＝命中时间＋不命中率×不命中开销路路路路

=2.0+1.4%*80=3.12ns=2.0*(1+10%)+1.0%*80=3.0ns两路组相联的平均访问时间比较低CPUtime=（CPU

+存储等待周期）*时钟周期执行CPUtime=IC（CPI

+总不命中次数/指令总数*不命中开销）*时钟周期执行时钟周期）

*时钟周期）+（每条指令的访存次数*不命中率*不命中开销*执行CPUtime1-way=IC(2.0*2+1.2*0.014*80)＝5.344ICCPUtime2-way=IC(2.2*2+1.2*0.01*80)＝5.36ICCPU

CPU

time2way

5.36/5.344=1.003cachecache1.04倍，而两路组相联Cache的平均性能比直接映象cache要高1.003倍。因此这里选择两路组相联7.14假设一台计算机具有以下特性：95Cache中命中；块大小为两个字，且不命中时整个块被调入；CPU109字/s；25％的访存为写访问；存储器的最大流量为19字/s（包括读和写；主存每次只能读或写一个字；在任何时候，Cache30％的块被修改过；写不命中时，Cache采用按写分配法。试对于以下两种情况计算主存频带的平均使用比例。Cache；Cache解：采用按写分配cache读命中，不访问主存；cache访问不命中，有两种情况：读不命中，将主存中的块调入cache中，访问主存两次；cache，访问主存两次，再将修改的cache示。访问命中访问类型频率访存次数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已用带宽=35.0%cache访问命中,读命中，不访问主存；cache出时，才写入主存；访问不命中,有一个块将被换出，这也有两种情况：如果被替换的块没有修改过，将主存中的块调入cache块中，访问主存两次；cache存。访问命中块为脏频率访存次数YN95%*70%=66.5%0YY95%*30%=28.5%0NN5%*70%=3.5%2NY5%*30%=1.5%4所以：一次访存请求最后真正的平均访存次数=66.5％*0＋28.5%*0+3.5%*2+1.5%*4=0.13已用带宽＝13%9.29.2(1)由Cube3(X3X2X1X0)=X3X2X1X0Cube3(0110)=1110 146令Cube3(X3X2X1X0)=0110,得X3X2X1X0=1110Cube3(0110)=1110 146所以处理器14和6双向互连由

(3)

(XX3

XX)=XXXX1 0 3 1 0 2(3)

(0110)=（0101）即处理器5连接到处理器63 2 1 令 (XXXX))=（0110）得XXXX3 2 1 (3) 3 2 1 0所以处理器5和6连，3和5连XX3 2

XX)=X1 0

XXX2 1 3(0110) =（0110）66所以处理器6和6双向互连(4)由XX3 2

XX)=X1 0

XXX3 1 0（2）(0110)=（1010）即处理器10连接到处理器63 2 1 令（2）(XXXX))=（0110）得3 2 1 3 2 1 0所以处理器6和10双向互连9.9(1)Cube2(X4X3X2X1X0)=X3X3X2X1X0Cube2(12)=Cube2(01100)=01000 812由X4

XXXX3 2 1

)=XXXXX3 2 1 0 4(8)(01000)(10000) 16连接到处理器(C)由PM2I (j)=j23mod323PM2I (28)=2823mod324 4283Cube0

(X4

XXXX3 2 1

))Cube0

(XX3

XX1 0

)=X4 3

XXX2 1 0 Cube(4))Cube(00100))=01001980 00 4

XXXX3 2 1

))(X4

XXX3 2

X)=XXXXX0 3 2 1 0 4(Cube（18))(Cube（10010))00111即处理器7连接到处理器280 02n个节点的直径为2n-1，从5号到7号，最短经过600101 00100 01000 01001 10010 10011 00111d=2n-1,n/2网络直径是3，节点度是9，与2号最远的是13,15,21,23号处理器9.110123456789ABCDEF4组4元32107654BA98FEDC2组8元45670123CDEF89AB116元BA98FEDC321076540000-10110000-1011Cube0+Cube1+Cube310.6.32400ns外，假设计算中的访问均命中局部存储器。当发出一个远程请求时，本处1GHzIPC2(0.2%的指令需要远程访问的状态下，前者比后者快多少?解:没有远程访问时，机器的CPI为1/基本IPC=1/2=0.5有0.2%远程访问的机器的实际CPI为CPI＝基本CPI＋远程访问率×远程访问开销＝0.5＋0.2%×远程访问开销远程访问开销为：远程访问时间/时钟周期时间＝400ns/1ns＝400个时钟周期∴CPI＝0.5＋0.2%×400＝1.30.2%1.3/0.5=2.6倍。7.11在伪相联中，假设在直接映象位置没有发现匹配，而在另一个位置才找到数据（伪命中）1周期50个时钟周期，2KBCache的不命中率为9.8%，27.6%；128KBCache的不命中率为%，20.7%。推导出平均访存时间的公式。利用2KBCache128KBCache相联的平均访存时间。解：不管作了何种改进，不命中开销相同。不管是否交换内容，在同一“伪相联”组中的两块都是用同一个索引得到的，因此不命中率相同，即：不命中率

＝伪相联2不命中率 。2路伪相联cache的命中时间等于直接映象cache的命中时间加上伪相联查找过程中的命中时间*该命中所需的额外开销。

＝

路

×1伪相联交换或不交换内容，伪相联的命中率都是由于在第一次不命中时，将地址取反，再在第二次查找带来的。

＝

－命中率1路1

＝（1－不命中率2路2

）－（1－不路1命中率 ）1路

＝

2－不命中率2路

。交换内容需要增加伪相联路的额外开销。

＝

＋（路

1路1

）×12路2＋不命中率2将题设中的数据带入计算，得到：

×不命中开销1路 路1平均访存时间2Kb=1+(0.098-0.076)*1+(0.076*50)=4.822平均访存时间128Kb=1+(0.010-0.007)*1+(0.007*50)=1.353显然是128KB的伪相联Cache要快一些。7.12假设采用理想存储器系统时的基本CPI是1.5404字节Cache50%32字节，20%TLB不命中的情况20CacheCPUCache0.2%TLB中找到。在理想TLB16KB直接