并行计算课件

并行计算,第一级,第二级,第三级,第一级,第二级,第三级,现代密码学理论与实践之五,*,*,并 行 计 算,中国科学技术大学计算机科学与技术系,国家高性能计算中心,(,合肥,),2004,年,12,月,2024/10/1,1,现代密码学理论与实践之五,并 行 计 算 中国科学技术大学计算机科学与技术系2022,第二篇 并行算法的设计,第四章 并行算法的设计基础,第五章 并行算法的一般设计方法,第六章,并行算法的基本设计技术,第七章 并行算法的一般设计过程,2024/10/1,2,现代密码学理论与实践之五,第二篇 并行算法的设计 第四章 并行算法的设计基础,第六章 并行算法的基本设计技术,6.1,划分设计技术,6.2,分治设计技术,6.3,平衡树设计技术,6.4,倍增设计技术,6.5,流水线设计技术,2024/10/1,3,现代密码学理论与实践之五,第六章 并行算法的基本设计技术 6.1 划分设计技,6.1,划分设计技术,6.1.1,均匀划分技术,6.1.2,方根划分技术,6.1.3,对数划分技术,6.1.4,功能划分技术,2024/10/1,4,现代密码学理论与实践之五,6.1 划分设计技术 6.1.1 均匀划分技术,均匀划分技术,划分方法,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),选择主元：用一台处理器从排好序的样本序列中选取,p-1,个主元，并,播送给其他,p,i,(6),主元划分：,p,i,按主元将有序段,A(i-1)n/p+1.in/p,划分成,p,段,(7),全局交换：各处理器将其有序段按段号交换到对应的处理器中,(8),归并排序：各处理器对接收到的元素进行归并排序,end.,2024/10/1,5,现代密码学理论与实践之五,均匀划分技术划分方法2022/10/105现代密码学理论与,均匀划分技术,例,6.1 PSRS,排序过程。,N=27,，,p=3,，,PSRS,排序如下,：,2024/10/1,6,现代密码学理论与实践之五,均匀划分技术例6.1 PSRS排序过程。N=27，p=3，,6.1,划分设计技术,6.1.1,均匀划分技术,6.1.2,方根划分技术,6.1.3,对数划分技术,6.1.4,功能划分技术,2024/10/1,7,现代密码学理论与实践之五,6.1 划分设计技术 6.1.1 均匀划分技术,方根划分技术,划分方法,n,个元素,A1.n,分成,A(i-1)n(1/2)+1.in(1/2),，,i=1n(1/2),示例：,SIMD-CREW,模型上的,Valiant,归并,(1975,年发表,),/,有序组,A1.p,、,B1.q,(,假设,plogm=log4=2,=j1=rank(b,logm,:A)=rank(b,2,:A)=rank(9:A)=3,j2=8,B,0,:3,9 B,1,:16,21,A,0,:4,6,7 A,1,:10,12,15,18,20,A,和,B,归并,化为,(,A,0,B,0,),和,(,A,1,B,1,),的归并,2024/10/1,12,现代密码学理论与实践之五,对数划分技术划分方法2022/10/1012现代密码学理论,6.1,划分设计技术,6.1.1,均匀划分技术,6.1.2,方根划分技术,6.1.3,对数划分技术,6.1.4,功能划分技术,2024/10/1,13,现代密码学理论与实践之五,6.1 划分设计技术 6.1.1 均匀划分技术,功能划分技术,划分方法,n,个元素,A1.n,分成等长的,p,组，每组满足某种特性。,示例：,(m,n),选择问题,(,求出,n,个元素中前,m,个最小者,),功能划分：要求每组元素个数必须大于,m,；,算法：,p148,算法,6.4,输入：,A=(a1,an);,输出：前,m,个最小者；,Begin,(1),功能划分：将,A,划分成,g=n/m,组，每组含,m,个元素；,(2),局部排序：使用,Batcher,排序网络将各组并行进行排序；,(3),两两比较：将所排序的各组两两进行比较，从而形成,MIN,序列；,(4),排序,-,比较：对各个,MIN,序列，重复执行第,(2),和第,(3),步，直至,选出,m,个最小者。,End,2024/10/1,14,现代密码学理论与实践之五,功能划分技术划分方法2022/10/1014现代密码学理论,功能划分技术,2024/10/1,15,现代密码学理论与实践之五,功能划分技术2022/10/1015现代密码学理论与实践之,第六章 并行算法的基本设计技术,6.1,划分设计技术,6.2,分治设计技术,6.3,平衡树设计技术,6.4,倍增设计技术,6.5,流水线设计技术,2024/10/1,16,现代密码学理论与实践之五,第六章 并行算法的基本设计技术 6.1 划分设计技,6.2,分治设计技术,6.2.1,并行分治设计步骤,6.2.2,双调归并网络,2024/10/1,17,现代密码学理论与实践之五,6.2 分治设计技术 6.2.1 并行分治设计步骤,并行分治设计步骤,将输入划分成若干个规模相等的子问题；,同时,(,并行地,),递归求解这些子问题；,并行地归并子问题的解，直至得到原问题的解。,2024/10/1,18,现代密码学理论与实践之五,并行分治设计步骤将输入划分成若干个规模相等的子问题；202,6.2,分治设计技术,6.2.1,并行分治设计步骤,6.2.2,双调归并网络,2024/10/1,19,现代密码学理论与实践之五,6.2 分治设计技术 6.2.1 并行分治设计步骤,双调归并网络,双调序列,(p149,定义,6.2),(1,3,5,7,8,6,4,2,0),(8,7,6,4,2,0,1,3,5),(1,2,3,4,5,6,7,8,),以上都是双调序列,Batcher,定理,给定双调序列,(x,0,x,1,x,n-1,),对于,s,i,=minxi,xi+n/2,和,l,i,=maxxi,xi+n/2,，,则小序列,(s,0,s,1,s,n-1,),和大序列,(,l,0,l,1,l,n-1,),仍是双调序列,2024/10/1,20,现代密码学理论与实践之五,双调归并网络双调序列(p149定义6.2)2022/10/,双调归并网络,(4,4),双调归并网络,2024/10/1,21,现代密码学理论与实践之五,双调归并网络(4,4)双调归并网络2022/10/1021,双调归并网络,Batcher,双调归并算法,输入：双调序列,X=(x,0,x,1,x,n-1,),输出：非降有序序列,Y=(y,0,y,1,y,n-1,),Procedure BITONIC_MERG(x),Begin,(1)for i=0 to n/2-1 par-do,(1.1)s,i,=minxi,xi+n/2,(1.2),l,i,=maxxi,xi+n/2,end for,(2)Recursive Call:,(2.1)BITONIC_MERG(MIN=(s,0,s,n/2-1,),(2.2)BITONIC_MERG(MIN=(,l,0,l,n/2-1,),(3)output sequence MIN followed by sequence MAX,End,2024/10/1,22,现代密码学理论与实践之五,双调归并网络Batcher双调归并算法2022/10/10,第六章 并行算法的基本设计技术,6.1,划分设计技术,6.2,分治设计技术,6.3,平衡树设计技术,6.4,倍增设计技术,6.5,流水线设计技术,2024/10/1,23,现代密码学理论与实践之五,第六章 并行算法的基本设计技术 6.1 划分设计技,6.3,平衡树设计技术,6.3.1,设计思想,6.3.2,求最大值,6.3.3,计算前缀和,2024/10/1,24,现代密码学理论与实践之五,6.3 平衡树设计技术 6.3.1 设计思想 6,平衡树设计技术,设计思想,以树的叶结点为输入，中间结点为处理结点，由叶向根或由根向叶逐层进行并行处理。,示例,求最大值,计算前缀和,2024/10/1,25,现代密码学理论与实践之五,平衡树设计技术设计思想2022/10/1025现代密码学理,6.3,平衡树设计技术,6.3.1,设计思想,6.3.2,求最大值,6.3.3,计算前缀和,2024/10/1,26,现代密码学理论与实践之五,6.3 平衡树设计技术 6.3.1 设计思想 6,求最大值,算法,6.8:SIMD-TC(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,A,1,A,n/4,A,n/2-1,A,n/2,A,n/2+1,A,n-2,A,n-1,A,n,A,n+1,A,n+2,A,n+3,A,2n-4,A,2n-3,A,2n-2,A,2n-1,K=m-1,K=m-2,K=0,P,1,P,1,P,2,P,n/2-1,P,n/2,P,1,P,n/2-1,2024/10/1,27,现代密码学理论与实践之五,求最大值算法6.8:SIMD-TC(SM)上求最大值算,6.3,平衡树设计技术,6.3.1,设计思想,6.3.2,求最大值,6.3.3,计算前缀和,2024/10/1,28,现代密码学理论与实践之五,6.3 平衡树设计技术 6.3.1 设计思想 6,计算前缀和,问题定义,n,个元素,x,1,x,2,x,n,，前缀和是,n,个部分和：,S,i,=x,1,*x,2,*x,i,1in,这里*可以是或,串行算法：,S,i,=S,i,1,*x,i,计算时间为,O(n),并行算法：,p154,算法,6.9 SIMD-TC,上非递归算法,令,Ai=x,i,i=1n,Bh,j,和,Ch,j,为辅助数组,(h=0logn,j=1n/2,h,),数组,B,记录由叶到根正向遍历树中各结点的信息,(,求和,),数组,C,记录由根到叶反向遍历树中各结点的信息,(,播送前缀和,),2024/10/1,29,现代密码学理论与实践之五,计算前缀和问题定义2022/10/1029现代密码学理论与,计算前缀和,例：,n=8,p=8,C,01,C,08,为前缀和,2024/10/1,30,现代密码学理论与实践之五,计算前缀和例：n=8,p=8,C01C08为前缀和2,第六章 并行算法的基本设计技术,6.1,划分设计技术,6.2,分治设计技术,6.3,平衡树设计技术,6.4,倍增设计技术,6.5,流水线设计技术,2024/10/1,31,现代密码学理论与实践之五,第六章 并行算法的基本设计技术 6.1 划分设计技,6.4,倍增设计技术,6.4.1,设计思想,6.4.2,表序问题,6.4.3,求森林的根,2024/10/1,32,现代密码学理论与实践之五,6.4 倍增设计技术 6.4.1 设计思想 6.,倍增设计技术,设计思想,又称指针跳跃,(pointer jumping),技术，特别适合于处理链表或有向树之类的数据结构；,当递归调用时，所要处理数据之间的距离逐步加倍，经过,k,步后即可完成距离为,2,k,的所有数据的计算。,示例,表序问题,求森林的根,2024/10/1,33,现代密码学理论与实践之五,倍增设计技术设计思想2022/10/1033现代密码学理论,6.4,