计算机系统结构习题课()-万继光讲解学习.ppt

《计算机系统结构习题课()-万继光讲解学习.ppt》由会员分享，可在线阅读，更多相关《计算机系统结构习题课()-万继光讲解学习.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 1/101/101计算机系统结构习题课()-万继光习题习题1.10计算机系统有三个部件可以改进，这三个部件的加速比如下：部件加速比130；部件加速比220；部件加速比310；(1)如果部件1和部件2的可改进比例为30，那么当部件3的可改进比例为多少时，系统的加速比才可以达到10？(2)如果三个部件的可改进比例为30、30和20，三个部件同时改进，那么系统中不可加速部分的执行时间在总执行时间中占的比例是多少？习题习题1.10习题习题1.11假设浮点数指令FP指令的比例为30%，其中其中浮点数平方根FPSQR占全部指令的比例为4%，FP操作的CPI为5，FPSQR操作的CPI为20，其他指令的

2、平均CPI为1.25。现有两种改进方案，第一种：把FPSQR操作的CPI减至3第二种：把所有的FP操作的CPI减至3试比较两种方案对系统性能的提高程度。v解法1：v利用原始CPI的唯一性，先使用已知条件求出原始CPI，再求出除去FPSQR指令外其他指令的平均CPI，最后比较改进后的CPI大小。v原始CPI=530%+1.25(1-30%)=2.375v设除FPSQR外其余指令的平均CPI为Xv则2.375=204%+(1-4%)X，解出X=1.640625v方案1：CPI1=34%+1.640625(1-4%)=1.695v方案2：CPI2=330%+1.25(1-30%)=1.775v结论：

3、方案1导致的新CPI更小，性能更好习题习题1.11v解法2：v用Amdahl公式求。记指令总条数=M，时钟周期长度=CYCLE。v原始总时间Told=0.3M5CYCLE+0.7M1.25CYCLEv=M2.375CYCLEvTFP=0.3M5CYCLE=M1.5CYCLE，v所占比例为1.5/2.37563%vTFPSQR=0.04M20CYCLE=M0.8CYCLE，v所占比例为0.8/2.37534%v方案1：Se=20/3，Fe34%，Sn1=1/(1-Fe)+Fe/Se1.4v方案2：Se=5/3，Fe63%，Sn2=1/(1-Fe)+Fe/Se1.3v结论：方案1导致加速比更大，性

4、能更好习题习题2.14（补充）（补充）vMIPS指令集。指令集。v人工模拟以下MIPS程序的单条指令运行方式，在表中用16进制编码记录每一步产生的结果（不得借助模拟软件）。v.datavn:.word3;n和x是偏移地址vx:.double0.5v.textvLDR1,n(R0);R1装入双字3(64位)vL.DF0,x(R0);F0装入双精度浮点数0.5(64位)vDADDIR2,R0,1;R21vMTC1R2,F11;把通用寄存器R2中的低32位传送到浮点寄存器F11的低32位vCVT.D.LF2,F11;把F11中的数据转换成双精度浮点数，送给F2。vloop:MUL.DF2,F2,F0

5、;F2F2*F0vDADDIR1,R1,-1;decrementR1by1vBNEZR1,loop;ifR10continuevHALT;此条不填表v：MIPS浮点数的格式是IEEE754习题习题2.14vIEEE754v为便于软件的移植，浮点数的表示格式应该有统一标准（定义）。1985年IEEE提出了IEEE754标准。v该标准规定基数为2，阶码E用移码表示，尾数M用原码表示，根据原码的规格化方法，最高数字位总是1，该标准将这个1缺省存储，使得尾数表示范围比实际存储的多一位。习题习题2.14v双精度浮点数类型类型数符数符阶码阶码尾数尾数总位数总位数指数偏移指数偏移短实数1位8位23位32位1

