发布时间 : 星期一 文章并行计算（陈国良版）课后答案更新完毕开始阅读c1c43b3243323968011c9233
第三章 互连网络
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.3 四元胖树如图3.47所示，试问：每个内节点有几个子节点和几个父节点？你知道那个机器使用了此种形式的胖树？
答：每个内节点有4个子节点，2个父节点。CM-5使用了此类胖树结构。
3.4 试构造一个N=64的立方环网络，并将其直径和节点度与N=64的超立方比较之，你的结论是什么？
答：A N=64的立方环网络,为4立方环（将4维超立方每个顶点以4面体替代得到），直径d=9，节点度n=4
B N=64的超立方网络，为六维超立方（将一个立方体分为8个小立方，以每个小立方作为简单立方体的节点，互联成6维超立方），直径d=6，节点度n=6
3.5 一个N=2^k个节点的 de Bruijin 网络如图3.48所示，令ak?1ak?2ak?3。。。a1a0，是一个节点的二进制表示，则该节点可达如下两个节点：ak?2ak?3。。。a1a00，ak?2ak?3。。。a1a01。试问：该网络的直径和对剖宽度是多少？
答：N=2^k个节点的 de Bruijin网络 直径d=k 对剖宽带w=2^(k-1)
3.6 一个N=2^n个节点的洗牌交换网络如图3.49所示。试问：此网络节点度==？网络直径==？网络对剖宽度==？
答：N=2^n个节点的洗牌交换网络，网络节点度为=2 ，网络直径=n-1 ，网络对剖宽度=4
3.7 一个N=（k+1）2^k个节点的蝶形网络如图3.50所示。试问：此网络节点度=？网络直径=？网络对剖宽度=？
答：N=（k+1）2^k个节点的蝶形网络，网络节点度=4 ，网络直径=2*k ，网络对剖宽度=2^k
3.9 对于如下列举的网络技术，用体系结构描述，速率范围，电缆长度等填充下表中的各项。（提示：根据讨论的时间年限，每项可能是一个范围） 答： 网络技术 1 网络结构 带宽 铜线距离 光纤距离 Myrinet HiPPI SCI 光纤通信 ATM FDDI 专用机群互联网络 用于异构计算机和其外设的组网 可扩展一致性接口，通常独立于拓扑结构 200MB/秒 800Mbps~1.6Gbps 250Mbps~8Gbps 25m 25m 50m 100m 500m 300m~10km 10km 2KM 多处理器和其外围设备之间，100Mbps~800Mbps 直连结构 主要应用于因特网主干线中 采用双向光纤令牌环，所有结点联接在该环中 25Mbps~10Gbps 100-200Mbps
3.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 在二维网孔中，试构造一个与X-Y选路等价的查表路由。 答： 所构造路由表描述如下：
1）每个节点包括两张路由表x表和y表
2）每个节点包含其以后节点信息，如节点【1，2】x表内容为:【2，2】【3，2】y表内容为：【1，3】 选路方法：
节点路由时进行查表：先查x表即进行x方向路由，如果查表能指明下一跳方向则直接进入下一跳。如果不能则继续查y表，直到到达目的地。
第四章 对称多处理机系统 4.1参照图4.20，试解释为什么采用WT策略进程从P2迁移到P1时，或采用WB策略将包含共享变量X的进程从P1迁移到P2时，会造成高速缓存的不一致。
处理器P1P2P1P2P1P2高速缓存XXX'X'X总线共享存储器XX'X迁移之前写通过写回
图4.20 进程迁移所造成的不一致性
2
答：采用WT策略进程从P2迁移到P1后，P2写共享变量X为X’，并且更新主存数据为X’，此时P1共享变量值仍然为X，与P2和主存X’不一致。采用WB策略进程从P1迁移到P2后，
P1写共享变量X为X’，但此时P2缓存与主存变量值仍然为X，造车不一致。
4.2参照图4.21所示，试解释为什么：①在采用WT策略的高速缓存中，当I/O处理器将一个新的数据X'写回主存时会造成高速缓存和主存间的不一致；②在采用WB策略的高速缓存中，当直接从主存输出数据时会造成不一致。
处理器P1P2P1P2P1P2高速缓存总线I/O处理机XXXXX'XX存储器I/OX'X'XX存储器(输入)（写直达）存储器(输出)（写回）
图4.21 绕过高速缓存的I/O操作所造成的不一致性
答：①中I/O处理器将数据X’写回主存，因为高速缓存采用WT策略，此时P1和P2相应的高速缓存值还是X，所以造成高速缓存与主存不一致。②直接从主存输出数据X，因为高速缓存采用WB策略，可能高速缓存中的数据已经被修改过，所以造成不一致。
4.3 试解释采用WB策略的写更新和写无效协议的一致性维护过程。其中X为更新前高速
缓存中的拷贝，X为修改后的高速缓存块，I为无效的高速缓存块。
x侦听总线高速缓存行共享存储器II'xP1xP2…处理器x高速缓存拷贝x’PnP1IP2…IPnx’P1x’P2…x’Pn（a）写操作前（b）处理器P1执行写无效操作后（c）处理器P1执行写更新操作后答：处理器P1写共享变量X为X’，写更新协议如图(c)所示，同时更新其他核中存在高速缓存拷贝的值为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代表读/写，数字代表发出该操作的处理器。假设所有高速缓存在开始时是空的，并且使用下面的性能模型：读/写高
3
速缓存命中，代价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共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协议时间更少。综上可知，如果同一块在写操作之后频繁被多个核读操作采用Dragon协议更好一些，因为Dragon协议写操作后会更新其它核副本。如果一个同多次连续对同一块进行写操作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 参照4.6.1中讨论多级高速缓存包含性的术语，假设L1和L2都是2-路组相联，n2>n1，
b1=b2，且替换策略用FIFO来代替LRU，试问包含性是否还是自然满足？如果替换策略是随机替换呢？
答：如果采用FIFO替换策略包含性自然满足，因为L1和L2都是2路组相联，FIFO保证了L1与L2在发生替换时会换出相同的缓存块，维护了包含性。如果采取随机替换策略，存在L1与L2替换不是相同块的情况，故不满足包含性。
4.7 针对以下高速缓存情况，试给出一个使得高速缓存的包含性不满足的内存存取序列？
L1 高速缓存容量32字节，2-路组相联，每个高速缓存块8个字节，使用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中关于分事务总线的讨论中，依赖于处理器与高速缓存的接口，下面情况有可能
4
发生：一个使无效请求紧跟在数据响应之后，使得处理器还没有真正存取这个高速缓存