基本通信操作

第八章基本通信操作习题例题：1、对于一个42的网孔（处理器按行主方式依次编号为0，1，2，3，4，5，6，7），如何将其嵌入3维超立方中？[提示：将42的网孔使用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个字的一到多传播的通信时间为：pptmttlog1loghws[提示：信包穿越1l个开关节点所需要的时间为ltmtthws。]图8.168个处理器的树上一到多播送过程4、给定p个数110,,,pnnn。所谓求前缀和（PrefixSum）就是计算kiiknS0。其中10pk。算法8.3给出了超立方上的求前缀和的方法。试按此算法，计算8个处理器的超立方上前缀和。算法8.3d维超立方上前缀和算法输入：p个数开始存在p个处理器中输出：第k个处理器存有前缀和kiiknS0，10pkBegin(1)result=my_number(2)msg=resultfori=0tod-1do(3.1)Partner=my_idi2(3.2)SendmsgtoPartner(3.3)ReceivenumberfromPartner(3.4)msg=msg+number(3.5)if(Partnermy_id)thenresult=result+numberendifendforEnd5、一到多个人通信又称之为单点散播（Single-NodeScatter），它与一到多播送不同之处是，此时源处理器有p个信包，每一个去向一个目的地（见图8.14（c））。图8.17示出了8个处理器上的超立方单点散射的过程。试证明：使用SF和CT方式在超立方上施行一到多个人通信的通信时间为：1logwspersalltoonepmtptt图8.178个处理器的超立方上单点散射过程6、多到多个人通信又称之为全交换（TotalExchange），每个处理器发送各自彼此不同的大小为m的信包给其余处理器（见图8.14（d））。图8.18示出了6个处理器的环上全交换的过程，其中，{x，y}表示{源处理器，目的处理器}，（{x1，y1}，{x2，y2}，…，{xn，yn}）表示传输过程中的信包流，每个处理器只接收属于它的信包。试证明：利用SF方式，在环上施行全交换的通信时间为：)1)(21(wexchange-totalppmttt[提示：第i步传送的信包大小为)(ipm]图8.186个处理器的环上全交换过程7、在p个处理器所谓循环q-移位系指处理器i发送包给处理器pqimod)(。图8.19示出了按行主编号的44pp环绕网孔上施行5-移位的过程：首先按行同时循环移位)1mod(pq次；然后作1/pq次列补偿移位（如图8.19（b）所示）；最后再作一次列移位。试证明：利用SF方式在正方形环绕二维网孔上施行循环q-移位的通信时间为：)12/2)((wsshift-circularpmttt