资源描述：
《第六章-并行算法一般设计技术.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、6.1划分设计技术6.2分治设计技术6.3平衡树设计技术6.4倍增设计技术6.5流水线设计技术6.1划分设计技术求解步骤：①将给定问题分成p个相互独立的长度基本的子问题；②用p台处理器并行求解每个子问题。划分方法：均匀、方根、对数技术和功能划分等6.1.1均匀划分技术划分方法n个元素A[1..n]分成p组，每组A[(i-1)n/p+1..in/p]，i=1~p示例：算法6.1MIMD-SM模型上的PSRS排序begin(1)均匀划分：将n个元素A[1..n]均匀划分成p段，每个pi处理A[(i-1)n/p+1..in/p](2)局部排序：pi调用串行排序算法对A[
2、(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)全局交换：各处理器将其有序段按段号交换到对应的处理器中(8)归并排序：各处理器对接收到的元素进行归并排序end.3例6.1n=27，p=3PSRS排序过程4633841597618940693614917263993
3、48207227325884975354211266154403621129391724846391514978472585333322720978969(d)采样排序：(c)正则采样：(b)局部排序：(a)均匀划分：(e)选择主元：63972124069203372612203339406972723369(f)主元划分：(g)全局交换：(h)归并排序：6615440362112939172484639151497725853333227209789696534846403936333227212015141297979391898472726961585465
4、44036484639333227202112151497847297899391725853696146.1.2方根划分技术方根划分：取每第i(i=1，2，…)个元素作为划分元素将序列分成若干段，然后分段处理之划分方法n个元素A[1..n]分成A[(i-1)n^(1/2)+1..in^(1/2)]，i=1~n^(1/2)算法6.2SIMD-CREW模型上的Valiant归并(1975年发表)//有序组A[1..p]、B[1..q],(假设p<=q),处理器数begin(1)方根划分:A,B分别按；(2)段间比较:A划分元与B划分元比较(至多对)，确定A划分元应插
5、入B中的区段；(3)段内比较:A划分元与B相应段内元素进行比较，并插入适当的位置；(4)递归归并:B按插入的A划分元重新分段，与A相应段(A除去原划分元)构成了成对的段组，对每对段组递归执行(1)~(3)，直至A组为0时，递归结束;各组仍按分配处理器；end.6.1.2方根划分技术6例:A={1,3,6,8,11,13}p=6;B={2,4,5,7,10,12,14},q=7=3,=3A={1,3,6*,8,11,13*}B={2,4,5*,7,10,12*,14},B’={2,4,5,6*,7,1012,13*,14}A11={1,3},A12={8,11},A
6、13={}B11={2,4,5},B12={7,1012},B13={14}A11={1,3*},A12={8,11*},B11={2,4*,5},B12={7,10*,12},B11’={2,3*,4,5},B12’={7,10,11*,12},A111={1},A112={}A121={8},A122={}B111={2},B112={4,5}B121={7,10},B122={12}A111={1*}A121={8*}B111={2*}B121={7,10*}B111’={1*,2*}B121’={7,8*,10*}A1111={},A1112={}A121
7、1={},A1212={}B1111={},B1111={}B1211={7},A1212={}786.1划分设计技术6.1.1均匀划分技术6.1.2方根划分技术6.1.3对数划分技术6.1.4功能划分技术6.1.3对数划分技术划分方法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,7,10,12,
8、15,18
