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