6、27长实数1位11位52位64位10230.5的二进制表示：0.1=1.0*(10)-1尾数：(1).0000阶码：-1+1023=0 x3fe 0 x3fe00000000000001的二进制表示：1.0=1.0*(10)0尾数(1).0000阶码：0+1023=0 x3ff 0 x3ff0000000000000习题习题2.14序号结果寄存器结果值（16进制）1R100000000000000032F03fe00000000000003R200000000000000014F1100000000000000015F23ff00000000000006F23fe00000000000007R

7、100000000000000028无无9F23fd000000000000010R1000000000000000111无无12F23fc000000000000013R1000000000000000014无无vn:.word3vx:.double0.5vvLDR1,n(R0)v L.DF0,x(R0)v DADDIR2,R0,1v MTC1R2,F11v CVT.D.LF2,F11vloop:MUL.DF2,F2,F0v DADDIR1,R1,-1v BNEZR1,loopv HALT习题习题3.8（时空图，性能指标）（时空图，性能指标）12345乘法加法tttt2t习题习题3.8如图，

8、在18个t时间中，给出了7个结果，所以TP=7/18t如果不用流水线，一次求积3t，一次求和5t，则T=(4*5+3*3)t=29t,因此S=29t/18t=1.61E=(4*5+3*3)/5*18=0.322考虑改为动态，怎么计算习题习题3.10（单功能非线性流水线调度）（单功能非线性流水线调度）v有一个5段流水线，各段执行时间均为t，其预约表如下 时间时间功能段功能段1234567S1S2S3S4S5(1)画出流水线任务调度的状态转移图。(2)分别求出允许不等时间间隔调度和等时间间隔调度的两种最优调度策略，以及这两种调度策略的流水线最大吞吐率。(3)若连续输入10个任务，求这两种调度策略的

9、流水线实际吞吐率和加速比。习题习题3.1010010110110110011110111155225544习题习题3.10（2）由状态转移图可得不发生段争用冲突的调度策略以及平均延迟时间如下所示。调度策略调度策略平均延迟时间平均延迟时间调度策略调度策略平均延迟时间平均延迟时间(2,2,5)3t(4,5)4.5t(2,5)3.5t(5)5t(4)4tu由上可知，允许不等时间间隔调度的最优调度策略是(2,2,5)，流水线最大吞吐率为：1/3t。u等时间间隔的调度的最优调度策略是(4)，流水线最大吞吐率为：1/4t。习题习题3.10习题习题3.11（相关，定向，指令调度）（相关，定向，指令调度）v在

10、改进的DLX流水线(按照图3.12)上运行如下代码序列：vLOOP:LWR1,0(R2)vADDIR1,R1,#1vSW0(R2),R1vADDIR2,R2,#4vSUBR4,R3,R2vBNZR4,LOOPv其中，R3的初始值是R2396。假设：在整个代码序列的运行过程中，所有的存储器访问都是命中的，并且在一个时钟周期中对同一个寄存器的读操作和写操作可以通过寄存器“定向”。问：v（1）在没有任何其它定向硬件的支持下，请画出该指令序列执行的流水线时空图。假设采用排空流水线的策略处理分支指令，且所有的存储器访问都可以命中Cache，那么执行上述循环需要多少个时钟周期？v（2）假设该DLX流水线有

11、正常的定向路径，请画出该指令序列执行的流水线时空图。假设采用预测分支失败的策略处理分支指令，且所有的存储器访问都可以命中Cache，那么执行上述循环需要多少个时钟周期？v（3）假设该DLX流水线有正常的定向路径，请对该循环中的指令进行调度。注意可以重新组织指令的顺序，也可以修改指令的操作数，但是不能增加指令的条数。请画出该指令序列执行的流水线时空图，并计算执行上述循环需要的时钟周期数？采用定向技术消除数据相关采用定向技术消除数据相关习题习题3.11（1）需要进行396/4=99次循环，由于每次分支都清空流水线。从上图可以看出每次循环需要17个时钟周期，因此总共需要的时钟周期数为99171168

