并行体系结构(陈国良版)课后答.pdf

《并行体系结构(陈国良版)课后答.pdf》由会员分享，可在线阅读，更多相关《并行体系结构(陈国良版)课后答.pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 习题设计计划1指导思想要求学生理解高端并行计算机系统设计技术，高端MPP、DSM、CLUSTER 等大规模并行计算机的关键设计理论和实现技术，包括互连网络技术、存储架构和高可用技术等。为此，必须用适量的作业、习题，启发学生独立思考以及熟练掌握一些基础知识和基本技能。2作业安排本教材每一章都附有大量的习题，根据教学进度和学时，合理选择书上习题，以达到进一步加深理解课堂讲授的内容。每一章讲授结束，收一次作业，给出成绩，并作一次集体答疑，讲解作业中的共性问题。作业成绩记入总成绩内。第一章绪论1.1 什么是并行计算机？答：简单地讲，并行计算机就是由多个处理单元组成的计算机系统，这些处理单元相互通信

2、和协作，能快速高效求解大型的复杂的问题。1.2 简述 Flynn 分类法：答：根据指令流和数据流的多重性将计算机分为：1）单指令单数据流SISD 2）单指令多数据流SIMD 3）多指令单数据流MISD 4）多指令多数据流MIMD 1.3 简述当代的并行机系统答：当代并行机系统主要有：1）并行向量机（PVP）2）对称多处理机（SMP）3）大规模并行处理机（MPP）4）分布式共享存储（DSM）处理机5）工作站机群（COW）1.4 为什么需要并行计算机？答：1）加快计算速度2）提高计算精度3）满足快速时效要求4）进行无法替代的模拟计算1.5 简述处理器并行度的发展趋势答：1）位级并行2）指令级并行3

3、）线程级并行1.6 简述 SIMD 阵列机的特点答：1）它是使用资源重复的方法来开拓计算问题空间的并行性。2）所有的处理单元（PE）必须是同步的。3）阵列机的研究必须与并行算法紧密结合，这样才能提高效率。2 21m4）阵列机是一种专用的计算机，用于处理一些专门的问题。1.7 简述多计算机系统的演变答：分为三个阶段：1）1983-1987 年为第一代，代表机器有：Ipsc/1、Ameteks/14 等。2）1988-1992 年为第二代，代表机器有：Paragon、Intel delta 等。3）1993-1997 年为第三代，代表机器有：MIT 的 J-machine。1.8 简述并行计算机的

4、访存模型答：1）均匀存储访问模型（UMA）2）非均匀存储访问模型（NUMA）3）全高速缓存存储访问模型（COMA）4）高速缓存一致性非均匀访问模型（CC-NUMA）1.9 简述均匀存储访问模型的特点答：1）物理存储器被所有处理器均匀共享。2）所有处理器访问任何存储字的时间相同。3）每台处理器可带私有高速缓存。4）外围设备也可以一定的形式共享。1.10 简述非均匀存储访问模型的特点答：1）被共享的存储器在物理上分布在所有的处理器中，其所有的本地存储器的集合构成了全局的地址空间。2）处理器访问存储器的时间不一样。3）每台处理器可带私有高速缓存，外备也可以某种的形式共享。第二章性能评测2.1 使用

5、40MHZ 主频的标量处理器执行一个典型测试程序，其所执行的指令数及所需的周期数如表2.13 所示。试计算执行该程序的有效CPI、MIPS 速率及总的CPU 执行时间。解：CPI=total cycles/total instructions=（45000*1+32000*2+15000*2+8000*2）/（45000+32000+15000+8000）=1.55 MIPS=时钟频率/(CPI*106)=(40*106)/(1.55*106)=25.8 CPU 执行时间=total cycles/时钟频率=0.00375s 2.2 欲在 40MHZ 主频的标量处理器上执行20 万条目标代码指

6、令程序。假定该程序中含有4种主要类型之指令，各指令所占的比例及CPI 数如表 2.14 所示，试计算：在单处理机上执行该程序的平均CPI。由所得结果，计算相应的MIPS速率。解：（1）CPI=1*60%+2*18%+4*12%+8*10%=2.12（2）MIPS=时钟频率/(CPI*106)=(40*106)/(2.12*106)=18.9 2.1 2.3 已知 SP2并行计算机的通信开销表达式为：t（m）=46+（0.035）m，试计算：渐近带宽r=?半峰值信息长度=?提示：to=46s 解：（1）渐近带宽r=1/0.035=28.6MB/S(2)半峰值消息长度m1/2=to*r=46us*

