并行算法的设计与分析(5).ppt

1、并行算法的设计与分析,第5章 排序与选择算法,5.4 AKL的并行k-选择算法,5.4.1 问题描述与算法原理 k-选择问题 任意给定n个数据序列S=x1,x2,xn ，从中选出第k小（大）的元素，kn/2。 串行k-选择算法（参见苏德富、钟诚，计算机算法设计与分析，第2版，电子工业出版社，2005）的时间复杂度为O(n) k-选择并行算法原理 思想：划分-中值-筛选-递归 (1) 将S 划分为若干组，每组分配给一个处理器处理。 (2) 并行求取各组的中值，得到一个由中值元素组成的序列（中值序列）。 (3) 求中值序列的中值m（中值之中值）。 (4) 将S划分成分别小于、等于、大于m的三个子序

2、列S1，S2，S3。 (5) 以一定的规则判断序列S1，S2，S3的长度与k的关系，以在S2中确定出第k小（大）元素，或者继续在相应的子序列（ S1或S3 ）中重复步骤(1)(5)直到找出第k小（大）元素为止。,5.4.2 并行k-选择算法,1. SIMD-SM上的数据播送算法 解决N个处理器并行读共享存储器SM中同一个单元数据m的问题。 Procedure Broadcast(m, N, B) / B为SM中长度为N的共享（中间）数组 Begin / 二叉树并行通信技术 (1) P1将SM中的m读入到自己的LM中，然后将它写入SM中的B1单元； (2) for i=0 to log N-1

3、do / i为逻辑二叉树的层号 for j=2i+1 to 2 i+1 do in parallel / 逐层并行播送数据，第i层有个2i结点 Pj将SM中Bj-2i读入到自己LM中，然后将它写入SM的Bj单元； End. 时间复杂度：O(logN) 示例：N=8, m=101 SM: m B1 B2 B3 B4 B5 B6 B7 B8 101 101 101 101 101 101 101 101 101 P1 P2 P3 P4 P5 P6 P7 P8 LM: 101 101 101 101 101 101 101 101 迭代次数： i=0 i=1 i=1 i=2 i=2 i=2 i=2,

4、5.4.2 并行k-选择算法,2. SIMD-SM上并行求N个数据的所有前缀和算法 初始时， Pj 存储第i 个前缀和初值Si=xi。 Procedure Allsums(S,N) Begin / 二叉树并行求前缀和技术 for j=0 to log N-1 do for i=2j+1 to N do in parallel Pi从SM中读入Si- 2j并计算Si =Si +Si- 2j ； End. 时间复杂度：O(logN) 示例：N=8, S=8,7,6,5,4,3,2,1，求S的所有前缀和 SM: S1 S2 S3 S4 S5 S6 S7 S8 8 7 6 5 4 3 2 1 j=0:

5、 15 13 11 9 7 5 3 20个前缀和求出 j=1: 21 26 22 18 14 10 21个前缀和求出 j=2: 30 33 35 36 22个前缀和求出 P1 P2 P3 P4 P5 P6 P7 P8,5.4.2 并行k-选择算法,3. SIMD-EREW上并行k-选择算法 Procedure PARALLEL SELECT(k,S) / t(n) / 处理器数目=n1- Begin (1) if |S|3 then 使用一个处理器返回第k小元素 else 将S分成n1-段Si(i=1n1-)， Pi处理段Si的n个元素；/ O(n) (2) for i=1 to n1- pa

