基本通信操作.doc

《基本通信操作.doc》由会员分享，可在线阅读，更多相关《基本通信操作.doc（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章 基本通信操作习题例题：1、对于一个的网孔（处理器按行主方式依次编号为0，1，2，3，4，5，6，7），如何将其嵌入3维超立方中？提示：将的网孔使用Gray码按行主对其进行编号。2、如图8.15所示，信包中的片0，1，2，3要分别去向目的地A，B，C，D。此时片0占据信道CB，片1占据信道DC，片2占据信道BA。试问：这将会产生什么现象？如果采用X-Y选路策略，可避免上述现象吗？为什么？ 图8.15 虫蚀选路网络中所出现的现象3、假定在二叉树中，叶结点为处理器节点，内结点为开关节点（参照图8.16）。试证明在p个叶节点的二叉树中，进行m个字的一到多传播的通信时间为：提示：信包穿越个开关节

2、点所需要的时间为。 图8.16 8个处理器的树上一到多播送过程4、给定p个数。所谓求前缀和（Prefix Sum）就是计算。其中。算法8.3给出了超立方上的求前缀和的方法。试按此算法，计算8个处理器的超立方上前缀和。算法8.3d维超立方上前缀和算法输入：p个数开始存在p个处理器中输出：第k个处理器存有前缀和，Begin(1)result = my_number(2)msg = resultfor i = 0 to d - 1 do(3.1) Partner = my_id(3.2)Send msg to Partner(3.3)Receive number from Partner(3.4)m

3、sg = msg + number(3.5)if ( Partner my_id ) then result =result + number endifend forEnd5、一到多个人通信又称之为单点散播（Single-Node Scatter），它与一到多播送不同之处是，此时源处理器有p个信包，每一个去向一个目的地（见图8.14（c）。图8.17示出了8个处理器上的超立方单点散射的过程。试证明：使用SF和CT方式在超立方上施行一到多个人通信的通信时间为： 图8.17 8个处理器的超立方上单点散射过程6、多到多个人通信又称之为全交换（Total Exchange），每个处理器发送各自彼此不

4、同的大小为m的信包给其余处理器（见图8.14（d）。图8.18示出了6个处理器的环上全交换的过程，其中，x，y表示源处理器，目的处理器，（x1，y1，x2，y2，xn，yn）表示传输过程中的信包流，每个处理器只接收属于它的信包。试证明：利用SF方式，在环上施行全交换的通信时间为：提示：第i步传送的信包大小为 图8.18 6个处理器的环上全交换过程7、在p个处理器所谓循环q-移位系指处理器i发送包给处理器。图8.19示出了按行主编号的环绕网孔上施行5-移位的过程：首先按行同时循环移位次；然后作次列补偿移位（如图8.19（b）所示）；最后再作一次列移位。试证明：利用SF方式在正方形环绕二维网孔上施行循环q-移位的通信时间为：