12、412345678910111213141516171819LOOP:LWR10(R2)IFIDEXMWBADDIR1R1#1IFIDSSEXMWBSW0(R2)R1IFSSIDSSEXMWBADDIR2R2#4SSIFSSIDEXMWBSUBR4R3R2SSIFIDSSEXMWBBNZR4LOOPIFSSIDSS EXM WBIFSSSSIF习题习题3.11（2）需要进行396/4=99次循环，由于每次分支都清空流水线。从上图可以看出每次循环需要10个时钟周期，因此总共需要的时钟周期数为9910+1991123456789101112LOOP:LW R1 0(R2)IFIDEXMWBADDI

13、R1R1#1IFIDSEXMWBSW0(R2)R1IFSIDEXMWBADDIR2R2#4SIFIDEXMWBSUBR4R3R2IFIDEXMWBBNZR4LOOPIFIDEXMWBLW R1 0(R2)IFmissmissIF指令执行重新排序如下：lwr1,0(r2);加法寄存器R1取数(R2)addir2,r2,#4;指针R2指针R2+4addir1,r1,#1;R1R1+1Subr4,r3,r2;R4R3-R2bnezr4,Loop;若R40,循环sw-4(r2),r1;分支延迟槽，存数(R2-4)R1LOOP:LWR1,0(R2)ADDIR1,R1,#1SW0(R2),R1ADDIR2

14、,R2,#4SUBR4,R3,R2BNZR4,LOOPLOOP:LWR1,0(R2)ADDIR2,R2,#4ADDIR1,R1,#1SW0(R2),R1SUBR4,R3,R2BNZR4,LOOPLOOP:LWR1,0(R2)ADDIR2,R2,#4ADDIR1,R1,#1SW-4(R2),R1SUBR4,R3,R2BNZR4,LOOPLOOP:LWR1,0(R2)ADDIR2,R2,#4ADDIR1,R1,#1SUBR4,R3,R2BNZR4,LOOPSW-4(R2),R1习题习题3.11（3）习题习题3.11（3）有正常定向路径。单周期延迟分支。loop:lw r1,0(r2)addi r2

15、,r2,#4addi r1,r1,#1sub r4,r3,r2bnz r4,loopsw r1,-4(r2)第i次迭代（i 0.98）开始周期：1（i 6）总的时钟周期数：（986）10598习题习题5.8（分支预测技术）（分支预测技术）v假设有一条长流水线，仅仅对条件转移指令使用分支目标缓冲。假设分支预测错误的开销为4个时钟周期，缓冲不命中的开销为3个时钟周期。假设命中率为90%，预测精度为90%，分支频率为15%，没有分支的基本CPI为1。v（1）求程序执行的CPI。v（2）相对固定的2个时钟周期延迟的分支处理，哪种更快？v解：v（1）程序执行的CPI=没有分支的基本CPI+分支带来的额外

16、开销v额外开销=15%*(90%命中*10%预测错误*4+10%没命中*3)v=0.099所以程序执行的CPI=1+0.099=1.099。v（2）采用固定的2个时钟周期延迟的分支处理vCPI=1+15%*2=1.3v由（1）（2）知分支目标缓冲方法执行速度快。习题习题5.9（分支预测技术）（分支预测技术）v假定分支目标缓冲的命中率为90%，程序中无条件转移指令为5%，其它指令的CPI为1。假设分支目标缓冲包含分支目标指令,允许无条件转移指令进入分支目标缓冲,则CPI是多少。假定原来的CPI为1.1。v（1）原来不采用分支目标缓冲器BTB情况下v实际CPI=理想CPI+各种停顿拍数v=1+5%

