《并行算法的设计与分析》5

《《并行算法的设计与分析》5》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Y.XuCopyrightUSTC2021/6/9ParallelAlgorithmsChapter5SortingandSelectinginAsynchronous2021/6/9Y.XuCopyrightUSTC主要内容5.1MIMD-CREW模型上的异步枚举排序算法5.2MIMD-TC模型上的异步快排序算法5.3分布式k-选择算法2021/6/9Y.XuCopyrightUSTC5.1MIMD-CREW模型上的异步枚举排序算法5.1.1MIMD异步算法的基本框架5.1.2异步枚举排序算法5.1.3示例5.1.4时间分析2021/6/9Y.XuCopyrightUSTC5.

2、1.1MIMD异步算法的基本框架①开始时所有处理器空闲，用某个开始算法，产生一些过程或进程(算法的一段)，进入进程等待队列；②若有空闲的机器，分配进程；进程执行完之后，机器进入等待；③若无等待进程，机器空闲，排队进入等待状态。注：SIMD每个时刻各处理器执行的操作相同2021/6/9Y.XuCopyrightUSTC5.1.2异步枚举排序算法1.输入待排序数组X[1..n]，输出已排序数组T[1..n]。2.算法：MIMD-CREW枚举排序begin(2.2)forj=1tondo(1)fori=1tondoifX[i]>X[j]thenk=k+1createprocessiel

3、seif(X[i]=X[j]andi>j)thenk=k+1endforendif(2)processi:(2.3)T[K+1]=X[i](2.1)k=0end注：算法生成n个进程，第i个进程计算X中比xi小的元素数k，将xi置于SM数组T[k+1]，各进程间无通讯要求，可互相独立完成。2021/6/9Y.XuCopyrightUSTC5.1.3异步枚举排序算法示例输入X={8,6,6,7,9}，p(n)=2，P1生成5个进程，设进程调度按FIFO，P1与P2首先执行进程1和进程2(1)进程内的运算(假定各操作时间相同，X数组已在本地)k=0,X(i)>X[j],X(i)=X[j

4、],i>j,k=k+1,T[k+1]=X[i](2)进程1：(3)进程2：1+3+3+3+3+3+1=17类似地，进程3(18)，进程4(13)，进程5(15)2021/6/9Y.XuCopyrightUSTC5.1.4异步枚举排序算法的时间分析1.假定：第(1)步之前无任何进程启动；可在常数时间内解决读冲突；不考虑进程间的调度时间2.MIMD-异步枚举排序算法时间n个进程：每个进程时间O(n)2021/6/9Y.XuCopyrightUSTC主要内容5.1MIMD-CREW模型上的异步枚举排序算法5.2MIMD-TC模型上的异步快排序算法5.3分布式k-选择算法2021/6/9

5、Y.XuCopyrightUSTC5.2MIMD-TC模型上的异步快排序算法5.2.1SISD上的快排序算法5.2.2SIMD-CRCW上的快排序算法5.2.3MIMD-TC模型上的异步快排序算法2021/6/9Y.XuCopyrightUSTC5.2.1SISD上的快排序算法ProcedureQUICKSORT(A,q,r)//输入无序序列(Aq,…,Ar);输出有序序列(Aq,…,Ar)beginifq

6、5)QUICKSORT(A,q,s)(6)QUICKSORT(A,s+1,r)end2021/6/9Y.XuCopyrightUSTC5.2.2SIMD-CRCW上的快排序算法1.算法说明(1)SIMD-CRCW上的快排序算法的核心是构造二叉排序树。(2)排序树的树根为root，左孩子为Lc[root]，右孩子为Rc[root](3)SM变量root,Lc[1..n],Rc[1..n],及待排序数组A[1..n](4)n个处理器Pi存有A[i](5)得到二叉排序树后，只要中序遍历即可得到排序序列(6)二叉排序树如下：2021/6/9Y.XuCopyrightUSTC2.SIMD-

7、CRCW上的快排序二叉树构造算法输入：A[1..n]到SM，n个处理器，并且A[i]保存在Pi的LM中输出：二叉排序树root,Lc[1..n],Rc[1..n]在SM中begin(1)foreachPipar-do(1.1)root=i(1.2)fi=root(1.3)Lci=Rci=n+1endfor(2)repeatforeachPi,i<>fipar-doif(Ai