7、28.6MB/S=1315.6B 2.4 并行机性能评测的意义。答：意义有：1）发挥并行机长处，提高并行机的使用效率。3 2）减少用户购机盲目性，降低投资风险。3）改进系统结构设计，提高机器的性能。4）促进软/硬件结合，合理功能划分。5）优化“结构-算法-应用”的最佳组合。6）提供客观、公正的评价并行机的标准。2.5 如何进行并行机性能评测答：1）机器级性能评测：CPU 和存储器的某些基本性能指标；并行和通信开销分析；并行机的可用性与好用性以及机器成本、价格与性/价比。2）算法级性能评测：加速比、效率、扩展性。3）程序级性能评测：Benchmark。2.6 简述 Gustafson 定律的出发

8、点答：1）对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。此时为了提高精度，必须加大计算量，相应地亦必须增多处理器数才能维持时间不变。2）除非学术研究，在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器上，增多处理器必须相应地增大问题规模才有实际意义。2.7 已知一程序可并行代码占比例为80%，将其在有10 个处理器的系统中运行，求其加速比？并求其极限加速比？并分析其结构带来的影响解：加速比=1/(20%+80%/10)=1/(0.2+0.08)=3.57。极限加速比，即处理器个数无穷大的时候呈现的加速比=1/20%=5。这个极限加速比，换

9、个角度说是，Amdahl 定律在很长一段时间影响了人们对开发并行计算机的信心，对于本例，因为就算你把处理器做到无穷也只能得到5倍的加速比，同时有一点更明显，就是处理器数目增加到一定程度后，加速比的增长非常缓慢。2.8 简述影响加速的因素答：1）求解问题中的串行分量。2）并行处理器所引起的额外开销。3）加大的处理器数超过的算法的并发程度。2.9 为什么增加问题规模可以在一定程度提高加速答：1）较大的问题规模可提高较大的并发度。2）额外开销的增加可能慢于有效计算的增加。3）算法中串行分量的比例不是固定不变的。2.10 进行可扩放行研究的主要意义答：1）确定解决某类问题用某类并行算法和某类并行体系结

10、构结合，可以有效的利用大量的处理器。2）对于运行于某种体系结构的并行机的某种算法当移到大规模处理机上的性能。3）对于某类固定规模的问题，确定在某类并行机上的最优处理器数目和最大的加速比。4）用于指导改进并行算法和并行体系结构，以使并行算法能尽可能充分利用可扩充的。大量的处理器。第三章互连网络3.1 对于一颗K 级二叉树（根为0 级，叶为 k-1 级），共有 N=2k-1 个节点，当推广至m-元树时（即每个非叶节点有m 个子节点）时，试写出总节点数N 的表达式。答：推广至 M 元树时，k 级 M 元树总结点数N 的表达式为：N=1+m1+m2+.+m（k-1）=(1-mk)*1/(1-m);4

11、3.2 二元胖树如图3.46 所示，此时所有非根节点均有2个父节点。如果将图中的每个椭圆均视为单个节点，并且成对节点间的多条边视为一条边，则他实际上就是一个二叉树。试问：如果不管椭圆，只把小方块视为节点，则他从叶到根形成什么样的多级互联网络？答：8 输入的完全混洗三级互联网络。3.3 四元胖树如图3.47 所示，试问：每个内节点有几个子节点和几个父节点？你知道那个机器使用了此种形式的胖树？答：每个内节点有4 个子节点，2 个父节点。CM-5 使用了此类胖树结构。3.4 试构造一个N=64 的立方环网络，并将其直径和节点度与N=64 的超立方比较之，你的结论是什么？答：A N=64 的立方环网络

12、,为 4 立方环（将 4 维超立方每个顶点以4 面体替代得到），直径d=9，节点度n=4 B N=64 的超立方网络，为六维超立方（将一个立方体分为8 个小立方，以每个小立方作为简单立方体的节点，互联成6 维超立方），直径 d=6，节点度n=6 3.5 一个 N=2k 个节点的de Bruijin 网络如图3.48 所示，令ak 1ak2ak 3。a1a0，是一个节点的二进制表示，则该节点可达如下两个节点：ak 2ak 3。a1a00，ak 2ak 3。a1a01。试问：该网络的直径和对剖宽度是多少？答：N=2k 个节点的de Bruijin 网络直径 d=k 对剖宽带w=2(k-1)3.6

13、一个 N=2n 个节点的洗牌交换网络如图3.49 所示。试问：此网络节点度=？网络直径=？网络对剖宽度=？答：N=2n 个节点的洗牌交换网络，网络节点度为=2，网络直径=n-1，网络对剖宽度=4 3.7 一个 N=（k+1）2k 个节点的蝶形网络如图3.50 所示。试问：此网络节点度=？网络直径=？网络对剖宽度=？答：N=（k+1）2k 个节点的蝶形网络，网络节点度=4，网络直径=2*k，网络对剖宽度=2k 3.9 对于如下列举的网络技术，用体系结构描述，速率范围，电缆长度等填充下表中的各项。（提示：根据讨论的时间年限，每项可能是一个范围）答：网络技术网络结构带宽铜线距离光纤距离Myrinet