17、L=1.1v解出L=2v（2）现在采用分支目标缓冲器BTB情况下v实际CPI=理想CPI+各种停顿拍数v=1+5%10%2=1.01习题习题5.11（超标量（超标量/超长指令字超长指令字/超流水）超流水）v设指令流水线由取指令,分析指令和执行指令3个部件构成,每个部件t,连续12条指令,分别画出ILP为4的超标量,超长指令字处理机和超流水线的时空图,并分别计算相对标量流水处理机的加速比.v1.标量流水处理机vTk=（k+n-1)t=(3+12-1)t=14tv2.超长指令字处理机v采用指令级并行技术，ILP=4,12个任务组装成3条长指令，每条含4条小指令，n=3。Tk=（k+n-1)t=(3

18、+3-1)t=5t，v加速比S=14t/5t=2.8习题习题5.11v3.超标量处理机vTk=(k+n-1)t=(3+3-1)tv=5tv加速比S=14t/5t=2.8v4.超流水处理机vILP=4,12个任务在4条时钟v依次错开0.25t的流水线上流过，v所以可取k=12,n=12,时钟=t/4。vTk=(k+n-1)t/4=(12+12-1)t/4=5.75t，v加速比S=14t/5.75t=2.435习题习题6.7（GCD测试方法）测试方法）v在使用GCD测试之前，必须先对这段代码进行“规范化”修改下标从1开始，而且每次循环后增加1。vFor(i=1;i=100;i+=2)ai=ai-1

19、;v规范化为：For(k=1;k=50;k+)a2K=a2K-1;v在这个循环中a=2，b=0，c=2，d=-1，v这样GCD(a,c)=2,d-b=-1，v由于前者不能够整除后者；v该循环不存在循环携带的真数据相关。习题习题6.8（循环展开）（循环展开）表表6.16.1本节使用的浮点流水线的延迟本节使用的浮点流水线的延迟产生结果的指令产生结果的指令使用结果的指令使用结果的指令延迟延迟(cycles)浮点计算浮点计算另一个浮点计算另一个浮点计算3浮点计算浮点计算浮点浮点store(S.D)2浮点浮点Load(L.D)浮点计算浮点计算1浮点浮点Load(L.D)浮点浮点store(S.D)0整数

20、运算，分支延迟和load需要一个周期延迟，如果分支的寄存器在前一条指令计算出，也需要一个周期延迟，因为整数计算在第3个周期完成，而分支第2个周期就用到DADDIU R1,R1,#-87(空转空转)8BNE R1,R2,Loop9 习题习题6.8在不进行指令调度的情况下，程序的实际执行情况如下：在不进行指令调度的情况下，程序的实际执行情况如下：指令流出时钟指令流出时钟Loop：L.D F0,0(R1)1L.D F4,0(R2)2(空转空转)3MUI.D F0,F0,F44(空转空转)5(空转空转)6(空转空转)7ADD.D F2,F0,F28DADDIU R1,R1,#-8 9DADDIU R2

21、,R2,#-810BNE R1,R3,Loop11(空转空转)12计算原程序周期数：计算原程序周期数：每对元素所需的时钟周期数每对元素所需的时钟周期数=12，其中空转数，其中空转数=5；习题习题6.8 新程序新程序vLoop:L.DF0,16(R1);F0A(i+2)L.DF4,16(R2);F4B(i+2)L.DF6,8(R1);F6A(i+1)MUL.DF0,F0,F4;F0A(i+2)B(i+2)L.DF8,8(R2);F8B(i+1)L.DF10,0(R1);F10A(i)MUL.DF6,F6,F8;F6A(i+1)B(i+1)ADD.DF2,F0,F2;F2F2+A(i+2)B(i+

22、2)L.DF12,0(R2);F12B(i)DADDUIR1,R1,-24;R1R1-24MUL.DF10,F10,F12;F10A(i)B(i)ADD.DF2,F6,F2;F2F2+A(i+1)B(i+1)DADDUIR2,R2,-24;R2R2-24BNER1,R3,loop;若R1R3,循环 (空转空转)ADD.DF2,F10,F2;F2F2+A(i)B(i)新程序周期数：每对元素所需的时钟周期数新程序周期数：每对元素所需的时钟周期数=16/3=5.3，其中空转数，其中空转数=1/3=0.3习题习题7.9（两级（两级Cache）v假设在3000次访存中，第一级cache不命中110次，第

