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

习题设计计划1．指导思想要求学生理解高端并行计算机系统设计技术，高端MPP、DSM、CLUSTER等大规模并行计算机的关键设计理论和实现技术，包括互连网络技术、存储架构和高可用技术等。为此，必须用适量的作业、习题，启发学生独立思考以及熟练掌握一些基础知识和基本技能。2．作业安排本教材每一章都附有大量的习题，根据教学进度和学时，合理选择书上习题，以达到进一步加深理解课堂讲授的内容。每一章讲授结束，收一次作业，给出成绩，并作一次集体答疑，讲解作业中的共性问题。作业成绩记入总成绩内。第一章绪论什么是并行计算机答：简单地讲，并行计算机就是由多个处理单元组成的计算机系统，这些处理单元相互通信和协作，能快速高效求解大型的复杂的问题。简述Flynn分类法：答：根据指令流和数据流的多重性将计算机分为：1）单指令单数据流SISD2）单指令多数据流SIMD3）多指令单数据流MISD4）多指令多数据流MIMD简述当代的并行机系统答：当代并行机系统主要有：1）并行向量机（PVP）2）对称多处理机（SMP）3）大规模并行处理机（MPP）4）分布式共享存储（DSM）处理机5）工作站机群（COW）为什么需要并行计算机答：1）加快计算速度2）提高计算精度3）满足快速时效要求4）进行无法替代的模拟计算简述处理器并行度的发展趋势答：1）位级并行2）指令级并行3）线程级并行简述SIMD阵列机的特点答：1）它是使用资源重复的方法来开拓计算问题空间的并行性。2）所有的处理单元（PE）必须是同步的。3）阵列机的研究必须与并行算法紧密结合，这样才能提高效率。4）阵列机是一种专用的计算机，用于处理一些专门的问题。简述多计算机系统的演变答：分为三个阶段：1）1983-1987年为第一代，代表机器有：Ipsc/1、Ameteks/14等。2）1988-1992年为第二代，代表机器有：Paragon、Inteldelta等。3）1993-1997年为第三代，代表机器有：MIT的J-machine。简述并行计算机的访存模型答：1）均匀存储访问模型（UMA）2）非均匀存储访问模型（NUMA）3）全高速缓存存储访问模型（COMA）4）高速缓存一致性非均匀访问模型（CC-NUMA）简述均匀存储访问模型的特点答：1）物理存储器被所有处理器均匀共享。2）所有处理器访问任何存储字的时间相同。3）每台处理器可带私有高速缓存。4）外围设备也可以一定的形式共享。简述非均匀存储访问模型的特点答：1）被共享的存储器在物理上分布在所有的处理器中，其所有的本地存储器的集合构成了全局的地址空间。2）处理器访问存储器的时间不一样。3）每台处理器可带私有高速缓存，外备也可以某种的形式共享。第二章性能评测使用40MHZ主频的标量处理器执行一个典型测试程序，其所执行的指令数及所需的周期数如表所示。试计算执行该程序的有效CPI、MIPS速率及总的CPU执行时间。解：CPI=totalcycles/totalinstructions=（45000*1+32000*2+15000*2+8000*2）/（45000+32000+15000+8000）=MIPS=时钟频率/(CPI*106)=(40*106)/*106)=CPU执行时间=totalcycles/时钟频率=欲在40MHZ主频的标量处理器上执行20万条目标代码指令程序。假定该程序中含有4种主要类型之指令，各指令所占的比例及CPI数如表所示，试计算：①在单处理机上执行该程序的平均CPI。②由①所得结果，计算相应的MIPS速率。解：（1）CPI=1*60%+2*18%+4*12%+8*10%=（2）MIPS=时钟频率/(CPI*106)=(40*106)/*106)=2.1已知SP2并行计算机的通信开销表达式为：t（m）=46+（）m，试计算：21m①渐近带宽r∞=②半峰值信息长度=[提示：to=46μs]解：（1）渐近带宽r∞=1/=S(2)半峰值消息长度m1/2=to*r∞=46us*S=并行机性能评测的意义。答：意义有：1）发挥并行机长处，提高并行机的使用效率。2）减少用户购机盲目性，降低投资风险。3）改进系统结构设计，提高机器的性能。4）促进软/硬件结合，合理功能划分。5）优化“结构-算法-应用”的最佳组合。6）提供客观、公正的评价并行机的标准。如何进行并行机性能评测答：1）机器级性能评测：CPU和存储器的某些基本性能指标；并行和通信开销分析；并行机的可用性与好用性以及机器成本、价格与性/价比。2）算法级性能评测：加速比、效率、扩展性。3）程序级性能评测：Benchmark。简述Gustafson定律的出发点答：1）对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。此时为了提高精度，必须加大计算量，相应地亦必须增多处理器数才能维持时间不变。2）除非学术研究，在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器上，增多处理器必须相应地增大问题规模才有实际意义。已知一程序可并行代码占比例为80%，将其在有10个处理器的系统中运行，求其加速比并求其极限加速比并分析其结构带来的影响解：加速比=1/(20%+80%/10)=1/+=。极限加速比，即处理器个数无穷大的时候呈现的加速比=1/20%=5。这个极限加速比，换个角度说是，Amdahl定律在很长一段时间影响了人们对开发并行计算机的信心，对于本例，因为就算你把处理器做到无穷也只能得到5倍的加速比，同时有一点更明显，就是处理器数目增加到一定程度后，加速比的增长非常缓慢。简述影响加速的因素答：1）求解问题中的串行分量。2）并行处理器所引起的额外开销。3）加大的处理器数超过的算法的并发程度。为什么增加问题规模可以在一定程度提高加速答：1）较大的问题规模可提高较大的并发度。2）额外开销的增加可能慢于有效计算的增加。3）算法中串行分量的比例不是固定不变的。进行可扩放行研究的主要意义答：1）确定解决某类问题用某类并行算法和某类并行体系结构结合，可以有效的利用大量的处理器。2）对于运行于某种体系结构的并行机的某种算法当移到大规模处理机上的性能。3）对于某类固定规模的问题，确定在某类并行机上的最优处理器数目和最大的加速比。4）用于指导改进并行算法和并行体系结构，以使并行算法能尽可能充分利用可扩充的。大量的处理器。第三章互连网络对于一颗K级二叉树（根为0级，叶为k-1级），共有N=2^k-1个节点，当推广至m-元树时（即每个非叶节点有m个子节点）时，试写出总节点数N的表达式。答：推广至M元树时，k级M元树总结点数N的表达式为：N=1+m^1+m^2+...+m^（k-1）=(1-m^k)*1/(1-m);二元胖树如图所示，此时所有非根节点均有2个父节点。如果将图中的每个椭圆均视为单个节点，并且成对节点间的多条边视为一条边，则他实际上就是一个二叉树。试问：如果不管椭圆，只把小方块视为节点，则他从叶到根形成什么样的多级互联网络答：8输入的完全混洗三级互联网络。四元胖树如图所示，试问：每个内节点有几个子节点和几个父节点你知道那个机器使用了此种形式的胖树答：每个内节点有4个子节点，2个父节点。CM-5使用了此类胖树结构。试构造一个N=64的立方环网络，并将其直径和节点度与N=64的超立方比较之，你的结论是什么答：AN=64的立方环网络,为4立方环（将4维超立方每个顶点以4面体替代得到），直径d=9，节点度n=4BN=64的超立方网络，为六维超立方（将一个立方体分为8个小立方，以每个小立方作为简单立方体的节点，互联成6维超立方），直径d=6，节点度n=6一个N=2^k个节点的deBruijin网络如图所示，令ak1ak2ak3。。。a1a0，是一个节点的二进制表示，则该节点可达如下两个节点：ak2ak3。。。a1a00，ak2ak3。。。a1a01。试问：该网络的直径和对剖宽度是多少答：N=2^k个节点的deBruijin网络直径d=k对剖宽带w=2^(k-1)一个N=2^n个节点的洗牌交换网络如图所示。试问：此网络节点度==网络直径==网络对剖宽度==答：N=2^n个节点的洗牌交换网络，网络节点度为=2，网络直径=n-1，网络对剖宽度=4一个N=（k+1）2^k个节点的蝶形网络如图所示。试问：此网络节点度=网络直径=网络对剖宽度=答：N=（k+1）2^k个节点的蝶形网络，网络节点度=4，网络直径=2*k，网络对剖宽度=2^k对于如下列举的网络技术，用体系结构描述，速率范围，电缆长度等填充下表中的各项。（提示：根据讨论的时间年限，每项可能是一个范围）答：网络技术网络结构带宽铜线距离光纤距离Myrinet专用机群互联网络200MB/秒25m500mHiPPI用于异构计算机和其外设的组网800Mbps~25m300m~10kmSCI可扩展一致性接口，通常独立于拓扑结构250Mbps~8Gbps光纤通信多处理器和其外围设备之间，直连结构100Mbps~800Mbps50m10kmATM主要应用于因特网主干线中25Mbps~10GbpsFDDI采用双向光纤令牌环，所有结点联接在该环中100-200Mbps100m2KM如图所示，信包的片0，1，2，3要分别去向目的地A，B，C，D。此时片0占据信道CB，片1占据信道DC，片2占据信道AD，片3占据信道BA。试问：1）这将会发生什么现象2）如果采用X-Y选路策略，可避免上述现象吗为什么答：1）通路中形成环，发生死锁2）如果采用X-Y策略则不会发生死锁。因为采用X-Y策略时其实质是对资源（这里是通道）进行按序分配（永远是x方向优先于y方向，反方向路由是y方向优先于x方向），因此根据死锁避免的原则判断，此时不会发生死锁。在二维网孔中，试构造一个与X-Y选路等价的查表路由。答：所构造路由表描述如下：1）每个节点包括两张路由表x表和y表2）每个节点包含其以后节点信息，如节点【1，2】x表内容为:【2，2】【3，2】y表内容为：【1，3】选路方法：节点路由时进行查表：先查x表即进行x方向路由，如果查表能指明下一跳方向则直接进入下一跳。如果不能则继续查y表，直到到达目的地。第四章对称多处理机系统参照图，试解释为什么采用WT策略进程从2P迁移到1P时，或采用WB策略将包含共享变量X的进程从1P迁移到2P时，会造成高速缓存的不一致。P1X处理器高速缓存共享存储器迁移写通写总线XP2P1X'XX'P2P1XX'XP2过回之前图进程迁移所造成的不一致性答：采用WT策略进程从2P迁移到1P后，2P写共享变量X为X’，并且更新主存数据为X’，此时1P共享变量值仍然为X，与2P和主存X’不一致。采用WB策略进程从1P迁移到2P后，1P写共享变量X为X’，但此时2P缓存与主存变量值仍然为X，造车不一致。参照图所示，试解释为什么：①在采用WT策略的高速缓存中，当I/O处理器将一个新的数据'X写回主存时会造成高速缓存和主存间的不一致；②在采用WB策略的高速缓存中，当直接从主存输出数据时会造成不一致。P1处理器I/O（写直达）总线XXP2P1XXP2P1X'XP2XX'X'XX存储器存储器存储器输入()输出()（写回）高速缓存I/O处理机图绕过高速缓存的I/O操作所造成的不一致性答：①中I/O处理器将数据X’写回主存，因为高速缓存采用WT策略，此时P1和P2相应的高速缓存值还是X，所以造成高速缓存与主存不一致。②直接从主存输出数据X，因为高速缓存采用WB策略，可能高速缓存中的数据已经被修改过，所以造成不一致。4.3试解释采用WB策略的写更新和写无效协议的一致性维护过程。其中X为更新前高速缓存中的拷贝，'X为修改后的高速缓存块，I为无效的高速缓存块。（b）处理器P1执行写无效操作后Ix’I…P1P2PnIx’x’x’（c）处理器P1执行写更新操作后…PnP2P1高速缓存拷贝x高速缓存行共享存储器侦听总线xxx处理器（a）写操作前…P1P2PnI答：处理器P1写共享变量X为X’，写更新协议如图(c)所示，同时更新其他核中存在高速缓存拷贝的值为X’;写无效协议如图