14、 专用机群互联网络200MB/秒25m 500m HiPPI 用于异构计算机和其外设的组网800Mbps1.6Gbps 25m 300m10km SCI 可扩展一致性接口，通常独立于拓扑结构250Mbps8Gbps 光纤通信多处理器和其外围设备之间，直连结构100Mbps800Mbps 50m 10km ATM 主要应用于因特网主干线中25Mbps10Gbp5 s FDDI 采用双向光纤令牌环，所有结点联接在该环中100-200Mbps 100m 2KM 3.10 如图 3.51 所示，信包的片0，1，2，3 要分别去向目的地A，B，C，D。此时片0 占据信道 CB，片 1 占据信道DC，片

15、2 占据信道AD，片 3 占据信道BA。试问：1）这将会发生什么现象？2）如果采用X-Y 选路策略，可避免上述现象吗？为什么？答：1）通路中形成环，发生死锁2）如果采用X-Y 策略则不会发生死锁。因为采用X-Y 策略时其实质是对资源（这里是通道）进行按序分配（永远是x 方向优先于y 方向，反方向路由是y 方向优先于x 方向），因此根据死锁避免的原则判断，此时不会发生死锁。3.12 在二维网孔中，试构造一个与X-Y 选路等价的查表路由。答：所构造路由表描述如下：1）每个节点包括两张路由表x 表和 y 表2）每个节点包含其以后节点信息，如节点【1，2】x 表内容为:【2，2】【3，2】y 表内容为

16、：【1，3】选路方法：节点路由时进行查表：先查x 表即进行x 方向路由，如果查表能指明下一跳方向则直接进入下一跳。如果不能则继续查y 表，直到到达目的地。第四章对称多处理机系统4.1 参照图 4.20，试解释为什么采用WT 策略进程从2P迁移到1P时，或采用WB 策略将包含共享变量X 的进程从1P迁移到2P时，会造成高速缓存的不一致。P1X处理器高速缓存共享存储器迁移写通写总线XP2P1XXXP2P1XXXP2过回之前图 4.20 进程迁移所造成的不一致性答：采用 WT 策略进程从2P迁移到1P后，2P写共享变量X 为 X，并且更新主存数据为X，此时1P共享变量值仍然为X，与2P和主存 X 不

17、一致。采用 WB 策略进程从1P迁移到2P后，1P写共享变量X 为 X，但此时2P缓存与主存变量值仍然为X，造车不一致。4.2 参照图4.21 所示，试解释为什么：在采用WT 策略的高速缓存中，当I/O 处理器将6 一个新的数据X写回主存时会造成高速缓存和主存间的不一致；在采用WB 策略的高速缓存中，当直接从主存输出数据时会造成不一致。P1处理器I/O（写直达）总线XXP2P1XXP2P1XXP2XXXXX存储器存储器存储器输入()输出()（写回）高速缓存I/O 处理机图 4.21 绕过高速缓存的I/O 操作所造成的不一致性答：中 I/O 处理器将数据X 写回主存，因为高速缓存采用WT策略，此

18、时P1和 P2相应的高速缓存值还是X，所以造成高速缓存与主存不一致。直接从主存输出数据X，因为高速缓存采用WB 策略，可能高速缓存中的数据已经被修改过，所以造成不一致。4.3 试解释采用WB 策略的写更新和写无效协议的一致性维护过程。其中X为更新前高速缓存中的拷贝，X为修改后的高速缓存块，I 为无效的高速缓存块。（b）处理器P1执行写无效操作后IxIP1P2PnIxxx（c）处理器P1执行写更新操作后PnP2P1高速缓存拷贝x高速缓存行共享存储器侦听总线xxx处理器（a）写操作前P1P2PnI答：处理器P1 写共享变量X 为 X，写更新协议如图(c)所示，同时更新其他核中存在高速缓存拷贝的值为

19、X;写无效协议如图(b)所示，无效其他核中存在高速缓存拷贝，从而维护了一致性过程。4.4 两种基于总线的共享内存多处理机分别实现了Illinois MESI 协议和 Dragon 协议，对于下面给定的每个内存存取序列，试比较在这两种多处理机上的执行代价，并就序列及一致性协议的特点来说明为什么有这样的性能差别。序列r1 w1 r1 w1 r2 w2 r2 w2 r3 w3 r3 w3；序列 r1 r2 r3 w1 w2 w3 r1 r2 r3 w3 w1；序列 r1 r2 r3 r3 w1 w1 w1 w1 w2 w3；所有的存取操作都针对同一个内存位置，r/w 代表读/写，数字代表发出该操作的