23、二级cache不命中55次。试问：在这种情况下，该cache系统的局部不命中率和全局不命中率各是多少？v解：v第一级cache不命中率（全局和局部）是110/3000，即3.67%；v第二级cache的局部不命中率是55/110，即50%；v第二级cache的全局不命中率是55/3000，即1.83%。习题习题7.10（存储系统性能指标）（存储系统性能指标）习题习题7.10v平均访问时间命中时间失效率失效开销v平均访问时间1-路=2.0+1.4%*80=3.12nsv平均访问时间2-路=2.0*(1+10%)+1.0%*80=3.0nsv两路组相联的平均访问时间比较低vCPUtime=（CPU

24、执行+存储等待周期）*时钟周期vCPUtime=（IC*CPI执行+总访存失效次数*失效开销）*时钟周期v=IC*（CPI执行*时钟周期+每条指令的访存次数*失效率*失效开销*时钟周期）vCPUtime1-way=IC(2.0*2+1.2*0.014*80)5.344ICvCPUtime2-way=IC(2.2*2+1.2*0.01*80)5.36ICv相对性能比：5.36/5.344=1.003v直接映象的访问时间是两路组相联的1.04倍，v两路组相联的平均CPU时间是直接映象的1.003倍。v因此这里选择直接映象。习题习题7.11（伪相联）（伪相联）伪相联中，假设在直接映象位置没有发现匹配

25、，而在另一个位置才找到数据（伪命中）时，需要1个额外的周期，而且不交换两个Cache中的数据，失效开销为50个时钟周期。假设2KB直接映象Cache的总失效率为0.098，2路相联的总失效率为0.076；128KB直接映象Cache的总失效率为0.010，2路相联的总失效率为0.007。试求：（1）推导出平均访存的时间公式。（2）利用（1）中得到的公式，对于2KBCache和128KBCache，重新计算伪相联的平均访存时间。请问哪一种伪相联更快？习题习题7.11v命中时间伪相联命中时间1路伪命中率伪相联1v因此伪命中率伪相联命中率2路命中率1路（1失效率2路）（1失效率1路）失效率1路失效率

26、2路。v平均访存时间伪相联命中时间1路（失效率1路失效率2路）1失效率2路失效开销2路v将题设中的数据带入计算，得到：平均访存时间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（TLB）v（1）假设TLB不命中率=0vCache中50%的块修改过，所以不命中时，替换Cache需要1次从内存取一块，50%次写回一块，共1.5次。v均摊不命中开销=不命中率1.540+32B/4B+020v=不命中率72v实际CPI1=

27、1.5+1.2不命中率72=1.5+不命中率86.4v带入3种Cache结构的不命中率得：vCache结构不命中率实际CPIv16KB直接混合映像0.0294.0056v16KB两路混合映像0.0223.4008v32KB直接混合映像0.0203.2280习题习题7.12v（2）假设TLB不命中率=0.2%v均摊不命中开销=不命中率1.540+32B/4B+0.2%20v=不命中率1.548.04=不命中率72.06v实际CPI2=1.5+1.2不命中率72.06v=1.5+不命中率86.472v带入3种Cache结构的不命中率后得vCache结构不命中率实际CPIv16KB直接混合映像0.0

28、294.0077v16KB两路混合映像0.0223.4024v32KB直接混合映像0.0203.2294习题习题7.14v假设一台计算机具有以下特性：v95的访存在Cache中命中；v块大小为两个字，且失效时整个块被调入；vCPU发出访存请求的速率为109字/秒；v25的访存为写访问；v存储器的最大流量为109字/秒（包括读和写）；v主存每次只能读或写一个字；v在任何时候，Cache中有30的块被修改过；v写失效时，Cache采用写分配法。v试对于以下两种情况计算主存频带的平均使用比例。（1）写直达Cache；（2）写回法Cache。习题习题7.14（写策略）（写策略）v采用按写分配（1）写直

