南京大学：《并行处理技术——分布式与并行计算 Distributed and Parallel computing（并行计算——结构、算法、编程）》课程教学资源（课件讲稿）第六章 并行算法的基本设计技术

方根划分技术 ·算法分析 (1)算法在并行递归过程中所需的处理器数≤k=L√P9 段间比较：VpLV比较对数≤Vp四于k; 段内比较：WP.WG」Dspa上k 递归调用：设A,B分成若干子段对为p1,q1),(P2,q2),· 则∑p:≤p,∑q:≤q,由Cauchy不等式=> ∑Wpa.Js∑p4,sL∑p,∑ns.pa=k 综上，整个过程可用处理器数k=√p西完成。 (2)时间分析 记是第1次递归后的A组最大长度，=>=p,≤V,s…≤p 算法在，=常数C时终止递归，即p”上常数C=>i≤1 og log p+常数C 由(1)知算法中其他各步的时间为O(1),所以Valiant归并算法时间 (p,q)=O(loglogp)p<q 2011/10/25

 算法分析 (1)算法在并行递归过程中所需的处理器数≤k   pq 段间比较: p  q 比较对数≤ pq＝k ； 段内比较:  p （  q －1）  pq ＝k 递归调用: 设 A,B 分成若干子段对为(p1,q1), (p2,q2),…… 则∑pi≤p, ∑qi≤q, 由 Cauchy 不等式＝>  p q   p q   p q   pq k  i i   i i   i i   综上，整个过程可用处理器数k   pq完成。 (2)时间分析 记λi是第 i 次递归后的 A 组最大长度，＝>0  p ,    i i i p      2   1  算法在i  常数C 时终止递归，即p  C i  常数  2 ＝> 1 i  log log p 常数C 由(1)知算法中其他各步的时间为 O(1), 所以 Valiant 归并算法时间 tk ( p,q)  O(loglog p) p  q 13 2011/10/25 方根划分技术

6.1划分设计技术 6.1.1均匀划分技术 6.1.2方根划分技术 6.1.3对数划分技术 6.1,4功能划分技术

6.1 划分设计技术 6.1.1 均匀划分技术 6.1.2 方根划分技术 6.1.3 对数划分技术 6.1.4 功能划分技术

对数划分技术 *关于划分技术的思考 *为了确定A序列中的划分元素在B序列中的全局位置， 所以划分元素必须在各段之间实行全局比较。 *如果在选取A序列中的划分元素时，就考虑到了它在 B序列中的全局位序，那么就不必对划分元素施行段 间的全局比较，而可直接对按划分元素所断开的各 段组两两进行归并，便可完成两个原序列的归并。 2011/10/25 15

对数划分技术  关于划分技术的思考  为了确定A序列中的划分元素在B序列中的全局位置， 所以划分元素必须在各段之间实行全局比较。  如果在选取A序列中的划分元素时，就考虑到了它在 B序列中的全局位序，那么就不必对划分元素施行段 间的全局比较，而可直接对按划分元素所断开的各 段组两两进行归并，便可完成两个原序列的归并。 15 2011/10/25

对数划分技术 划分方法 n个元素A[1.n分成A[(-1)logn+1..ilogn,i=1~n/1ogn *示例：PRAM-CREW.上的对数划分并行归并排序 (1)归并过程：设有序组A[1.n和B[1m B B= ···bogm b2o啊 b()logm A= a···a0 a0)+ ···a2) ai)+1 a(4) 4 A A j间=rank(boem:A)为boem在A中的位序，即A中小于等于boem的元素个数 (2)例：A=(4,6,7,10,12,15,18,20),B=(3,9,16,21)n=8,m=4 =>logm=1og4=2 =>j[1]=rank(bIogm:A)=rank(b2:A)=rank(9:A)=3,j[2]=.=8 Bo:3,9B:16,21 A:4,6,7A:10,12,15,18,20 A和B归并化为(Ao,B)和(A1,B)的归并 2011/10/25 16

对数划分技术  划分方法 n个元素A[1..n]分成A[(i-1)logn+1..ilogn]，i=1~n/logn  示例：PRAM-CREW上的对数划分并行归并排序 (1)归并过程: 设有序组A[1..n]和B[1..m] j[i]=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 =>logm=log4=2 => j[1]=rank(blogm:A)=rank(b 2:A)=rank(9:A)=3, j[2]=…=8 B 0: 3, 9 B1: 16, 21 A 0: 4, 6, 7 A1: 10, 12, 15, 18, 20 A和B归并化为(A 0, B 0)和(A1, B1)的归并 1 log = 1 1 = 1 i ... ... ... ... log +1 ... ... (1) (1)+1 (2) ... ... 2log log +1 ( +1)log ( )+1 ( +1) ... ... 0 0 16 2011/10/25

6.1划分设计技术 6.1.1均匀划分技术 6.1,2方根划分技术 6.1.3对数划分技术 6.1.4功能划分技术

6.1 划分设计技术 6.1.1 均匀划分技术 6.1.2 方根划分技术 6.1.3 对数划分技术 6.1.4 功能划分技术