中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 对数剡分技术 ■划分方法 n个元素A[1.n]分成A[(-)logn+1.logn],i=1-n/og 示例: PRAM-CREW上的对数划分并行归并排序 (1)归并过程:设有序组A[1.n]和B[1.m B B B ogle gmM+l b(+1) logm A f(i)+1 Ao j]=rank(bgm:A)为bgm在A中的位序,即A中小于等于bgm的元素个数 (2)例:A=(4,67,10,12,1518,20),B=(3,9,16,21)n=8,m=4 >logm=log4=2 >jll]=rank(blogm: A)=rank(b2: A)=rank(9: A)=3, j[2]=8 Bo:3,9 B1:16,21 A0:4,6,7A;:10,12,15,18,20 A和B归并化为(A,B0)和(A1,B1)的归并 国家高性能计算中心(合肥 2021/2/19 12
国家高性能计算中心（合肥） 12 2021/2/19 对数划分技术 ▪ 划分方法 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(b2 :A)=rank(9:A)=3, j[2]=…=8 B0 : 3, 9 B1 : 16, 21 A0 : 4, 6, 7 A1 : 10, 12, 15, 18, 20 A和B归并化为(A0 , B0 )和(A1 , B1 )的归并 b1 blogm B = B1 Bi a1 A = A1 Ai ... ... ... b ... logm +1 ... ... aj(1) aj(1)+1 aj(2) ... ... b2logm bilogm +1 b(i+1)logm aj(i )+1 aj(i+1) ... ... A0 B0
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 61划分设计技术 61.1均匀划分技术 61.2方根划分技术 61.3对数划分技术 61.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组,每组满足某种特性。 示例:(m,n)选择问题(求出n个元素中前m个最小者) 功能划分:要求每组元素个数必须大于m; ■算法:p148算法6.4 输入:A=(a1,an);输出:前m个最小者; Begin ()功能划分:将A划分成8=n/m组,每组含m个元素; (2)局部排序:使用 Batcher排序网络将各组并行进行排序; (3)两两比较:将所排序的各组两两进行比较,从而形成MN序列; (4)排序-比较:对各个MN序列,重复执行第(2)和第(3)步,直至 选出m个最小者。 End 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 14 2021/2/19 功能划分技术 ▪ 划分方法 n个元素A[1..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
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr 功能划分技术 MAX MIN m mrm MAX MIN mrm mr m 图6.3(m-n)-选择过程 国家高性能计算中心(合肥 2021/2/19 15
国家高性能计算中心（合肥） 15 2021/2/19 功能划分技术 (M) m m m m m m (M) m m MAX MIN MAX MIN 图6.3 (m-n)-选择过程 S S S S S S ...
中国料学火计算机科学与波术系 niversity of Science and Technology 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 流水线设计技术