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