中国科学技术大学：《并行计算 Parallel Computing》课程教学资源（PPT课件讲稿）第二篇 并行算法的设计 第六章 并行算法的基本设计技术

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 第二篇并行算法的设计 第四章并行算法的设计基础 第五章并行算法的一般设计方法 第六章并行算法的基本设计技术 第七章并行算法的一般设计过程

第二篇 并行算法的设计 第四章 并行算法的设计基础 第五章 并行算法的一般设计方法 第六章 并行算法的基本设计技术 第七章 并行算法的一般设计过程

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 第六章并行算法的基本设计技术 61划分设计技术 62分治设计技术 63平衡树设计技术 64倍增设计技术 65流水线设计技术

第六章 并行算法的基本设计技术 6.1 划分设计技术 6.2 分治设计技术 6.3 平衡树设计技术 6.4 倍增设计技术 6.5 流水线设计技术

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 61划分设计技术 61.1均匀划分技术 61.2方根划分技术 61.3对数划分技术 6.1.4功能划分技术

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

中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 划分方法 均匀划分技术 n个元素A[1.n分成P组,每组A[-)n/p+1.inp],i=1-~p 示例:MMD-SM模型上的PSRS排序 begin ()均勺划分:将n个元素AI.n]均勺划分成p段,每个p处理 A[(i-1)n/p+1.in/p] (2)局部排序:p调用串行排序算法对A[(-)n/p+1.in/]排序 (3)选取样本:p从其有序子序列A[〔-1)n/p+1.in/]中选取p个样本元素 (4)样本排序:用一台处理器对p2个样本元素进行串行排序 (5)选择主元:用一台处理器从排好序的样本序列中选取p-1个主元,并 播送给其他p (6)主元划分:P按主元将有序段A[(-1n/p+1.in/]划分成p段 (7)全局交换:各处理器将其有序段按段号交换到对应的处理器中 (8)归并排序:各处理器对接收到的元素迸行归并排序 end 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 5 2021/2/19 ▪ 划分方法 均匀划分技术 n个元素A[1..n]分成p组，每组A[(i-1)n/p+1..in/p]，i=1~p ▪ 示例：MIMD-SM模型上的PSRS排序 begin (1)均匀划分：将n个元素A[1..n]均匀划分成p段，每个pi处理 A[(i-1)n/p+1..in/p] (2)局部排序：pi调用串行排序算法对A[(i-1)n/p+1..in/p]排序 (3)选取样本：pi从其有序子序列A[(i-1)n/p+1..in/p]中选取p个样本元素 (4)样本排序：用一台处理器对p 2个样本元素进行串行排序 (5)选择主元：用一台处理器从排好序的样本序列中选取p-1个主元，并 播送给其他pi (6)主元划分：pi按主元将有序段A[(i-1)n/p+1..in/p]划分成p段 (7)全局交换：各处理器将其有序段按段号交换到对应的处理器中 (8)归并排序：各处理器对接收到的元素进行归并排序 end

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 均匀划分技术 ■例6.1PSRS排序过程。N=27,p=3,PSR排序如下 a)均匀划分:1546489339672|9114366940896197122154539784158322733720 (b)局部排序:6141539464872|9193122136405461698997202732335358728497 (c)正则采样 63972124069203372 (d)采样排序 61220333940697272 (e)选择主元: (f)主元划分:61415394648729193122136405461698997|202732331535872|84 (8)全局交换:[6141512120232383968364054619558291989728497 ()归并排序:[6121415202127323363940464853545861697272848991939797 国家高性能计算中心(合肥 2021/2/19 图6

国家高性能计算中心（合肥） 6 2021/2/19 均匀划分技术 ▪ 例6.1 PSRS排序过程。N=27，p=3，PSRS排序如下： 15 46 48 93 39 6 72 91 14 36 69 40 89 61 97 12 21 54 53 97 84 58 32 27 33 72 20 6 14 15 39 46 48 72 91 93 12 21 36 40 54 61 69 89 97 20 27 32 33 53 58 72 84 97 6 39 72 12 40 69 20 33 72 6 12 20 33 39 40 69 72 72 33 69 6 14 15 39 46 48 72 91 93 12 21 36 40 54 61 69 89 97 20 27 32 33 53 58 72 84 97 6 14 15 6 14 15 12 21 20 27 32 33 39 46 48 36 40 54 61 69 53 58 72 91 93 89 97 72 84 97 12 20 21 27 32 33 36 39 40 46 48 53 54 58 61 69 72 72 84 89 91 93 97 97 图6.1 (a) 均匀划分： (b) 局部排序： (c) 正则采样： (d) 采样排序： (e) 选择主元： (f) 主元划分： (h) 归并排序： (g) 全局交换：

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 61划分设计技术 61.1均匀划分技术 61.2方根划分技术 61.3对数划分技术 6.1.4功能划分技术

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

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 方根剡分技术 ■划分方法 n个元素A[1.n分成A[(-)n^(1/2)+1.n^(12)],i=1~n^(1/2) 示例: SIMD-CREW模型上的k=」 Valiant归并(975年发表) ∥有序组A[p、B[1.qu(假设p<=q),处理器数k=网」 begIn (1)方根划分:A,B分别小D和份成若干段(=1-p=1-q; (2)段间比较:A划分元与B划分元比较(至多对) 确定A划分元应插入B中的区段; 3)段内比较:A划分元与B相应段内元素进行比较,并插入适当的位置; (4)递归归并:B按插入的A划分元重新分段,与A相应段(A除去原划分元) 构成了成对的段组,对每对段组递归执行()~(3),直至A 组为0时,通归结束;各组仍按k=分配处理器; en 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 8 2021/2/19 方根划分技术 ▪ 划分方法 n个元素A[1..n]分成A[(i-1)n^(1/2)+1..in^(1/2)]，i=1~n^(1/2) ▪ 示例：SIMD-CREW模型上的 Valiant归并(1975年发表) //有序组A[1..p]、B[1..q], (假设p<=q), 处理器数 begin (1)方根划分: A,B分别按 ； (2)段间比较: A划分元与B划分元比较(至多 对)， 确定A划分元应插入B中的区段； (3)段内比较: A划分元与B相应段内元素进行比较，并插入适当的位置； (4)递归归并: B按插入的A划分元重新分段，与A相应段(A除去原划分元) 构成了成对的段组，对每对段组递归执行(1)~(3)，直至A 组为0时，递归结束; 各组仍按 分配处理器； end. k =  pq k =  pq i p和 j q分成若干段（i =1~  p、j =1~  q）  p q k =  pq

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 方根剡分技术 示例:A=(1,3,8,9,1,13,15,16},p=8;B=(2,4,5,6,7,10,12,14,17],q=9 A:13891113*1516 3 (1)(2 B:245*6710*121417 138*91113*1516 B:245*6710*121417 (p1=2)lA2:911(p2=2)|A2:1516 B1:245678(q1=6)|B2:101213(q2=3)B3:1417 1 ☆ A1:1 B11:23*B12:45678 B:123456781910111213l141516117 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 9 2021/2/19 方根划分技术 ◼ 示例: A={1,3,8,9,11,13,15,16},p=8; B={2,4,5,6,7,10,12,14,17},q=9 A: 1 3 8* 9 11 13* 15 16 B: 2 4 5* 6 7 10* 12 14 17* （p=8, p=3, p=2) （q = 9, q= 3, q = 3) (1)(2) A: 1 3 8* 9 11 13* 15 16 B: 2 4 5* 6 7 10* 12 14 17* (3)  A1 : 1 3 (p1=2) A2 : 9 11 (p2=2) A2 : 15 16 B1 : 2 4 5 6 7 8(q1=6) B2 : 10 12 13(q2=3) B3 : 14 17 A1 : 1 3* (p1=2) ...... ...... B1 : 2 4 5* 6 7 8*(q1=6) ...... ...... A11 : 1* A11 : ...... ...... B11 : 2 3* B12 : 4 5 6 7 8 ...... ...... A: B: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 方根剡分技术 算法分析 (1算法在并行递归过程中所需的处理器数≤k=m」 段间比较:F比较对数≤/m」k 段内比较: pIdqhdslvpg」k 递归调用:设AB分成若干子段对为(P1,q1),(p2q2),… 则∑p≤p,∑q≤q,由 Cauchy不等式=> ∑\P」∑P」L∑n∑k{mk 综上,整个过程可用处理器数k=完成。 (2)时间分析 记入1是第次递归后的A组最大长度,=>=p,… 算法在2=常数C时终止递归,即p上常数C i≤ loglog p+常数C1 由1知算法中其他各步的时间为O(1),所以 Valiant归并算法时间 t(p, q=O(og log p) psq 国家高性能计算中心(合肥 2021/2/19

国家高性能计算中心（合肥） 10 2021/2/19 ◼ 算法分析 方根划分技术 (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 归并算法时间 t k ( p,q) = O(log log p) p  q

中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 61划分设计技术 61.1均匀划分技术 61.2方根划分技术 61.3对数划分技术 6.1.4功能划分技术

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