20、处理器。假设所有高速缓存在开始时是空的，并且使用下面的性能模型：读/写高速缓存命中，代价1 个时钟周期；缺失引起简单的总线事务（如BusUpgr，BusUpd），60个时钟周期；缺失引起整个高速缓存块传输，90 时钟周期。假设所有高速缓存是写回式。答：读写命中、总线事务、块传输分别简记为H、B、T。MESI协议：BTH H H H BTH BH H H BTH BH H H 共 5B+12H+3T=582时钟周期 BTH BTH BTH BH BTH BTH BTH BTH H BH BTH 共10B+12H+8T=1330时钟周期 BTH BTH BTH H BH H H H BTH BTH

21、 共 6B+10H+4T=730时钟周期。Dragon 协议：BTH H H H BTH BTH H BTH BTH BTH H BTH 共 7B+12H+7T=882时钟周期BTH BTH BTH BTH BTH BTH H H H H BTTH BTH 共 8B+12H+8T=1212时钟周期 BTH BTH BTH H BTH BTH BTH BTH BTH BTH 共 9B+10H+9T=1360时钟周期。由结果得出，、序列用MESI协议时间更少，而序列用Dragon 协议时间更少。综上可知，如果同一块在写操作之后频7 繁被多个核读操作采用Dragon 协议更好一些，因为 Dragon

22、 协议写操作后会更新其它核副本。如果一个同多次连续对同一块进行写操作MESI协议更有效，因为它不需要更新其它核副本，只需要总线事务无效其它核即可。4.5 考虑以下代码段，说明在顺序一致性模型下，可能的结果是什么？假设在代码开始执行时，所有变量初始化为0。a.P1 P2 P3 A=1 U=A V=B B=1 W=A b.P1 P2 P3 P4 A=1 U=A B=1 W=B V=B X=A 答：顺序一致性模型性下，保护每个进程都按程序序来发生内存操作，这样会有多种可能结果，这里假设最简单情况，即 P1、P2、P3 依次进行。则 a中 U=V=W=1，b 中 U=X=W=1，V=0。4.6 参照

23、4.6.1 中讨论多级高速缓存包含性的术语，假设L1 和 L2 都是 2-路组相联，n2n1，b1=b2，且替换策略用FIFO 来代替 LRU，试问包含性是否还是自然满足？如果替换策略是随机替换呢？答：如果采用FIFO 替换策略包含性自然满足，因为L1 和 L2 都是 2 路组相联，FIFO 保证了 L1 与 L2 在发生替换时会换出相同的缓存块，维护了包含性。如果采取随机替换策略，存在 L1 与 L2 替换不是相同块的情况，故不满足包含性。4.7 针对以下高速缓存情况，试给出一个使得高速缓存的包含性不满足的内存存取序列？L1 高速缓存容量32 字节，2-路组相联，每个高速缓存块8 个字节，使

24、用LRU 替换算法；L2 高速缓存容量128 字节，4-路组相联，每个高速缓存块8 个字节，使用LRU 替换算法。答：假设m1、m2、m3 块映射到一级Cache 和二级 Cache 的同一组中，考虑如下内存存取序列 Rm1，Rm2，Rm1，Rm3，由 LRU 替换算法知道，当Rm3执行后，L1 中被替换出的是m2，L2 中被替换出的是m1，此时 m1 块在 L1 却不在 L2 中，不满足包含性。4.8 在 4.6 中关于分事务总线的讨论中，依赖于处理器与高速缓存的接口，下面情况有可能发生：一个使无效请求紧跟在数据响应之后，使得处理器还没有真正存取这个高速缓存块之前，该高速缓存块就被使无效了。

25、为什么会发生这种情况，如何解决?答：考虑如下情景：SMP 目录一致性协议中，核1 读缺失请求数据块A，主存响应请求传送数据块 A 给核 1，同时核 2 对数据块A 进行写操作，到主存中查得核1 拥有副本，向核 1发使无效请求。如此，一个使无效请求紧跟在数据响应之后。解决方法，可以使每个核真正存取高速缓存块后向主存发回应，然后再允许其它对此块操作的使无效或其它请求。4.9 利用 LL-SC 操作实现一个Test&Set 操作。答：Test&Set：ll reg1,location/*Load-locked the location to reg1*/bnz reg1,lock/*if locat

26、in was locked,try again*/8 mov reg2,1/*set reg2 1*/sc location,reg2/*store reg2 conditional into location*/4.10 在 4.7.4 部分描述具有感觉反转的路障算法中，如果将Unlock 语句不放在if 条件语句的每个分支中，而是紧接放在计数器增1 语句后，会发生什么问题？为什么会发生这个问题？答：再进入下一个路障时可能会发生计数器重新清0 现象，导致无法越过路障。考虑如下情景：第一次进入路障时，最后两个进入路障的进程分别为1、2。假设最后进入路障的进程为2 进程，2 进程执行共享变量加一

