吉林大学研究所课程-并行计算课件-第4章—并行计算的基本设计技术.ppt

实例—求前缀和 实例—求前缀和 算法实现 Begin (1) for j=1 to l=n/p do B(0,l(s-1)+j)- A(l(s-1)+j) end for (2) for h=1 to k do (2.1)if(k-h-q=0) then for j=2k-h-q(s-1)+1 to 2k-h-qs do B(h,j)-B(h-1,2j-1)*B(h-1,2j) end for end if (2.2) if (s=2k-h) then B(h,s)-B(h-1,2s-1)*B(h-1,2s) end if end for 实例—求前缀和 (3) for h=k to 0 do (3.1) if(k-h-q=0) then for j=2k-h-q(s-1)+1 to 2k-h-qs do (1) if(j=even) then C(h,j)-C(h+1,j/2) end if (2) if(j=1) then C(h,1)-B(h,1) end if (3) if j=odd1 then C(h,j)-C(h+1,(j-1)/2)*B(h,j) end if end for (3.2) if s2k-h then (1) if(s=even) then C(h,s)-C(h+1,s/2) end if (2) if(s=1) then C(h,1)-B(h,1) end if (3) if(s=odd1) then C(h,s)-C(h+1,(s-1)/2)*B(h,s) end if end if end for end 实例—求前缀和 实例：n=8,p=2时求前缀和 处理分布情况： p1 p1 p1 p1 p1 p1 p1 p1 p2 p2 p2 p2 p2 p2 p2 实例—求前缀和 以p2情况为例 第一步：p2将设置B(0,5)=A(5),(0,6)=a(6) B(0,7)=A(7),(0,7)=a(7) 第二步：正向遍历时，p2在h=1,2时是活动的，在 h=3是空闲的，p2通过循环B(1,3),B(1,4) 和B(3,2) 第三步：反向遍历时，p2在h=3时是空闲的，而在 h=2时是活动的 因此，p2将产生：C(2,2),C(1,3),C(1,4),C(0,5),C(0,6),C(0,7),C(0,8) 作业 1. 在划分设计技术、分治设计技术、平衡树设计技术、倍增设计技术、破对称设计技术、流水线设计技术中任选2种设计技术、分别求解1个实际问题。要求： ① 自选一个实际问题并对问题本身进行详细描述; ② 给出算法的形式化描述并加以必要的文字说明； ③举例说明算法的求解过程 2. 简述并行计算的3种设计方法； 3. 简述PCAM设计过程； * * DFT计算过程图示 偶下标输出Z(1) 奇下标输出Z(2) Z(1) 计算 DFT + + + - - - x0 x1 Z(2) 计算 DFT 1 w 算法 输入 输出 每个元素的值 X的DFT X为n为向量 算法 Procedure PAR FFT(X,Y) Begin (1) if n=2 then yo?x0+x1;y1?x0-x1 Endif (2) for l=0 to n/2-1 Par_do (2,1) (2,2) Endfor (3) Recursirely Call: (3.1) PAR FFT([ (3.2) PAR FFT([ (4) for j=0 to n-1 par_do (4.1) if j=even then Endif (4.2) if j=odd then