6、r-do / O(n) Pi执行串行k-选择算法找出Si中的中值mi，并写入SM中的Mi； (3) 调用PARALLEL SELECT( , M)找出中值序列M的中值m / t(n1-) 并播送m到所有处理器； / 调用数据播送算法， O(logn1-) (4) for i=1 to n1- par-do / O(n) Pi求出Si中小于、等于和大于m的元素集Si1,Si2,Si3并求出这些元素集的元素数目|Si1|，|Si2|，|Si3|; (5) 求出S中小于、等于和大于m的元素集S1，S2，S3; / O(n) (6) if k|S1| then PARALLEL SELECT(k, S

7、1); / 第k小元素在S1中，筛去S2和S3 ； t(3n/4) else if k|S1|+|S2| then return(m); / 第k小元素在S2中 else PARALLEL SELECT(k-|S1|-|S2|, S3); /第k小元素在S3中，筛去S1和S2 End / 调用求前缀和算法用O(logn1-)时间由|Si1|,|Si2|和|Si3|(i=1 n1- )可求出|S1| , |S2|和 |S3|,5.4.2 并行k-选择算法,4. 算法复杂度 设算法的时间复杂度为t(n)。 第(1)步最多需时间O(n)；第(2)步最多需时间O(n)；第(3)步递归调用算法最多需时间

8、t(n1-)，播送中值m所需时间为O(logn1-); 第(4)步最多需时间O(n)；第(5)步最多需时间O(n) 。 执行前缀和算法求出|S1| , |S2|和 |S3|所需时间为O(logn1-) 。 因为m是M的中值，所以可判定M中至少有|M|/2= n1-/2个元素不会大于m。M中每个元素最多小于它对应（所在）子序列的n /2个元素。 按照组合数学组合原理的加法规则和乘法规则，有|S1| n/2 + n1-/2 * n /2=3n/4 。 同理， |S3| 3n/4 。 因此，第(6)步递归调用算法最多需时间t(3n/4) 。 算法总的时间 t(n)=O(logn1-)+O(n)+ t

9、(n1-)+t(3n/4) =t(n)=O(n)， p(n)=n1- =c(n)=t(n)p(n)=O(n), 代价最优 =Sp(n)=O(n)/O(n)=O(n1- ), 线性加速 Remark: 若采用CREW、CRCW模型, 则算法不需要调用数据播送算法，但它不影响算法的复杂度。,5.4.2 并行k-选择算法,5. 示例,P1,P2,P3,P4,P5,处理器数,中值的中值,6th在S1中，对S1再划分：,6th在S2中,5.5 Valiant并行归并与排序,5.5.1 问题描述与Valiant归并原理 1.问题描述 将两个有序序列A、B归并成一个有序序列C=A+B ，p=|A|, q=|

10、B|, pq， |C| = p+ q 。 2.Valiant归并原理 思想：并行“分组（划分）、挑选、插入、递归”。 分组策略：方根划分方法的应用。,5.5.2 Valiant并行归并算法,3. 算法描述 算法5.4 SIMD-CREW模型上的Valiant归并 / 有序组A1.p，B1.q, pq, 处理器数k=|(pq)1/2 Begin (1) 方根划分: A, B中位置分别为ip1/2 |和j q1/2 |的元素打*（它们将A 和B分成若干段( i=1- |p1/2 ,j=1- |q1/2 )； (2) 段间比较: A的划分元素与B的划分元素 (至多|p1/2 |q1/2 对)并行 比

11、较，结果可确定出A的划分元应插入到B中的区段； (3) 段内比较: A的划分元（ |p1/2 个）与其要插入的B相应段内非打* 元素（q1/2 | -1个）进行比较，并插入到B 段内适当的位置。这些 插入位置将B重新划分成若干段。 (4) 递归: B的新分段与A相应段(A中除去原划分元)构成了新的成对的段 组， 对每对段组（并行）递归执行(1)(4)，直至A段组为空时，递归 结束。 在递归过程中，各组仍按k=|(pq)1/2 分配处理器； End.,4. Valiant归并算法复杂度,5.5.2 Valiant并行归并算法,示例：p=8, q=9, A=1,3,8,9,11,13,15,16;

