基本通信操作.docx

第八章 基本通信操作
习题例题：
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个字的一到多传播的通信时间为：

[提示：信包穿越个开关节点所需要的时间为。]

图8.16 8个处理器的树上一到多播送过程
4、给定p个数。所谓求前缀和（Prefix Sum）就是计算。其中。算法8.3给出了超立方上的求前缀和的方法。试按此算法，计算8个处理器的超立方上前缀和。
算法8.3 d维超立方上前缀和算法
输入：p个数开始存在p个处理器中
输出：第k个处理器存有前缀和，
Begin
(1)result = my_number
(2)msg = result
for 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)msg = msg + number
(3.5)if ( Partner < my_id ) then result =result + number
endif
end for
End
5、一到多个人通信又称之为单点散播（Single-Node Scatter），它与一到多播送不同之处是，此时源处理器有p个信包，每一个去向一个目的地（见图8.14（c））。图8.17示出了8个处理器上的超立方单点散射的过程。试证明：使用SF和CT方式在超立方上施行一到多个人通信的通信时间为：

图8.17 8个处理器的超立方上单点散射过程
6、多到多个人通信又称之为全交换（Total Exchange），每个处理器发送各自彼此不同的大小为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-移位的通信时间为：