并行算法的设计与分析课件

Title,This is our 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bullet,This is our next 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bullet,*,Y.Xu Copyright USTC,Parallel Algorithms,*,/Ch2,Parallel Algorithms,Chapter,2,Fundamental,Techniques of Parallel Algorithms,2024/11/16,Y.Xu Copyright USTC,Parallel Algorithms Chapte,主要内容,2.1,平衡树方法,2.2,倍增技术,2.3,分治策略,2.4,划分原理,2.5,流水线技术,2024/11/16,Y.Xu Copyright USTC,主要内容2.1 平衡树方法2023/9/22Y.Xu Cop,2.1,平衡树方法,设计思想,树叶结点为输入，中间结点为处理结点，由叶向根或由根向叶逐层并行处理。,示例,求最大值,计算前缀和,2024/11/16,Y.Xu Copyright USTC,2.1 平衡树方法2023/9/22Y.Xu Copyrig,算法,2.1 SIMD-SM,上求最大值算法,Begin,for k=m-1 to 0 do,for j=,2,k,to 2,k+1,-1 par-do,Aj=maxA2j,A2j+1,end for,end for,end,时间分析,t(n)=mO(1)=O(logn),p(n)=n/2,c(n)=O(nlogn),非成本最优,2.1,平衡树方法,2024/11/16,Y.Xu Copyright USTC,算法2.1 SIMD-SM上求最大值算法时间分析2.1 平,前缀和,问题定义,n,个元素,x,1,x,2,x,n,，前缀和是,n,个部分和：,S,i,=x,1,*x,2,*x,i,1,in,这里*可以是或,串行算法：,S,i,=S,i,1,*x,i,计算时间为,O(n),并行算法：,p56,算法,2.2 SIMD-SM,上非递归算法,(,高层描述,),p58,算法,2.3 SIMD-SM,上非递归算法,(,底层描述,),令,Ai=x,i,i=1n,Bh,j,和,Ch,j,为辅助数组,(h=0logn,j=1n/2,h,),数组,B,记录由叶到根正向遍历树中各结点的信息,(,求和,),数组,C,记录由根到叶反向遍历树中各结点的信息,(,播送前缀和,),2.1,平衡树方法,2024/11/16,Y.Xu Copyright USTC,前缀和2.1 平衡树方法2023/9/22Y.Xu Copy,p56,算法,2.2 SIMD-SM,上非递归算法,begin,(1)for j=1 to n par-do,/,初始化,B0,j=Aj,end if,(2)for h=1 to logn do,/,正向遍历,for j=1 to n/2,h,par-do,Bh,j=Bh-1,2j-1*Bh-1,2j,end for,end for,时间分析,:,(1)O(1)(2)O(logn)(3)O(logn),=,t(n)=O(logn),p(n)=n,c(n)=O(nlogn),(3)for h=logn to 0 do,/,反向遍历,for j=1 to n/2,h,par-do,(i)if j=even then /,该结点为其父结点的右儿子,Ch,j=Ch+1,j/2,end if,(ii)if j=1 then /,该结点为最左结点,Ch,1=Bh,1,end if,(iii)if j=odd1 then /,该结点为其父结点的左儿子,Ch,j=Ch+1,(j-1)/2*Bh,j,end if,end for,end for,end,2.1,平衡树方法,2024/11/16,Y.Xu Copyright USTC,p56 算法2.2 SIMD-SM上非递归算法 时间分析:,主要内容,2.1 Balanced Trees Method,2.2 Doubling Techniques,2.3 Divide-and-Conquer Strategy,2.4 Partitioning Principle,2.5 Pipelining Techniques,2024/11/16,Y.Xu Copyright USTC,主要内容2.1 Balanced Trees Method2,主要内容,2.1,平衡树方法,2.2,倍增技术,2.3,分治策略,2.4,划分原理,2.5,流水线技术,2024/11/16,Y.Xu Copyright USTC,主要内容2.1 平衡树方法2023/9/22Y.Xu Cop,设计思想,又称指针跳跃,(pointer jumping),技术，特别适合于处理链表或有向树之类的数据结构；,当递归调用时，所要处理数据之间的距离逐步加倍，经过,k,步后即可完成距离为,2,k,的所有数据的计算。,示例,表序问题,求森林的根,2.2,倍增技术,2024/11/16,Y.Xu Copyright USTC,2.2 倍增技术2023/9/22Y.Xu Copyrigh,表序问题：,问题描述,n,个元素的列表,L,，求出每个元素在,L,中的次第号,(,秩或位序或,rank(k),，,rank(k),可视为元素,k,至表尾的距离；,示例：,n=7,(1),pa=b,pb=c,pc=d,pd=e,pe=f,pf=g,pg=g,ra=rb=rc=rd=re=rf=1,rg=0,(2),pa=c,pb=d,pc=e,pd=f,pe=pf=pg=g,ra=rb=rc=rd=re=2,rf=1,rg=0,(3),pa=e,pb=f,pc=pd=pe=pf=pg=g,ra=4,rb=4,rc=4,rd=3,re=2,rf=1,rg=0,注：递归计算位序,r,(4),pa=pb=pc=pd=pe=pf=pg=g,ra=6,rb=5,rc=4,rd=3,re=2,rf=1,rg=0,2.2,倍增技术,2024/11/16,Y.Xu Copyright USTC,表序问题：2.2 倍增技术2023/9/22Y.Xu Cop,表序问题：,算法：,P60,算法,2.4,(1),并行做：初始化,pk,和,distancek /O(1),(2),执行 次,/O(logn),(2.1),对,k,并行地做,/O(1),如果,k,的后继不等于,k,的后继之后继，则,(i)distancek=distancek+distancepk,(ii)pk=ppk,(2.2),对,k,并行地做,rankk=distancek /O(1),运行时间：,t(n)=O(logn)p(n)=n,2.2,倍增技术,2024/11/16,Y.Xu Copyright USTC,表序问题：2.2 倍增技术2023/9/22Y.Xu Cop,求森林的根,问题描述,一组有向树,F,中,如果,是,F,中的一条弧，则,pi=j(,即,j,是,i,的双亲,),；若,i,为根，则,pi=i,。求每个结点,j(j=1n),的树根,sj.,示例,初始时,P1=p2=5 p3=p4=p5=6 P6=p7=8 p8=8,P9=10 p10=11 p11=12 p12=13 p13=13,si=pi,2.2,倍增技术,2024/11/16,Y.Xu Copyright USTC,求森林的根初始时2.2 倍增技术2023/9/22Y.Xu,求森林的根,示例,第一次迭代后 第二次迭代后,算法,：,p61,算法,2.5,运行时间,：,t(n)=O(logn),2.2,倍增技术,2024/11/16,Y.Xu Copyright USTC,求森林的根2.2 倍增技术2023/9/22Y.Xu Cop,主要内容,2.1 Balanced Trees Method,2.2 Doubling Techniques,2.3 Divide-and-Conquer Strategy,2.4 Partitioning Principle,2.5 Pipelining Techniques,2024/11/16,Y.Xu Copyright USTC,主要内容2.1 Balanced Trees Method2,主要内容,2.1,平衡树方法,2.2,倍增技术,2.3,分治策略,2.4,划分原理,2.5,流水线技术,2024/11/16,Y.Xu Copyright USTC,主要内容2.1 平衡树方法2023/9/22Y.Xu Cop,设计思想,将原问题划分成若干个相同的子问题分而治之，若子问题仍然较大，则可以反复递归应用分治策略处理这些子问题，直至子问题易求解。,求解步骤,将输入划分成若干个规模相等的子问题；,同时,(,并行地,),递归求解这些子问题；,并行地归并子问题的解成为原问题的解。,示例,SIMD-SM,模型上的,FFT,递归算法,2.3,分治策略,2024/11/16,Y.Xu Copyright USTC,2.3 分治策略2023/9/22Y.Xu Copyrigh,FFT,递归算法,DFT,离散富里叶变换的定义,给定向量 ，,DFT,将,A,变换为 ，即,写成矩阵形式为,注：串行直接计算,DFT,需要,O(n,2,),2.3,分治策略,2024/11/16,Y.Xu Copyright USTC,FFT递归算法2.3 分治策略2023/9/22Y.Xu C,FFT,递归算法：,将原问题的,DFT,划分为两个规模为,n/2,的子问题的,DFT,SIMD-SM,模型上的算法：,p64,算法,2.7,2.3,分治策略,2024/11/16,Y.Xu Copyright USTC,FFT递归算法：将原问题的DFT划分为两个规模为n/2的子问,主要内容,2.1 Balanced Trees Method,2.2 Doubling Techniques,2.3 Divide-and-Conquer Strategy,2.4 Partitioning Principle,2.5 Pipelining Techniques,2024/11/16,Y.Xu Copyright USTC,主要内容2.1 Balanced Trees Method2,主要内容,2.1,平衡树方法,2.2,倍增技术,2.3,分治策略,2.4,划分原理,2.5,流水线技术,2024/11/16,Y.Xu Copyright USTC,主要内容2.1 平衡树方法2023/9/22Y.Xu Cop,划分原理：,设计思想,将原问题划分成,p,个独立的规模几乎相等的子问题；,p,台处理器并行地求解各子问题。,Remark:,划分重点在于,:,子问题易解,组合成原问题的解方便,;,常见划分方法,均匀划分,方根划分,对数划分,功能划分,2.4,划分原理,2024/11/16,Y.Xu Copyright USTC,划分原理：2.4 划分原理2023/9/22Y.Xu Cop,均匀划分：,方法,:n,个元素,A1.n,分成,p,组，每组,A(i-1)n/p+1.in/p,，,i=1p,示例,:MIMD-SM,模型上的,PSRS,排序,begin,(1),均匀划分：将,n,个元素,A1.n,均匀划分成,p,段，每个,p,i,处理,A(i-1)n/p+1.in/p,(2),局部排序：,p,i,调用串行排序算法对,A(i-1)n/p+1.in/p,排序,(3),选取样本：,p,i,从其有序子序列,A(i-1)n/p+1.in/p,中选取,p,个样本元素,(4),样本排序：用一台处理器对,p,2,个样本元素进行串行排序,(5),选择主元：用一台处理器从排好序的样本序列中选取,