中国料学火计算机科学与波术系 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