第三章 互连网络
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 对于如下列举的网络技术，用体系结构描述，速率范围，电缆长度等填充下表中的各项。（提示：根据讨论的时间年限，每项可能是一个范围） 答： 网络技术 网络结构 带宽 铜线距离 光纤距离 Myrinet HiPPI SCI 光纤通信 ATM FDDI 专用机群互联网络 用于异构计算机和其外设的组网 可扩展一致性接口，通常独立于拓扑结构 200MB/秒 800Mbps~1.6Gbps 250Mbps~8Gbps 25m 25m 50m 100m 500m 300m~10km 10km 2KM 多处理器和其外围设备之间，100Mbps~800直连结构 Mbps 主要应用于因特网主干线中 采用双向光纤令牌环，所有结点联接在该环中 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 进程迁移所造成的不一致性
答：采用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代表读/写，数字代表发出该操作的处理器。假设所有高速缓存在开始时是空的，并且使用下面的性能模型：读/写高速缓存命中，代价1个时钟周期；缺失引起简单的总线事务（如BusUpgr，BusUpd），60
并行计算课后答案