12、 B=2,4,5,6,7,10,12,14,17 （1）A: 1, 3, 8, 9, 11, 13, 15, 16 / 大红色表示打* B: 2, 4, 5, 6, 7, 10, 12, 14, 17 （2）A: 1, 3, 8, 9, 11, 13, 15, 16 B: 2, 4, 5, 6, 7, 10, 12, 14, 17 (3）A: 1, 3, 9, 11, 15, 16 B: 2, 4, 5, 6, 7, 8, 10, 12, 13, 14, 17 (4) A: 1, 3, 9, 11, 15, 16 B: 2, 4, 5, 6, 7, 8, 10, 12, 13, 14, 17

13、(5) A: 1, 3, 9, 11, 15, 16 B: 2, 4, 5, 6, 7, 8, 10, 12, 13, 14, 17 (6) A: 1, 9, 15 B: 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14,16, 17 (7) A: 1, 9, 15 B: 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 16, 17 (8) A: B: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,15, 16, 17,5.5.3 Valiant并行排序算法,设原始数据序列为X=x1,

14、x2,xi,xn，n=2m。 Valiant并行排序的思想：初始时，将X中的n个元素分别看作是n个长度分别为1的有序序列，然后不断并行地调用Valiant归并算法对这些有序子序列进行归并，经过m=logn步之后，就可以将它们归并成完整的长度为n的有序序列。 算法5.6 SIMD-CREW上Valiant并行排序 Begin for i=1 to logn do for j=1 to n/2i do in parallel 调用Valiant归并算法将两个长度分别为2i-1的有序子序列归并成长度2i 的有序序列 endfor endfor End. 算法复杂度：t(n)=i=1 logn O(l

15、oglog2i ) =i=1 logn O(logi)=O(logn*loglogn),5.10 MIMD-TC（逻辑树机）模型上异步并行Quick快排序算法,5.10.1 SISD上的Quick排序串行算法 Algorithm Quicksort(A, q, r) / 输入无序序列(Aq,Ar); 输出有序序列(Aq,Ar) begin if qr then (1) x= Aq ； (2) s=q ； (3) for i=q+1 to r do if Aix then (i) s=s+1； (ii) swap(As, Ai) ； / 交换As,和 Ai end if (4) swap(Aq,

16、 As) ； (5) Quicksort(A, q, s) ； / 递归调用 (6) Quicksort(A, s+1, r) ； / 递归调用 end,5.10 MIMD-TC模型上异步并行Quick快排序算法,5.10.2 MIMD-TC上异步并行Quick排序算法 1. 算法思想 并行“寻找中值、中值定位、序列划分、递归” 2.算法描述 输入数组数组X1.n, Qi为X的子数组，qi为Qi中第1个元素的首地址，|Qi|=si, R是存放(qi,si)的数组 Begin 主进程Process0： (4) 进程Processi: / 对Qi进行快排序 (1) Q1=X; (4.1) (qi,

17、 si)=Ri; / 取Qi首地址和Qi的大小 (2) R1=(q1, n); (4.2) if si2 then 直接排序Qi (3) 生成进程Process1 else (i) 调用串行k-选择算法求Qi中值m; / O(si) (ii) 将m定位在X的最终排序位置上; / O(1) (iii) 将Qi划分成小于、大于m的两子序列Q2i和Q2i+1; / O(si) (iv) R2i=(q2i, s2i) ; R2i+1=(q2i+1, s2i+1) ; / O(1) (v) 生成进程Process2i和进程Process2i+1 / O(1) end if End,5.10.2 MIMD

18、-TC模型上异步并行Quick快排序算法,3.示例：X=10, 3, 7, 15, 2, 4, 11, 1, 12, 6, 8, 13, 9, 16, 14, 5, n=16, p(n)=4的执行过程 按中序遍历此逻辑二叉树得到排序结果：1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 Remark: 第0层第2层可以由4个处理器并行求解，而第3层以上一个处理器需要顺序处理多个进程。,5.10.2 MIMD-TC模型上异步并行Quick快排序算法,4.算法复杂度 设n=2k ，k=logn, p=2l 。处理器调用串行k-选择算法选取Qi中值的时间为O(si)，将Qi划分成Q2i和Q2i+1所需的时间为O(si) 。 算法在执行过程中相当于动态生成一棵逻辑二叉树，第 i 次动态生成的进程数为2i ,i=0k-1。所以，在第0（树根）层