pc具体的算法设计方法精要.ppt

并行计算中国科学技术大学计算机科学与技术系中国科学技术大学计算机科学与技术系国家高性能计算中心国家高性能计算中心( (合肥合肥) ) 2004 2004 年年12 12月月第二篇并行算法的设计第四章并行算法的设计基础第五章并行算法的一般设计方法第六章并行算法的基本设计技术第七章并行算法的一般设计过程第六章并行算法的基本设计技术 划分设计技术 分治设计技术 平衡树设计技术 倍增设计技术 流水线设计技术 划分设计技术 均匀划分技术 方根划分技术 对数划分技术 功能划分技术国家高性能计算中心(合肥) 5 2017-1-29 均匀划分技术??划分方法划分方法 n n个元素个元素 A[1..n] A[1..n] 分成分成 p p组,每组组,每组 A[(i-1)n/p+1..in/p] A[(i-1)n/p+1..in/p] , , i=1~p i=1~p ??示例: 示例: MIMD-SM MIMD-SM 模型上的模型上的 PSRS PSRS 排序排序 begin begin (1) (1) 均匀划分:将均匀划分:将 n n个元素个元素 A[1..n] A[1..n] 均匀划分成均匀划分成 p p段,每个段,每个 p p i i处理处理 A[(i-1)n/p+1..in/p] A[(i-1)n/p+1..in/p] (2) (2) 局部排序: 局部排序: p p i i调用串行排序算法对调用串行排序算法对 A[(i-1)n/p+1..in/p] A[(i-1)n/p+1..in/p] 排序排序 (3) (3) 选取样本: 选取样本: p p i i从其有序子序列从其有序子序列 A[(i-1)n/p+1..in/p] A[(i-1)n/p+1..in/p] 中选取中选取 p p个样本元素个样本元素 (4) (4) 样本排序:用一台处理器对样本排序:用一台处理器对 p p 2 2个样本元素进行串行排序个样本元素进行串行排序 (5) (5) 选择主元:用一台处理器从排好序的样本序列中选取选择主元:用一台处理器从排好序的样本序列中选取 p-1 p-1 个主元,并个主元,并播送给其他播送给其他 p p i i (6) (6) 主元划分: 主元划分: p p i i按主元将有序段按主元将有序段 A[(i-1)n/p+1..in/p] A[(i-1)n/p+1..in/p] 划分成划分成 p p段段 (7) (7) 全局交换:各处理器将其有序段按段号交换到对应的处理器中全局交换:各处理器将其有序段按段号交换到对应的处理器中 (8) (8) 归并排序:各处理器对接收到的元素进行归并排序归并排序:各处理器对接收到的元素进行归并排序 end. end. 国家高性能计算中心(合肥) 6 2017-1-29 均匀划分技术??例例 PSRS PSRS 排序过程。排序过程。 N=27 N=27 , , p=3 p=3 , , PSRS PSRS 排序如下排序如下: : 划分设计技术 均匀划分技术 方根划分技术 对数划分技术 功能划分技术国家高性能计算中心(合肥) 8 2017-1-29 方根划分技术??划分方法划分方法 n n个元素个元素 A[1..n] A[1..n] 分成分成 A[(i-1)n^(1/2)+1..in^(1/2)] A[(i-1)n^(1/2)+1..in^(1/2)] , , i=1~n^(1/2) i=1~n^(1/2) ??示例: 示例: SIMD-CREW SIMD-CREW 模型上的模型上的 Valiant Valiant 归并归并(1975 (1975 年发表年发表) ) // // 有序组有序组 A[1..p] A[1..p] 、、 B[1..q], ( B[1..q], ( 假设假设 p<=q), p<=q), 处理器数处理器数 begin begin (1) (1) 方根划分方根划分: A,B : A,B 分别按分别按; ; (2) (2) 段间比较段间比较: A : A 划分元与划分