并行计算(陈国良版)课后答案

《并行计算(陈国良版)课后答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章互连网络3.1对于一颗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);3.2二元胖树如图3.46所示，此时所有非根节点均有2个父节点。如果将图中的每个椭圆均视为单个节点，并且成对节点间的多条边视为一条边，则他实际上就是一个二叉树。试问：如果不管椭圆，只把小方块视为节点，则他从叶到根形成什么样的多级互联网络？答：8输入的完全混洗三级互联网络。3.

2、3四元胖树如图3.47所示，试问：每个内节点有几个子节点和几个父节点？你知道那个机器使用了此种形式的胖树？答：每个内节点有4个子节点，2个父节点。CM-5使用了此类胖树结构。3.4试构造一个N=64的立方环网络，并将其直径和节点度与N=64的超立方比较之，你的结论是什么？答：AN=64的立方环网络,为4立方环（将4维超立方每个顶点以4面体替代得到），直径d=9，节点度n=4BN=64的超立方网络，为六维超立方（将一个立方体分为8个小立方，以每个小立方作为简单立方体的节点，互联成6维超立方），直径d=6，节点度n=63.5一个N=2^k个节点的deBruijin网络如图3.

3、48所示，令。。。，是一个节点的二进制表示，则该节点可达如下两个节点：。。。0，。。。1。试问：该网络的直径和对剖宽度是多少？答：N=2^k个节点的deBruijin网络直径d=k对剖宽带w=2^(k-1)3.6一个N=2^n个节点的洗牌交换网络如图3.49所示。试问：此网络节点度==？网络直径==？网络对剖宽度==？答：N=2^n个节点的洗牌交换网络，网络节点度为=2，网络直径=n-1，网络对剖宽度=43.7一个N=（k+1）2^k个节点的蝶形网络如图3.50所示。试问：此网络节点度=？网络直径=？网络对剖宽度=？答：N=（k+1）2^k个节点的蝶形网络，网络节点度=4

4、，网络直径=2*k，网络对剖宽度=2^k3.9对于如下列举的网络技术，用体系结构描述，速率范围，电缆长度等填充下表中的各项。（提示：根据讨论的时间年限，每项可能是一个范围）答：网络技术网络结构带宽铜线距离光纤距离14Myrinet专用机群互联网络200MB/秒25m500mHiPPI用于异构计算机和其外设的组网800Mbps~1.6Gbps25m300m~10kmSCI可扩展一致性接口，通常独立于拓扑结构250Mbps~8Gbps光纤通信多处理器和其外围设备之间，直连结构100Mbps~800Mbps50m10kmATM主要应用于因特网主干线中25Mbps~10GbpsF

5、DDI采用双向光纤令牌环，所有结点联接在该环中100-200Mbps100m2KM3.10如图3.51所示，信包的片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方向），因此根据死锁避免的原则判断，此时不会发生死锁。3.12在二维网孔中

6、，试构造一个与X-Y选路等价的查表路由。答：所构造路由表描述如下：1）每个节点包括两张路由表x表和y表2）每个节点包含其以后节点信息，如节点【1，2】x表内容为:【2，2】【3，2】y表内容为：【1，3】选路方法：节点路由时进行查表：先查x表即进行x方向路由，如果查表能指明下一跳方向则直接进入下一跳。如果不能则继续查y表，直到到达目的地。第四章对称多处理机系统4.1参照图4.20，试解释为什么采用WT策略进程从迁移到时，或采用WB策略将包含共享变量X的进程从迁移到时，会造成高速缓存的不一致。图4.20进程迁移所造成的不一致性14答：采用WT策略进程从迁移到后，写共享变量X

7、为X’，并且更新主存数据为X’，此时共享变量值仍然为X，与和主存X’不一致。采用WB策略进程从迁移到后，写共享变量X为X’，但此时缓存与主存变量值仍然为X，造车不一致。4.2参照图4.21所示，试解释为什么：①在采用WT策略的高速缓存中，当I/O处理器将一个新的数据写回主存时会造成高速缓存和主存间的不一致；②在采用WB策略的高速缓存中，当直接从主存输出数据时会造成不一致。图4.21绕过高速缓存的I/O操作所造成的不一致性答：①中I/O处理器将数据X’写回主存，因为高速缓存采用WT策略，此时P1和P2相应的高速缓存值还是X，所以