27、操作并解锁。然后2 进程执行一条if 条件语句，此时由于某种原因换出或睡眠，而此时共享变量的值已经为p。如果 1 进程此时正执行 if 条件语句，则清零计数器，设置标志，其它进程越过路障。到目前为止没有出现问题，问题出现在下一次进入路障。进程再一次进入路障，此时会执行共享变量加一操作。如果此时2 进程被换入或被唤醒，会重新清零共享变量，使之前到达路障的进程的加一操作无效，导致无法越过路障。第五章大规模并行处理机系统5.1 简述大规模并行处理机的定义，原理和优点？答：并行处理机有时也称为阵列处理机，它使用按地址访问的随机存储器，以单指令流多数据流方式工作，主要用于要求大量高速进行向量矩阵运算的应

28、用领域。并行处理机的并行性来源于资源重复，它把大量相同的处理单元（PE）通过互联网络（ICN）连接起来，在统一的控制器（CU）控制下，对各自分配来的数据并行地完成同一条指令所规定的操作。PE 是不带指令控制部件的算术逻辑运算单元。并行处理机具有强大的向量运算能力，具有向量化功能的高级语言编译程序有助于提高并行处理机的通用性，减少编译时间。5.2 并行处理机有两种基本结构类型，请问是哪两种？并作简单介绍。答：采用分布存储器的并行处理结构和采用集中式共享存储器的并行处理结构。分布式存储器的并行处理结构中，每一个处理机都有自己的存储器，只要控制部件将并行处理的程序分配至各处理机，它们便能并行处理，各

29、自从自己的存储器中取得信息。而共享存储多处理机结构中的存储器是集中共享的，由于多个处理机共享，在各处理机访问共享存储器时会发生竞争。因此，需采取措施尽可能避免竞争的发生。5.3 简单说明多计算机系统和多处理机系统的区别。答：他们虽然都属于多机系统但是他们区别在于：（1）多处理机是多台处理机组成的单机系统，多计算机是多台独立的计算机。（2）多处理机中各处理机逻辑上受同一的OS 控制，而多计算机的OS 逻辑上独立.(3)多处理机间以单一数据，向量。数组和文件交互作用，多计算机经通道或者通信线路以数据传输的方式进行。（4）多处理机作业，任务，指令，数据各级并行，多计算机多个作业并行。5.4 举例说明

30、MPP 的应用领域及其采用的关键技术。答：全球气候预报，基因工程，飞行动力学，海洋环流，流体动力学，超导建模，量子染色动力学，视觉。采用的关键技术有VLSI，可扩张技术，共享虚拟存储技术。5.5 多处理机的主要特点包括答：（1）结构的灵活性。与SIMD计算机相比，多处理机的结构具有较强的通用性，它可以9 同时对多个数组或多个标量数据进行不同的处理，这要求多处理机能够适应更为多样的算法，具有灵活多变的系统结构。2）程序并行性。并行处理机实现操作一级的并行，其并行性存在于指令内部，主要用来解决数组向量问题；而多处理机的并行性体现在指令外部，即表现在多个任务之间。3）并行任务派生。多处理机是多指令流

31、操作方式，一个程序中就存在多个并发的程序段，需要专门的程序段来表示它们的并发关系以控制它们的并发执行，这称为并行任务派生。4）进程同步。并行处理机实现操作级的并行，所有处于活动状态的处理单元受一个控制器控制，同时执行共同的指令，工作自然同步；而多处理机实现指令、任务、程序级的并行，在同一时刻，不同的处理机执行着不同的指令，进程之间的数据相关和控制依赖决定了要采取一定的进程同步策略。5.6 在并行多处理机系统中的私有Cache 会引起 Cache 中的内容相互之间以及与共享存储器之间互不相同的问题，即多处理机的Cache一致性问题。请问有哪些原因导致这个问题？答：1）出现 Cache 一致性问题

32、的原因主要有三个：共享可写的数据、进程迁移、I/O 传输。共享可写数据引起的不一致性。比如P1、P2 两台处理机各自的本地高速缓冲存储器C1、C2中都有共享存储器是M 中某个数据X 的拷贝，当P1 把 X 的值变成X/后，如果P1 采用写通过策略，内存中的数据也变为X/，C2 中还是 X。如果通过写回策略，这是内存中还是X。在这两种情况下都会发生数据不一致性。2）进程迁移引起的数据不一致性。P1 中有共享数据 X 的拷贝，某时刻P1 进程把它修改为X/并采用了写回策略，由于某种原因进程从P1迁移到了P2 上，它读取数据时得到X，而这个X 是“过时”的。3）I/O 传输所造成的数据不一致性。假设

