1、Parallel Algorithms1/Ch2Y.Xu Copyright USTC2023-5-28Parallel Algorithms Chapter 2 Fundamental Techniques of Parallel AlgorithmsParallel Algorithms2/Ch22023-5-28Y.Xu Copyright USTC主要内容主要内容n2.1 平衡树方法平衡树方法n2.2 倍增技术倍增技术 n2.3 分治策略分治策略 n2.4 划分原理划分原理 n2.5 流水线技术流水线技术 Parallel Algorithms3/Ch22023-5-28Y.Xu Co
2、pyright USTC2.1 平衡树方法平衡树方法n设计思想设计思想树叶结点为输入，中间结点为处理结点，由叶向根或由根树叶结点为输入，中间结点为处理结点，由叶向根或由根向叶逐层并行处理。向叶逐层并行处理。n示例示例求最大值求最大值计算前缀和计算前缀和Parallel Algorithms4/Ch22023-5-28Y.Xu Copyright USTCn算法算法2.1 SIMD-SM上求最大值算法上求最大值算法Begin for k=m-1 to 0 do for j=2k to 2k+1-1 par-do Aj=maxA2j,A2j+1 end for end forend时间分析时间分析
3、t(n)=mO(1)=O(logn)p(n)=n/2c(n)=O(nlogn)非成本最优2.1 平衡树方法平衡树方法Parallel Algorithms5/Ch22023-5-28Y.Xu Copyright USTC前缀和前缀和n问题定义问题定义n个元素个元素x1,x2,xn，前缀和是，前缀和是n个部分和：个部分和：Si=x1*x2*xi,1inin 这里这里*可以是或可以是或n串行算法：串行算法：Si=Si1*xi 计算时间为计算时间为 O(n)n并行算法：并行算法：p56算法算法2.2 SIMD-SM上非递归算法上非递归算法(高层描述高层描述)p58算法算法2.3 SIMD-SM上非递
4、归算法上非递归算法(底层描述底层描述)令令Ai=xi,i=1n,Bh,j和和Ch,j为辅助数组为辅助数组(h=0logn,j=1n/2h)数组数组B记录由叶到根正向遍历树中各结点的信息记录由叶到根正向遍历树中各结点的信息(求和求和)数组数组C记录由根到叶反向遍历树中各结点的信息记录由根到叶反向遍历树中各结点的信息(播送前缀和播送前缀和)2.1 平衡树方法平衡树方法Parallel Algorithms6/Ch22023-5-28Y.Xu Copyright USTCp56 算法算法2.2 SIMD-SM上非递归算法上非递归算法begin (1)for j=1 to n par-do /初始化初
5、始化 B0,j=Aj end if (2)for h=1 to logn do /正向遍历正向遍历 for j=1 to n/2h 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/2h par-do (i)if j=even then /该结点为其父结点的右儿子该结点为其父结点的右儿子 Ch,j=Ch+1,j/2 end i
6、f (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 end2.1 平衡树方法平衡树方法Parallel Algorithms7/Ch22023-5-28Y.Xu Copyright USTC主要内容主要内容n2.1 Balanced Trees Methodn2.2 Doubling Techniques n2.3 Divide-and-Conquer Str
7、ategy n2.4 Partitioning Principle n2.5 Pipelining Techniques Parallel Algorithms8/Ch22023-5-28Y.Xu Copyright USTC主要内容主要内容n2.1 平衡树方法平衡树方法n2.2 倍增技术倍增技术 n2.3 分治策略分治策略 n2.4 划分原理划分原理 n2.5 流水线技术流水线技术 Parallel Algorithms9/Ch22023-5-28Y.Xu Copyright USTCn设计思想设计思想又称指针跳跃又称指针跳跃(pointer jumping)技术，特别适合于处理链技术，特别
8、适合于处理链表或有向树之类的数据结构；表或有向树之类的数据结构；当递归调用时，所要处理数据之间的距离逐步加倍，经过当递归调用时，所要处理数据之间的距离逐步加倍，经过k步后即可完成距离为步后即可完成距离为2k的所有数据的计算。的所有数据的计算。n示例示例表序问题表序问题求森林的根求森林的根2.2 倍增技术倍增技术Parallel Algorithms10/Ch22023-5-28Y.Xu Copyright USTC表序问题：表序问题：n问题描述问题描述 n个元素的列表个元素的列表L，求出每个元素在，求出每个元素在L 中的次第号中的次第号(秩或位序或秩或位序或rank(k)，rank(k)可视为
9、元素可视为元素k至表尾的距离；至表尾的距离；n示例：示例：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
10、2.2 倍增技术倍增技术Parallel Algorithms11/Ch22023-5-28Y.Xu Copyright USTC表序问题：表序问题：n算法：算法：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(
11、n)=O(logn)p(n)=nnlog2.2 倍增技术倍增技术Parallel Algorithms12/Ch22023-5-28Y.Xu Copyright USTC求森林的根求森林的根n问题描述问题描述 一组有向树一组有向树F中中,如果如果是是F中的一条弧，则中的一条弧，则pi=j(即即j是是i的双亲的双亲)；若；若i为根，则为根，则pi=i。求每个结点。求每个结点j(j=1n)的树根的树根sj.n示例示例初始时初始时P1=p2=5 p3=p4=p5=6 P6=p7=8 p8=8P9=10 p10=11 p11=12 p12=13 p13=13 si=pi 2.2 倍增技术倍增技术Par
12、allel Algorithms13/Ch22023-5-28Y.Xu Copyright USTC求森林的根求森林的根n示例示例 第一次迭代后第一次迭代后 第二次迭代后第二次迭代后n算法算法：p61算法算法2.5n运行时间运行时间：t(n)=O(logn)2.2 倍增技术倍增技术Parallel Algorithms14/Ch22023-5-28Y.Xu Copyright USTC主要内容主要内容n2.1 Balanced Trees Methodn2.2 Doubling Techniques n2.3 Divide-and-Conquer Strategy n2.4 Partition
13、ing Principle n2.5 Pipelining Techniques Parallel Algorithms15/Ch22023-5-28Y.Xu Copyright USTC主要内容主要内容n2.1 平衡树方法平衡树方法n2.2 倍增技术倍增技术 n2.3 分治策略分治策略 n2.4 划分原理划分原理 n2.5 流水线技术流水线技术 Parallel Algorithms16/Ch22023-5-28Y.Xu Copyright USTCn设计思想设计思想将原问题划分成若干个相同的子问题分而治之，若子问题仍将原问题划分成若干个相同的子问题分而治之，若子问题仍然较大，则可以反复递归
14、应用分治策略处理这些子问题，直然较大，则可以反复递归应用分治策略处理这些子问题，直至子问题易求解。至子问题易求解。n求解步骤求解步骤将输入划分成若干个规模相等的子问题；将输入划分成若干个规模相等的子问题；同时同时(并行地并行地)递归求解这些子问题；递归求解这些子问题；并行地归并子问题的解成为原问题的解。并行地归并子问题的解成为原问题的解。n示例示例SIMD-SM模型上的模型上的FFT递归算法递归算法2.3 分治策略分治策略Parallel Algorithms17/Ch22023-5-28Y.Xu Copyright USTCFFT递归算法递归算法nDFT离散富里叶变换的定义离散富里叶变换的定
15、义 给定向量给定向量 ，DFT将将A变换为变换为 ，即，即 写成矩阵形式为写成矩阵形式为 注：串行直接计算注：串行直接计算DFT需要需要O(n2)TnaaaA),.,(110TnbbbB),.,(1101,10/210ienjabninkkjkj这里110)1)(1()1(21012100000110nnnnnnnaaabbb2.3 分治策略分治策略Parallel Algorithms18/Ch22023-5-28Y.Xu Copyright USTCFFT递归算法：递归算法：将原问题的将原问题的DFT划分为两个规模为划分为两个规模为n/2的子问题的的子问题的DFTnSIMD-SM模型上的算
16、法：模型上的算法：p64算法算法2.7 2.3 分治策略分治策略Parallel Algorithms19/Ch22023-5-28Y.Xu Copyright USTC主要内容主要内容n2.1 Balanced Trees Methodn2.2 Doubling Techniques n2.3 Divide-and-Conquer Strategy n2.4 Partitioning Principle n2.5 Pipelining Techniques Parallel Algorithms20/Ch22023-5-28Y.Xu Copyright USTC主要内容主要内容n2.1 平衡
17、树方法平衡树方法n2.2 倍增技术倍增技术 n2.3 分治策略分治策略 n2.4 划分原理划分原理 n2.5 流水线技术流水线技术 Parallel Algorithms21/Ch22023-5-28Y.Xu Copyright USTC划分原理：划分原理：n设计思想设计思想将原问题划分成将原问题划分成p个独立的规模几乎相等的子问题；个独立的规模几乎相等的子问题；p台处理器并行地求解各子问题。台处理器并行地求解各子问题。Remark:划分重点在于划分重点在于:子问题易解子问题易解,组合成原问题的解方便组合成原问题的解方便;n常见划分方法常见划分方法均匀划分均匀划分 方根划分方根划分 对数划分对
18、数划分 功能划分功能划分2.4 划分原理划分原理Parallel Algorithms22/Ch22023-5-28Y.Xu Copyright USTC均匀划分：均匀划分：n方法方法:n个元素个元素A1.n分成分成p组，每组组，每组A(i-1)n/p+1.in/p，i=1pn示例示例:MIMD-SM模型上的模型上的PSRS排序排序 begin (1)均匀划分：将均匀划分：将n个元素个元素A1.n均匀划分成均匀划分成p段，每个段，每个pi处理处理A(i-1)n/p+1.in/p (2)局部排序：局部排序：pi调用串行排序算法对调用串行排序算法对A(i-1)n/p+1.in/p排序排序 (3)选
19、取样本：选取样本：pi从其有序子序列从其有序子序列A(i-1)n/p+1.in/p中选取中选取p个样本元素个样本元素 (4)样本排序：用一台处理器样本排序：用一台处理器对对p2个样本元素进行串行排序个样本元素进行串行排序 (5)选择主元：用一台处理器从排好序的样本序列中选取选择主元：用一台处理器从排好序的样本序列中选取p-1个主元，并播送给其他个主元，并播送给其他pi (6)主元划分：主元划分：pi按主元将有序段按主元将有序段A(i-1)n/p+1.in/p划分成划分成p段段 (7)全局交换：各处理器将其有序段按段号交换到对应的处理器中全局交换：各处理器将其有序段按段号交换到对应的处理器中 (
20、8)归并排序：各处理器对接收到的元素进行归并排序归并排序：各处理器对接收到的元素进行归并排序 end.2.4 划分原理划分原理Parallel Algorithms23/Ch22023-5-28Y.Xu Copyright USTCn例 PSRS排序过程。N=27，p=3，PSRS排序如下：2.4 划分原理划分原理Parallel Algorithms24/Ch22023-5-28Y.Xu Copyright USTC对数划分：对数划分：n方法方法:n个元素个元素A1.n分成分成A(i-1)logn+1.ilogn，i=1n/logn，p=n/lognn示例示例:PRAM-CREW上的对数划分
21、并行归并排序上的对数划分并行归并排序 (1)归并过程归并过程:设有序组设有序组A1.n和和B1.m ji=rank(bilogm:A)为为bilogm在在A中的位序，即中的位序，即A中小于等于中小于等于bilogm的元素个数的元素个数 (2)例：例：A=(4,6,7,10,12,15,18,20),B=(3,9,16,21)n=8,m=4,p=2 =logm=log4=2 =j1=rank(blogm:A)=rank(b2:A)=rank(9:A)=3,j2=8 B0:3,9 B1:16,21 A0:4,6,7 A1:10,12,15,18,20 A和和B归并归并化为化为(A0,B0)和和(A
22、1,B1)的归并的归并 2.4 划分原理划分原理Parallel Algorithms25/Ch22023-5-28Y.Xu Copyright USTC方根划分：方根划分：n方法方法:n个元素个元素A1.n分成分成A(i-1)n(1/2)+1.in(1/2)，i=1n(1/2),p=n(1/2)n示例示例:SIMD-CREW模型上的模型上的Valiant归并排序算法归并排序算法(1975年发表年发表)/有序组有序组A1.p、B1.q,(假设假设p=q),处理器数处理器数k=(pq)(1/2)begin (1)方根划分：方根划分：A,B分别按分别按ip(1/2)和和iq(1/2)分成若干段；分
23、成若干段；(2)段间比较：段间比较：A划分元与划分元与B划分元比较划分元比较(共有共有p(1/2)q(1/2)对对)，确定，确定A划分元应划分元应 插入插入B中的区段；中的区段；(3)段内比较：段内比较：A划分元与划分元与B相应段内元素进行比较，并插入适当的位置；相应段内元素进行比较，并插入适当的位置；(4)递归归并：递归归并：B按插入的按插入的A划分元重新分段，与划分元重新分段，与A相应段相应段(A除去原划分元除去原划分元)构成了构成了 成对的段组，对每对段组递归执行成对的段组，对每对段组递归执行(1)(3)，直至，直至A组为组为0时，递归时，递归 结束结束 end.时间复杂度：若时间复杂度
24、：若p=q=n，t(n)=O(loglogn)p(n)=n2.4 划分原理划分原理Parallel Algorithms26/Ch22023-5-28Y.Xu Copyright USTC功能划分：功能划分：n方法方法:n个元素个元素A1.n分成等长的分成等长的p组，每组满足某种特性。组，每组满足某种特性。n示例示例:(m,n)选择问题选择问题(求出求出n个元素中前个元素中前m个最小者个最小者)(1)划分时要求每组元素个数必须大于划分时要求每组元素个数必须大于m；(2)算法是基于算法是基于Batcher排序网络，以后介绍排序网络，以后介绍 2.4 划分原理划分原理Parallel Algori
25、thms27/Ch22023-5-28Y.Xu Copyright USTC主要内容主要内容n2.1 Balanced Trees Methodn2.2 Doubling Techniques n2.3 Divide-and-Conquer Strategy n2.4 Partitioning Principle n2.5 Pipelining Techniques Parallel Algorithms28/Ch22023-5-28Y.Xu Copyright USTC主要内容主要内容n2.1 平衡树方法平衡树方法n2.2 倍增技术倍增技术 n2.3 分治策略分治策略 n2.4 划分原理划分
26、原理 n2.5 流水线技术流水线技术 Parallel Algorithms29/Ch22023-5-28Y.Xu Copyright USTCn设计思想设计思想将算法流程划分成将算法流程划分成p个前后衔接的任务片断，每个任务片断的输出作为下一个前后衔接的任务片断，每个任务片断的输出作为下一个任务片断的输入；个任务片断的输入；所有任务片断按同样的速率产生出结果。所有任务片断按同样的速率产生出结果。nRemark流水线技术是一种广泛应用在并行处理中的技术；流水线技术是一种广泛应用在并行处理中的技术；脉动算法脉动算法(Systolic algorithm)是其中一种流水线技术；是其中一种流水线技术
27、；n示例：示例：5-point DFT的计算。应用秦九韶的计算。应用秦九韶(Horner)法则，法则，04142434440313233343021222324201112131410010203040021426316444021426312433021426384220112233441100102030400)()()()()(aaaaayaaaaayaaaaayaaaaayaaaaayaaaaabyaaaaabyaaaaabyaaaaabyaaaaaby2.5 流水线技术流水线技术Parallel Algorithms30/Ch22023-5-28Y.Xu Copyright USTCn示例：示例：5-point DFT的计算，的计算，p(n)=n-1,t(n)=2n-2=O(n)2.5 流水线技术流水线技术Parallel Algorithms31/Ch2Y.Xu Copyright USTC2023-5-28 End of Chapter 2
