《并行算法的设计与分析(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