29、达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已用带宽=0.35109/10 9=35.0%习题习题7.14v（2）写回法c

30、ache访问命中,有两种情况：读命中，不访问主存；写命中，采用写回法，不访问主存。访问失效,有一个块将被换出，这也有两种情况：如果被替换的块没有修改过，将主存中的块调入cache块中，访存两次；如果被替换的块修改过，则首先将修改的块写入主存，需要访存两次；然后将主存中的块调入cache块中，需要访问主存两次，共四次访存。访问命中块为脏频率访存次数YN95%*70%=66.5%0YY95%*30%=28.5%0NN5%*70%=3.5%2NY5%*30%=1.5%4所以：一次访存请求最后真正的平均访存次数 =66.5*028.5%*0+3.5%*2+1.5%*4=0.13 已用带宽0.1310

31、9/10 913%习题习题8.11（I/O与与Cache数据一致性）数据一致性）假设在一个计算机系统中：（1）每页为32KB，Cache块大小为128B（2）对应新页的地址不在Cache中，CPU不访问新页中的任何数据；（3）Cache中95%的被替换块将再次被读取，引起一次不命中；（4）Cache使用写回方法，平均60%的块被修改过；（5）I/O系统缓冲能够存储一个完整的cache块（6）访问或不命中在所有cache块中均匀分布；（7）在CPU和I/O之间，没有其他访问cache的干扰；（8）无I/O时，每100万个时钟周期内有18000次不命中；（9）不命中开销是40个时钟周期，如果被替换

32、的块被修改过，则再加上30个周期用于写回主存；（10）假设计算机平均每200万个周期处理一页试分析I/O对于性能的影响有多大习题习题8.11v解：每个主存页有32K/128256块。v按块传输，I/O传输本身并不引起Cache失效。但可能要替换Cache中的有效块。如果替换块中有60被修改过，将需要25660304608个时钟周期将这些脏块写回主存。v替换出去的块中，有95的再次被访问，从而产生95256244次失效，将再次发生替换。由于这次被替换的244块中数据是从I/O直接写入Cache的，因此所有块都为被修改块，需要写回主存（因为CPU不会直接访问从I/O来的新数据），需要244（403

33、0）17080个时钟周期。v没有I/O时，每一页平均使用200万个时钟周期，Cache失效36000次，其中60被修改过，所需的IO时间为：v=36000403600060302088000（时钟周期）v时钟I/O造成的额外性能损失比例为v（460817080）（20000002088000）0.538.12（RAID系统，可靠性）系统，可靠性）v假定某网络型RAID系统包含6个SCSI磁盘，采用RAID1+0结构，对给定时间t，各部分可靠度为：网络接口通道NIC的R1=0.9，阵列控制器R2=0.95，SCSI通道适配器R3=0.95，磁盘R4=0.8。v（1）画出系统可靠性框图；v（2）写

34、出系统可靠性R的表达式，计算R的数值；v（3）提出进一步增强系统可靠性的若干建议。NIC阵列控制器SCSI通道适配器NICGGHHIIDDEEFFAABBCC习题习题8.12v（1）v（2）R=(1-(1-R1)2)R2R3(1-(1-R4)2)30.79v（3）采用双控制器、双SCSI适配器、提高数据冗余度、网络通道冗余度、提高各部分器件可靠度等。R1R1R2R3R4R4R4R4R4R4串联系统：串联系统：并联系统：并联系统：各种互连函数总结各种互连函数总结v交换置换函数定义:E(Xn-1Xn-2X1X0)=Xn-1Xn-2X1X0，其中0in-1v立方体函数定义：Cubei的功能是对入端结

