第六章 并行算法的基本设计技术

《第六章 并行算法的基本设计技术》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、并行计算第二篇并行算法的设计第四章并行算法的设计基础第五章并行算法的一般设计方法第六章并行算法的基本设计技术第七章并行算法的一般设计过程第六章并行算法的基本设计技术6.1划分设计技术6.2分治设计技术6.3平衡树设计技术6.4倍增设计技术6.5流水线设计技术6.1划分设计技术6.1.1均匀划分技术6.1.2方根划分技术6.1.3对数划分技术6.1.4功能划分技术均匀划分技术划分方法n个元素A[1..n]分成p组，每组A[(i-1)n/p+1..in/p]，i=1~p示例：MIMD-SM模型上的PSRS排序begin(1)均

2、匀划分：将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)样本排序：用一台处理器对p2个样本元素进行串行排序(5)选择主元：用一台处理器从排好序的样本序列中选取p-1个主元，并播送给其他pi(6)主元划分：pi按主元将有序段A[(i-1)n/p+1..in/p]划分成p段(7)全局交换：各处理器将其有序段按段号

3、交换到对应的处理器中(8)归并排序：各处理器对接收到的元素进行归并排序end.2021/10/55国家高性能计算中心（合肥）均匀划分技术例6.1PSRS排序过程。N=27，p=3，PSRS排序如下：2021/10/56国家高性能计算中心（合肥）6.1划分设计技术6.1.1均匀划分技术6.1.2方根划分技术6.1.3对数划分技术6.1.4功能划分技术方根划分技术划分方法n个元素A[1..n]分成A[(i-1)n^(1/2)+1..in^(1/2)]，i=1~n^(1/2)示例：SIMD-CREW模型上的Valiant归并(1

4、975年发表)//有序组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.2021/10/58国家高性能计算中心（合肥）方根划分技术2021/10/59国

5、家高性能计算中心（合肥）方根划分技术2021/10/510国家高性能计算中心（合肥）6.1划分设计技术6.1.1均匀划分技术6.1.2方根划分技术6.1.3对数划分技术6.1.4功能划分技术对数划分技术划分方法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,

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]=…=8B0:3,9B1:16,21A0:4,6,7A1:10,12,15,18,20A和B归并化为(A0,B0)和(A1,B1)的归并2021/10/512国家高性能计算中心（合肥）6.1划分设计技术6.1.1均匀划分技术6.1.2方根划分技术6.1.3对数划分技术6.1.4功能划分技术功能划分技术划分方法n个元素A[1..n

7、]分成等长的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个最小者。End2021/10/514国家高性能计算中心（

8、合肥）功能划分技术2021/10/515国家高性能计算中心（合肥）第六章并行算法的基本设计技术6.1划分设计技术6.2分治设计技术6.3平衡树设计技术6.4倍增设计技术6.5流水线设计技术6.2分治设计技术6.2.1并行分治设计步骤6.2.2双调归并网络并行分治设计步骤将输入划分成若干个规模相等的子问题