基本通信操作

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

2、为：8.16）。试证明在p个叶节点ts mtw th log p 1 log p提示：信包穿越l1个开关节点所需要的时间为ts mtw thl。1图8.16 8 个处理器的树上一到多播送过程Ski 04、给定p个数n0,n1,册1。所谓求前缀和(Pre巾xSum就是计算。其中0 k p 18个处理器的超立方上前缀和。算法8.3给出了超立方上的求前缀和的方法。试按此算法，计算算法8.3 d维超立方上前缀和算法输入：p个数开始存在p个处理器中knii 0, 0 k p 1Sk输出：第k个处理器存有前缀和Begin(1)result = my_number(2)msg = resultfor i =

3、 0 to d - 1 do(3.(1) Partner = my_id 2(3.(2) nd msg to Partner(3.(3) ceive number from Partner(3.(4) g = msg + number(3.(5) if ( Partner my_id ) then result =result + number endifend forEnd5、一到多个人通信又称之为 单点散播(Single-Node Scatter ),它与一到多播送不同之处是，此时源 处理器有p个信包，每一个去向一个目的地(见图 8.14 (c)。图8.17示出了 8个处理器上的超立方 单

4、点散射的过程。试证明：使用 SF和CT方式在超立方上施行一到多个人通信的通信时间为：one to allperstslog p mtw p 1(h) Initial dislnbuticn 01 ni辐区aggf bi D ist ribut ion before th早 second skp(c) Distribution before the third step图8.17 8个处理器的超立方上单点散射过程6、多到多个人通信又称之为全交换( Total Exchange),每个处理器发送各自彼此不同的大小为m的信包给其余处理器(见图 8.14 (d)。图8.18示出了 6个处理器的环上全交

5、换的过程，其中， x, y表 示源处理器，目的处理器, (xi,y,x2,y2,，xn,yn)表示传输过程中的信包流，每个处理器只接收属于它的信包。试证明：利用 SF方式，在环上施行全交换的通信时间为：ttotal -exchange，1、，、(t - mtw p)( p 1)提示：第i步传送的信包大小为 m(p i)卜I i !i-feai I ! B4“ ；ZJi1Q!l j I5J;.： 心 氏4 E=Hh-I!V j ji (4tlJ!叫j _i ；Ofk”if 1.2: .RrSHici - i -( i rirfaifli-a-i SiaTpr dri i id*，irrtirira iii HiJ!翌Lgdlnu#也知44,1舟， .M：i：.；-L/ l 23图8.18 6 个处理器的环上全交换过程7、在p个处理器所谓循环q-移位系指处理器i发送包给处理器（i q）modP 。图8.19示出了按行主编号的Vp p 4 4环绕网孔上施行 5-移位的过程：首先按行同时循环移位（qm0dd;。次；然后作q/dp 1次列补偿移位（如图 8.19