中国料学火计算机科学与波术系 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) 全局交换：