33、 P1 和 P2 的本地缓存C1、C2 中都有某数据X 的拷贝，当 I/O 处理机将一个新的数据 X/写入内存时，就导致了内存和Cache之间的数据不一致性。5.7 分别确定在下列两种计算机系统中，计算表达式所需的时间：s=A1*B1+A2*B2+A4*B4。a)有 4 个处理器的SIMD系统；b)有 4 个处理机的MIMD系统。假设访存取指和取数的时间可以忽略不计；加法与乘法分别需要2 拍和 4 拍；在 SIMD和 MIMD系统中处理器（机）之间每进行一次数据传送的时间为1拍；在 SIMD系统中，PE之间采用线性环形互连拓扑，即每个 PE与其左右两个相邻的PE直接相连，而在MIMD中每个 P

34、E都可以和其它PE有直接的的通路。答：假设4 个 PE 分别为 PE0，PE1，PE2，PE3。利用 SIMD 计算机计算上述表达式，4 个乘法可以同时进行，用时=4 个时间单位；然后进行PE0 到 PE1，PE2 到 PE3 的数据传送，用时=1 个时间单位。在PE1 和 PE3 中形成部分和，用时=2 个时间单位。接着进行PE1 到PE3 的部分和传送，用时=1*2=2 个时间单位。最后，在PE3 中形成最终结果，用时=2 个时间单位。因此，利用SIMD 计算机计算上述表达式总共用时=4（乘法）+1（传送）+2（加法）+2（传送）+2（加法）=11 个时间单位。而利用MIMD计算机计算上述

35、表达式，除了在第二次传送节省1 个时间单位以外，其他与SIMD 相同。因此用时=4（乘法）+1（传送）+2（加法）+1（传送）+2（加法）=10 个时间单位。5.8 假定有一个处理机台数为p 的共享存储器多处理机系统。设 m为典型处理机每条执行执行时间对全局存储器进行访问的平均次数。设 t 为共享存储器的平均存储时间，x 为使用本地存储器的单处理机MIPS速率，再假定在多处理机上执行n 条指令。现在假设 p=32,m=0.4,t=1 s,要让多处理机的有效性能达到56MIPS，需要每台处理机10 的 MIPS效率是多少？A.2 B.4 C.5.83 D.40 答：B 5.9 试在含一个PE的

36、SISD机和在含n个 PE且连接成一线性环的SIMD机上计算下列求内积的表达式：其中n=2kniiiBAs1假设完成每次ADD操作需要2 个单元时间，完成每次MULTIPLY操作需要 4 个单位时间，沿双向环在相邻PE间移数需1 个单位时间(1)SISD 计算机上计算s 需要多少时间(2)SIMD计算机上计算s 需要多少时间(3)SIMD机计算 s 相对于 SISD计算的加速比是多少？答：(1)4n+2(n-1)(2)124nk(3)nknn231245.10 如果一台SIMD计算机和一台流水线处理机具有相同的计算性能，对构成它们的主要部件分别有什么要求？答：一台具有n 个处理单元的SIMD计

37、算机与一台具有一条n 级流水线并且时钟周期为前者1/n 的流水线处理机的计算性能相当，两者均是每个时钟周期产生 n 个计算结果。但是，SIMD计算机需要n 倍的硬件（n 个处理单元），而流水线处理机中流水线部件的时钟速率要求比前者快n 倍，同时还需要存储器的带宽也是前者的n 倍。第六章机群系统6.1 试区分和例示下列关于机群的术语：1）专用机群和非专用机群；2）同构机群和异构机群；3）专用型机群和企业型机群。答：1）根据节点的拥有情况，分为专用机群和非专用机群，在专用机群中所有的资源是共享的，并行应用可以在整个机群上运行，而在非专用机群中，全局应用通过窃取CPU 时间获得运行，非专用机群中由于

38、存在本地用户和远地用户对处理器的竞争，带来了进程迁移和负载平衡问题。2）根据节点的配置分为同构机群和异构机群，同构机群中各节点有相似的的体系，并且使用相同的操作系统，而异构机群中节点可以有不同的体系，运行的操作系统也可以不同。3）专用型机群的特点是紧耦合的、同构的，通过一个前端系统进行集中式管理，常用来代替传统的大型超级计算机系统；而企业型机群是松耦合的，一般由异构节点构成，节点可以有多个属主，机群管理者对节点有有限的管理权。11 6.2 试解释和例示一下有关单一系统映像的术语：1）单一文件层次结构；2）单一控制点；3）单一存储空间；4）单一进程空间；5）单一输入/输出和网络。答：1）用户进入

