《并行算法的设计与分析(8)》由会员分享，可在线阅读，更多相关《并行算法的设计与分析(8)（3页珍藏版）》请在金锄头文库上搜索。
1、并行算法的设计与分析第8章选路（路由）算法8.4 数据分布算法8.4.1 超立方机器上数据分布算法 1. 若干概念代表结点：拥有共享数据的结点; 随从结点：比代表结点编号大的尚未获得共享 数据的结点; 活动结点：已接收到代表结点分布（播送）来的共享数据的结点 2. 算法描述算法8.5 Data distribution on hypercube machine / n=2d, 处理器编号0n-1Beginfor i=1 to d=logn dofor j=0 to n-1 do in parallelif 结点 j 活动且 j+2d-i n-1 then (1) 结点 j 将共享数据和代表结点
2、编号传送给结点j+2d- i ；(2) if 结点j+2d-i 所代表结点的编号与传送来的代表结点编号一致 then(2.1) 令结点j+2d-i活动； (2.2) 结点j+2d-i复制刚才传送给它的数据End.时间复杂度：tc(n)=O(logn), tr(n)=logn; t(n)= O(logn)+logn= O(logn)8.4.1 超立方机器上数据分布算法3. 示例： n=16, d=4； 结点0,1,11,13是代表结点(活动结点)，它们分别存储有共享数据A,B,C,D 结点2-10是结点1的随从；结点12是结点11的随从；结点14-15是结点13的随从i=1时, j=0,1,11
3、,13为活动结点；满足条件的有：j=1 (B,1)j+2d-1=9 ， 结点9保存接收数据，结点 9 变为活动结点 i=2时, j=0,1,9,11,13为活动结点；满足条件的有： j=1 (B,1)j+2d-2=5 ， 结点5保存接收数据，结点 5 变为活动结点 i=3时, j=0,1,5,9,11,13为活动结点；满足条件的有： j=1 (B,1)j+2d-3=3 ， j=5 (B,1) j+2d-3=7， j=13 (D,13)j+2d-3=15， 结点3,7,15保存接收数据，结点 3, 7, 15 变为活动结点 i=4时, j=0,1,3,5,7,9,11,13,15为活动结点；满足条件的有： j=1 (B,1)j+20=2， j=3 (B,1) j+ 20 =4， j=5 (B,1)j+ 20 =6， j=7 (B,1)j+ 20 =8 ， j=9 (B,1)j+ 20 =10 ， j=11 (C,11)j+ 20 =12 ， j=13 (D,13)j+ 20 =14，结点2,4,6,8,10,12,14保存接收数据，结点 2, 4, 6, 8, 10, 12, 14 变为 活动结点0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15A B C D
