文档介绍：并行算法的设计与分析
第8章
选路(路由)算法
数据分布算法
超立方机器上数据分布算法
1. 若干概念
代表结点:拥有共享数据的结点; 随从结点:比代表结点编号大的尚未获得共享数据的结点; 活动结点:已接收到代表结点分布(播送)来的共享数据的结点
2. 算法描述
Data distribution on hypercube machine // n=2d, 处理器编号0~n-1
Begin
for i=1 to d=logn do
for j=0 to n-1 do in parallel
if 结点 j 活动且 j+2d-i ≤n-1 then
(1) 结点 j 将共享数据和代表结点编号传送给结点j+2d- i ;
(2) if 结点j+2d-i 所代表结点的编号与传送来的代表结点编号一致 then
() 令结点j+2d-i活动;
() 结点j+2d-i复制刚才传送给它的数据
End.
时间复杂度:tc(n)=O(logn), tr(n)=logn; t(n)= O(logn)+logn= O(logn)
超立方机器上数据分布算法
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,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