并行算法的设计技术

1、第四章第四章 并行算法的设计技术并行算法的设计技术 划分(Partitioning)分解成小的任务，开拓并发性 通讯(Communication)确定诸任务间的数据交换，监测划分的合理性； 组合(Agglomeration)依据任务的局部性，组合成更大的任务 映射(Mapping)将每个任务分配到处理器上，提高算法的性能并行算法的设计技术并行算法的设计技术 平衡树方法 倍增技术 分治策略 流水线技术平衡树技术平衡树技术平衡树设计思想 以树的叶结点为输入，中间结点为处理结点，由叶向根或由根向叶逐层进行并行处理。 A1An/4An/2-1An/2An/2+1An-2An-1AnAn+1An+2An

2、+3A2n-4A2n-3A2n-2A2n-1K=m-1K=m-2K=0P1P1P2Pn/2-1Pn/2P1Pn/2-1应用应用-N个数求和个数求和输入：数组A(1:N)，N=2K输出：数组值的总和存储于A(1)中begin p=n/2 while p0 do for i=1 to p do in parallel A(i)=A(2i-1)+A(2i) end parallel p=p/2 end whileend应用应用-计算前缀和计算前缀和82022-6-27 计算前缀和计算前缀和SIMD-TC模型上非递归求前缀和算法模型上非递归求前缀和算法输入：n=2k的数组A，k为非负整数输出：数组C，

3、其中C(0,j)是第j个前缀和begin (1) for j=1 to n par-do B(0,j)-A(j) end for (2) for h=1 to log n do for j=1 to n/2h par-do B(h,j)- B(h-1,2j-1)* B(h-1,2j) end for endfor SIMD-TC模型上非递归求前缀和算法模型上非递归求前缀和算法 (3) for h=log n to 0 do for j=1 to n/2h par-do (i) if j=even then C(i,j)-C(h+1,j/2) end if (ii) if j=1 then C(

4、h,1)1 then C(H,j)-C(h+1,(j- 1)/2) *B(h,j) end for end for end for end122022-6-27 倍增设计技术倍增设计技术k132022-6-27 表序问题表序问题输入：N个元素的表列L输出：rank(k)Begin:(1) for all kl par_do (1.1) p(k)next(k) (1.2) if p(k)k then distance(k) 1 else distance(k) 0 end if end for(2) repeatlog ntimes (2.1)for all kl par_do If p(k)p

5、(p(k) then ()distance(k) distance(k)+distance(p(k) ()p(k) p(p(k) end if end for (2.2) for all kl par_do rank(k) distance(k) end for end repeatendA0 An/p-1 An/p A2n/p-1 A2n/p A(p-1)n/p An-1+局部和局部和总和总和 2路分治法路分治法int add(int s ) if(number(s)=2) return (n1+n2); else Divide(s, s1,s2); Part_sum1=add(s1); P

6、art_sum2=add(s2); Return (Part_sum1+ Part_sum2); Int add(int *s) if (number(s)=4) return(n1+n2+n3+n4); else divide (s,s1,s2,s3,s4); part_sum1=add(s1); part_sum2=add(s2); part_sum3=add(s3); part_sum4=add(s4); return(part_sum1+ part_sum2+ part_sum3+ part_sum1) 矩形面积= d * f ( p + d / 2 )xf(x)a p d q b梯形

7、面积= d * ( f ( p ) + f ( q ) ) / 2 )xf(x)a p d q b1 40 1+x21 + ( ) 4 i + 0.5 2 n0in1n = dx d (f(a)+f(a+d)2d (f(a+d d)+f(a+2d)2d (f(a+(n-1)d)+f(b)2面积= + += d + f(a+d) + f(a+2d) + f(a+(n-1)d) + f(b)2f(a)2 算法只需做少量修改：part_sum = 0.5 *(f(start)+f(end);for (x = start + d; xend; x = x + d) /calcs partial sum

8、s part_sum += f(x);part_sum = d * part_sum;算法描述算法描述在SPMD 模式中：If (I=master) printf(“Enter number of intervals”); scanf(“%d”,&n);Bcast(&n,pgroup); region=(b-a)/p; start=a+region*I; end=start+region; 算法描述算法描述 d=(b-a)/n; area=0.0; for (x=start;xend;x=x+d) area=area+0.5*(f(x)+f(x+d)*d; reduce_add(&integr

9、al,&area, pgroup);- for(x=start;xend;x=x+d) area=area+f(x)+f(x+d); area=0.5*area*d;a4a3a2 a4 a3 a2 a1 a1 a4 a3 a2 a4 a3P 0P 1P 2P 3P 4 a4 流水线技术流水线技术并行算法aSin SoutaSin Souta1aSin Souta2aSin Souta3a0sum每个处理机（流水线中的中间级）需要执行相同的操作：recv (sum,Pi-1);sum = sum + a;send (sum, Pi+1);主机Processors线性结构的线性结构的多处理机系统多处理机系统线性结构和环形结构可以完美地嵌入到网格和超线性结构和环形结构可以完美地嵌入到网格和超立方体结构之上。这就使得网格和超立方体成为立方体结构之上。这就使得网格和超立方体成为合适的平台。合适的平台。可将结果返回给主进程的双向流水线机器结构:未排序未排序的数列的数列P0P1Pp-1主进程主进程从进程从进程未排序未排序的数列的数列P0P1Pp-1主进程主进程从进程从进程已排序已排序的数列的数列P0P1P2P3P4流水线时间流水线时间将要被排序的数列：5, 2, 1, 3, 41542354132542315531245423152