中国科学技术大学：《并行计算 Parallel Computing》课程教学资源（习题）第八章 基本通信操作

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

第八章 基本通信操作 习题例题： 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。试问： ①这将会产生什么现象？ ②如果采用 X-Y 选路策略，可避免上述现象吗？为什么？ 图 8.15 虫蚀选路网络中所出现的现象 3、假定在二叉树中，叶结点为处理器节点，内结点为开关节点（参照图 8.16）。试证明在 p 个叶节点的二叉树中，进行 m 个字的一到多传播的通信时间为： (t s + mtw + t h (log p +1))log p [提示：信包穿越 l −1 个开关节点所需要的时间为 t mt t l s + w + h 。]

图8168个处理器的树上一到多播送过程 4、给定P个数m,n,…,n21所谓求前缀和( Prefix Sum)就是计算S=∑n其中 0≤k≤p-1。算法83给出了超立方上的求前缀和的方法。试按此算法,计算8个处理器 的超立方上前缀和。 算法8.3d维超立方上前缀和算法 输入:p个数开始存在p个处理器中 输出:第k个处理器存有前缀和S=∑n,0≤k≤p- (2)msg=result for i=0 to d-I do 2 (3. 3)Receive number from Partner (3.4)msg=msg+ number (3.5)if( Partner <my id)then result =result+ number nd for End 5、一到多个人通信又称之为单点散播( Single-Node scatter,它与一到多播送不同之处是, 此时源处理器有p个信包,每一个去向一个目的地(见图814(c)。图817示出了8个处 理器上的超立方单点散射的过程。试证明:使用SF和CT方式在超立方上施行一到多个人 通信的通信时间为: t、ogp

图 8.16 8 个处理器的树上一到多播送过程 4、给定 p 个数 0 1 1 , , , n n  np− 。所谓求前缀和（Prefix Sum）就是计算 = = k i Sk ni 0 。其中 0  k  p −1 。算法 8.3 给出了超立方上的求前缀和的方法。试按此算法，计算 8 个处理器 的超立方上前缀和。 算法 8.3 d 维超立方上前缀和算法 输入：p 个数开始存在 p 个处理器中 输出：第 k 个处理器存有前缀和 = = k i Sk ni 0 ， 0  k  p −1 Begin (1)result = my_number (2)msg = result for i = 0 to d - 1 do (3.1) Partner = my_id i  2 (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 方式在超立方上施行一到多个人 通信的通信时间为： log ( 1) t one−to−all−pers = t s p + mtw p −

(4,5 l2,3 0.1, (a) Initial distribution of messages (b) Distribution before the second step (0,1) (c)Distribution before the third step (d) Final distribution of messages 图8178个处理器的超立方上单点散射过程 6、多到多个人通信又称之为全交换( Total Exchange),每个处理器发送各自彼此不同的大 小为m的信包给其余处理器(见图814(d)。图818示出了6个处理器的环上全交换的过 程,其中,{x,y表示{源处理器,目的处理器},({x1,y},{x2,y},…,{xm,mn})表示 传输过程中的信包流,每个处理器只接收属于它的信包。试证明:利用SF方式,在环上施 行全交换的通信时间为 ttotalkexchange =(t+mt pXp-D) 提示:第i步传送的信包大小为m(Pp-1)]

图 8.17 8 个处理器的超立方上单点散射过程 6、多到多个人通信又称之为全交换（Total Exchange），每个处理器发送各自彼此不同的大 小为 m 的信包给其余处理器（见图 8.14（d））。图 8.18 示出了 6 个处理器的环上全交换的过 程，其中，{x，y}表示{源处理器，目的处理器}，（{x1，y1}，{x2，y2}，…，{xn，yn}）表示 传输过程中的信包流，每个处理器只接收属于它的信包。试证明：利用 SF 方式，在环上施 行全交换的通信时间为： )( 1) 2 1 ( t total-exchange = t + mtw p p − [提示：第 i 步传送的信包大小为 m( p − i) ]

14:0 1451-94329:2 (l2(m:: 1431(54 (51.54 (521…1543) ({.2},{4,3}) ({2,13 (3,2 …5 图8186个处理器的环上全交换过程 7、在p个处理器所谓循环q移位系指处理器i发送包给处理器(i+q)modp。图819示出 了按行主编号的、p×p=4×4环绕网孔上施行5移位的过程:首先按行同时循环移位 (gmdD=1次然后作q/」=1次列补偿移位(如图819(b)所示)最后再作 次列移位。试证明:利用SF方式在正方形环绕二维网孔上施行循环q-移位的通信时间为 2p/2+)

图 8.18 6 个处理器的环上全交换过程 7、在 p 个处理器所谓循环 q-移位系指处理器 i 发送包给处理器 (i + q)mod p 。图 8.19 示出 了按行主编号的 p  p = 4 4 环绕网孔上施行 5-移位的过程：首先按行同时循环移位 (qmod p =1) 次；然后作 q / p =1 次列补偿移位（如图 8.19（b）所示）；最后再作一 次列移位。试证明：利用 SF 方式在正方形环绕二维网孔上施行循环 q-移位的通信时间为： ( )(2 / 2 1) t circular-shift = t s + mtw p +