39、系统后所见的文件系统是一个单一的文件和目录层次结构，该系统透明的将本地磁盘、全局磁盘和其他文件设备结合起来。2）整个机群可以从一个单一的节点对整个机群或某一单一的节点进行管理和控制。3）将机群中分布于各个节点的本地存储器实现为一个大的、集中式的存储器。4）所有的用户进程，不管它们驻留在哪个节点上，都属于一个单一的进程空间，并且共享一个统一的进程识别方案。5）单一输入/输出意味着任何节点均可访问多个外设。单一网络是任一节点能访问机群中的任一网络连接。6.3 就 Solaris MC 系统回答下列问题：1）Solaris MC 支持习题6.2 中单一系统映像的哪些特征？不支持哪些特征？2）对那些S

40、olaris MC 支持的特征，解释一下Solaris MC 是如何解决的。答：1）支持单一文件层次结构、单一进程空间、单一网络和单一I/O 空间。不支持单一控制点和单一的存储空间。2）Solaris 使用了一个叫PXFS 的全局文件系统GFS。PXFS 文件系统的主要特点包括：单一系统映像、一致的语义及高性能。PXFS 通过在 VFS/vnode 接口上截取文件访问操作实现单一系统映像，保证了单一文件层次结构。Solaris MC 提供了一个全局进程标示符pid 可定位系统所有进程，一个进程可以迁移到其他节点，但它的宿主节点中总记录有进程的当前位置，它通过在Solaris 核心层上面增加一个

41、全局进程以实现单一进程空间，每个节点有一个节点管理程序，每个本地进程有一个虚拟进程对象vproc，vproc 保留每个父进程和子进程的信息，实现了全局进程的管理。单一网络和I/O 空间通过一致设备命名技术和单一网络技术实现。6.4 举例解释并比较以下有关机群作业管理系统的术语：1）串行作业与并行作业；2）批处理作业与交互式作业；3）机群作业和外来作业；4）专用模式、空间共享模式、时间共享模式；5）独立调度与组调度。答：1）串行作业在单节点上运行，并行作业使用多个节点。2）批处理作业通常需要较多的资源，如大量的内存和较长的CPU 时间，但不需要迅速的反应；交互式作业要求较快的周转时间，其输入输出

42、直接指向终端设备，这些工作一般不需要大量资源，用户期望它们迅速得到执行而不必放入队列中。3）机群作业时通过使用JMS 功能分布实现的用户作业，用户服务器位于任一主机节点，12 资源管理器跨越所有的机群节点。外来作业在JMS 之外生成的，如 NOW 上的一个工作站拥有者启动的外部作业，它不提交给JMS。4）专用模式：任一时候只有一个作业在机群上运行，任一时候也只有一个作业进程分配给一个节点。空间共享模式：多个作业可以在不重叠的节点区域上运行。时间共享模式：在专用模式和空间共享模式下，只有一个用户进程分配给一个节点，但是所有的系统进程或监护程序仍在同一个节点上运行。5）独立调度：各节点OS 进行自

43、己的调度，但这会显著损坏并行作业的性能，因为并行作业的进程间需要交互。组调度：将并行作业的所有进程一起调度。一个进程激活时，所有进程都被激活。6.5 针对 LSF 回答下列问题：1）对 LSF 的四种作业类型各举一个例子；2）举一个例子说明外来作业；3）对一个有1000 个服务器的机群，为什么LSF 负载分配机制优于：1 整个机群只有一个LIM 或者 2 所有 LIM 都是主机？说明原因。答：1）交互式：用户使用lshosts命令就可以列出每个服务器节点的静态资源，实现交互。批处理：lsbatch 实用程序允许通过LSF 提交、监控和执行批处理作业。串行：用户一旦进入lstcsh shell，

44、发送的每条命令自动在最适合的节点上执行。并行：lsmake 实用程序是UNIX make 实用程序时一个并行版本，允许在多个节点同时处理一个Makefile。2）不通过 LSF 执行的称为外来作业。例如执行一些本地作业：字处理，web 网络浏览等。3）机群的服务器数目太多，如果只采用一个LIM 会导致 LIM 的负责过重，不能及时的处理响应所有服务器的请求和分派所有机群作业；如果采用2 会导致 LIM 之间相互交换负载信息过多，导致网络通信量过大。6.6 为什么在分布式文件系统中，UNIX 语义难以实现？有哪些放松的文件共享语义？采用放松的文件共享语义会有一些什么缺点？答：在 UNIX 语义中