35、点编号二进制形式的第i位取反vCubei(Xn-1Xi+1XiXi-1X0)=Xn-1Xi+1XiXi-1X0，其中0in-1v均匀洗牌 :shuffle（Xn-1Xn-2X0）=Xn-2X0Xn-1（循环左移）v蝶式互连函数butterfly ：最高位与最低位互换；v反位序函数 ：就是二进制各位次序颠倒过来；vPM2I函数定义：PM2i的功能是对入端结点编号加或减2i，然后再作模N运算vPM2+i（X）=X+2i mod NvPM2-i（X）=X-2i mod Nv 其中 X=0 N-1，i=0 n-1。习题习题9.9（单级互连网络）（单级互连网络）几个单级静态网络参数几个单级静态网络参数v

36、单级混洗交换网络网络的直径是2n-1。0和N-1的入度和出度各为1，其它的各为2；v单级PM2I网络2n-1种不同的置换，度为2n-1；单级PM2I网络的直径是vn-立方体中结点的度都是n，直径也是n，0 1 2 3 4 5 6 7习题习题9.9(2)25个结点的混洗交换网的直径是2n-1=25-1=9;从5号处理机（00101B）发送数据到7号处理机（00111B），最短路径要经过6步，包含5步左移和1步求反（因为00101BXOR00111B=00010B），经过的处理机编号为：00101B01010B 10100B 01001B 10010B 10011B 00111B（3）网络直径是5

37、/2=3；结点度是2n-1=25-1=9；与2号处理机距离最远的是13、15、21、23号处理机。习题习题9.13（多级互连网络）（多级互连网络）有log2N级，每级用N/2个22开关，共需要N/2*log2N个开关。用N=8的三级Omega网络连接8个处理机（P0P7），8个处理机的输出端分别依次连接Omega的8个输入端07，8个处理机的输入端分别依次连接Omega的8个输出端07，处理机P6要把数据播送到处理机P0P4，处理机P3要把数据播送到处理机P5P7，能否同时为它们的播送要求实现连接，画出开关状态图。习题习题10.6（并行处理对性能的提高）（并行处理对性能的提高）一个具有32台处

38、理机的系统，对远程存储器访问时间是2000ns。除了通信以外，假设计算中的访问均命中局部存储器。当发出一个远程请求时，本地处理机挂起。处理机的时钟周期是10ns，假设指令基本的CPI为1.0（假设所有访存均命中cache）。对于下述两种情况：（1）没有远程访问；（2）0.5%的指令需要远程访问.试问前者比后者快多少？解：远程访存时钟周期为2000/10=200则有远程访问情况CPI2=CPI1+pC=1+5%200=2因此前者比后者快1倍习题习题10.9（栅栏同步，旋转锁）（栅栏同步，旋转锁）采用排队锁和fetch-and-increment重新实现栅栏同步，并将分别与采用旋转锁实现的栅栏同步

39、进行性能对比。解：fetch-and-increment(count);if(count=total)/进程全部到达count=0;/重置计数器release=1;/释放进程else/还有进程未到达spin(release=1);/等待信号1.当有N个处理器时，上述代码执行fetch-and-increment操作N次次；2.当N-1个处理器第一次访问release时候，有N-1个cache未命中。3.当最后一个处理器到达栅栏条件后，release置为“1”，一次一次写操作；4.此时有N-1个release访问cache未命中。5.所以，共有3N-1次总线传输操作。如果有10个处理器，则共有2

40、9次总线传输操作，总共需要2900个时钟周期。旋转锁实现的栅栏同步性能旋转锁实现的栅栏同步性能第i个处理器通过栅栏产生的事件序列 事件 数量 对应源代码 说明LL i Lock(counterlock)；所有处理器抢锁SC i Lock(counterlock)；一个成功LD 1 count=count+1；读countSD 1 count=count+1；写countLL i-1 Lock(counterlock)；不成功的处理器再次抢锁SD 1 unlock(counterlock)；获得锁产生的失效LD 2 spin(release=1)；读release：初次和最后写产生的失效，最后一个处理器只需要1次写操作。因此对n个处理器，总线事务的总和为：n (3i+4)-1=(3n2+11n)/2-1 i=1对于10个处理器有204个总线事务，需要20400个时钟周期。Count=0应该也导致一次总线事务；习题习题10.95151/101/101此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