并行计算课后答案

《并行计算课后答案》由会员分享，可在线阅读，更多相关《并行计算课后答案（20页珍藏版）》请在文档大全上搜索。

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

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

3、3 。 a1a0 ，是一个节点的二进制表示，则该节点可达如下两个节点：ak 2 ak 3 。 a1 a00， ak 2 ak 3。 a1 a0 1。试问：该网络的直径和对剖宽度是多少答： N=2k 个节点的 de Bruijin网络直径 d=k 对剖宽带w=2(k-1)一个 N=2n 个节点的洗牌交换网络如图所示。宽度 =答： N=2n 个节点的洗牌交换网络，网络节点度为试问：此网络节点度 =网络直径 =网络对剖=2，网络直径 =n-1，网络对剖宽度=4一个 N=（ k+1） 2k 个节点的蝶形网络如图所示。试问：此网络节点度剖宽度 =答：N=（k+1）2k 个节点的蝶形网络，网络节点度 =4

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

5、结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 方向），因此根据死锁避免的原则判断，此时不会发生死锁。在二维网孔中，试构造一个

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

7、;X总线共享X'XX存储器迁移 之前写通 过写回图 进程迁移所造成的不一致性答：采用 WT策略进程从 P2迁移到 P1 后， P2写共享变量 X 为 X，并且更新主存数据为 X，此时 P1 共享变量值仍然为X，与 P2和主存 X不一致。采用WB策略进程从 P1 迁移到 P2 后，P1 写共享变量 X 为 X，但此时 P2 缓存与主存变量值仍然为X，造车不一致。参照图所示，试解释为什么：在采用WT策略的高速缓存中，当I/O 处理器将一个新的数据 X ' 写回主存时会造成高速缓存和主存间的不一致； 在采用 WB策略的高速缓存中， 当直接从主存输出数据时会造成不一致。处理器P1P2P

8、1P2P1P2高速缓存XXXXX'X总线I/O处理机XX'X'XX存储器I/O存储器( 输入)存储器( 输出 )（写直达）（写回）图 绕过高速缓存的I/O 操作所造成的不一致性答：中I/O 处理器将数据X写回主存，因为高速缓存采用WT策略，此时P1 和 P2 相应的高速缓存值还是X，所以造成高速缓存与主存不一致。直接从主存输出数据X，因为高速缓存采用WB策略，可能高速缓存中的数据已经被修改过，所以造成不一致。4.3 试解释采用WB策略的写更新和写无效协议的一致性维护过程。其中X 为更新前高速缓存中的拷贝，X ' 为修改后的高速缓存块，I 为无效的高速缓存块。x高

9、速缓存行共享存储器II侦听总线xxx 高速缓存拷贝xIIxxxP1P2处理器PnP1P2PnP1P2Pn（a）写操作前（b）处理器P1执行写无效操作后（c）处理器P1执行写更新操作后答：处理器P1 写共享变量X 为 X，写更新协议如图(c) 所示，同时更新其他核中存在高速缓存拷贝的值为X; 写无效协议如图(b) 所示，无效其他核中存在高速缓存拷贝，从而维护了一致性过程。4.4 两种基于总线的共享内存多处理机分别实现了Illinois MESI协议和 Dragon 协议，对于下面给定的每个内存存取序列，试比较在这两种多处理机上的执行代价，并就序列及一致性协议的特点来说明为什么有这样的性能差别。序

10、列r1 w1 r1 w1 r2 w2 r2 w2 r3w3 r3 w3 ；序列 r1 r2 r3 w1 w2 w3 r1 r2 r3 w3 w1；序列 r1 r2 r3 r3 w1 w1 w1w1 w2 w3；所有的存取操作都针对同一个内存位置，r/w 代表读 / 写，数字代表发出该操作的处理器。假设所有高速缓存在开始时是空的，并且使用下面的性能模型：读/ 写高速缓存命中，代价1 个时钟周期；缺失引起简单的总线事务（如BusUpgr，BusUpd）， 60个时钟周期； 缺失引起整个高速缓存块传输，90 时钟周期。 假设所有高速缓存是写回式。答：读写命中、总线事务、块传输分别简记为H、B、 T。

11、 MESI协议： BTH H H H BTH BH HH 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共 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时钟周期 BT