45、，一个修改过的块应该立刻被所有其他应用程序见到。然而分布式的文件系统中，多个节点可能存放了同一文件块的拷贝，当其中一个节点修改文件可的拷贝时，其他节点不能立刻就知道，这就使得UNIX 语义难以实现。放松的文件共享语义有：对话语义、类事物语义、不可改变的共享文件语义等。采用放松的文件共享语义要求应用程序员修改程序代码，以适用这种新的语义，这就增加了程序员的负担。6.7 试解释在机群并行文件系统中，为什么采用软件RAID、高速缓存机制和预取能够提高文件系统性能。答：软件 RAID 是文件系统负责分布数据和维护容错级别，能够和RAID5 有一样的性能，实现机群磁盘间的数据分布，提高了 I/O 系统的

46、传输带宽。高速缓存是将应用程序要取的块放在CACHE 中，根据局部性原理，应用程序可以基本上从CACHE 中读取数据块，而不要通过读取内存或硬盘，提高了读取速度。预取是在真正读取数据块之前就将这些数据块读入内存，这也提高了I/O 性能，改善了文件系统性能。6.8 讨论并行文件系统协作化高速缓存的基本技术前提是什么？这个前提有什么意义？答：13 基本技术前提是互联网络的速度很快，一个节点需要的文件块在其他节点的缓存中，那么就不需要从磁盘读，而是直接从其他节点的缓存中读出。这个前提的意义是可以提高系统的性能，使得节点间的协作化缓存变得更有意义。6.9 回答以下关于Berkeley NOW 项目的问

47、题：1）Berkeley NOW 项目支持单一系统映像的哪几个方面？即单入口点、单文件层次结构、单控制点、单存储空间、单进程空间哪个的哪几项？并解释如何支持。2）解释 Berkeley NOW 项目用来提高性能的四个结构特征。3）解释 Berkeley NOW 项目和 SP机群四个体系结构的差异，并讨论各自的优点。答：1）通过用户级整个机群软件GLUNIX，提供单一系统映像。开发了一种新的无服务器网络文件系统xFS，以支持单一文件层次结构。2）主动消息通信协议，支持有效的通信；机群软件GLUNIX提供单一的系统映像、资源管理和可用性；xFS 支持可扩放性和单一文件层次结构的高可用性；软件框架W

48、ebOS 构筑高可用性、渐增可扩放性。3）SP机群的体系结构特征：每个节点都是RS/600 工作站，并有自己的局部磁盘；每个节点内驻留一个完整的AIX；各节点通过其I/O 总线连接到专门设计的多级高速网络；尽量使用标准工作站部件。这样的优点是简单性和灵活性。6.10 考虑 xFS，并回答下列问题：1）解释 xFS 和集中式文件服务器的两个不同点，并讨论各自的优点；2）解释 xFS 用来提高可用性的主要技术；3）解释 xFS 用来减轻小写问题的主要技术。答：1）无服务器文件系统xFS 将文件服务的功能分布到机器的所有节点上，xFS 中所有的服务器和客户的功能由分散的所有节点实现之。这与集中文件服

49、务器的中央存储、中央缓存、中央管理不同。xFS 的优点是采用分布式管理和协同文件缓存以及冗余磁盘阵列，这提高了系统的可用性以及I/O 的性能和吞吐量。集中式文件服务器会减少缓存的不一致性，管理简单。2）xFS 提高可用性的主要技术是采用廉价冗余磁盘阵列RAID。无工作站文件系统能用来生成软件RAID，以提高性能和高可用性。现在xFS 使用单奇偶校验磁盘条。一个文件数据块在多个存储服务器节点上按条划分，在另一个节点上有奇偶校验块。如果一个节点失效，失效磁盘的内容，可利用其余盘和奇偶盘之异或操作重建之。3）xFS 使用日志条的方法解决小写问题：每个用户首先将写接合到各用户的日志上；然后此日志采用日

50、志段提交给磁盘，每个段系由K-1 个日志片组成，它与奇偶校验片以道送给 K 个存储服务器。第七章分布式共享存储系统7.1 什么是分布式共享存储系统，它相对于共享存储系统与分布式系统有哪些优点？答：分布式共享存储系统，是把共享存储器分成许多模块并分布于各处理机之中。分布式系统中采用消息传递通信，性能提高了，但多地址空间不利于程序员编程。共享存储系统支持传统的单地址空间，但共享必然引起冲突，形成瓶颈，于是分布式共享存储系统结合两者的优点。7.2 释放一致性模型(RC)把处理器一致性(PC)和弱一致性模型(WC)的优点结合在一起了。14 试回答下面有关这些一致性模型的问题：a)比较这三种一致性模型的