并行计算-多媒体课件-并行算法设计与分析-ch05 Sorting and Selecting in Asynchronous.ppt

《并行计算-多媒体课件-并行算法设计与分析-ch05 Sorting and Selecting in Asynchronous.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、thenk=k+1createprocessielseif(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/7/21Y.XuCopyrightUSTC5.1.3异步枚举排序算法示例输入X={8,6,6,7,9}，p(n)=2，P1生成5个进程，设进程调度按FIFO，P1与P2首先执行进程1和进程2(

4、1)进程内的运算(假定各操作时间相同，X数组已在本地)k=0,X(i)>X[j],X(i)=X[j],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/7/21Y.XuCopyrightUSTC5.1.4异步枚举排序算法的时间分析1.假定：第(1)步之前无任何进程启动；可在常数时间内解决读冲突；不考虑进程间的调度时间2.MIMD-异步枚举排序算法时间n个进程：每个进程时间O(n)2021/7/21Y.XuCopyrigh

5、tUSTC主要内容5.1MIMD-CREW模型上的异步枚举排序算法5.2MIMD-TC模型上的异步快排序算法5.3分布式k-选择算法2021/7/21Y.XuCopyrightUSTC5.2MIMD-TC模型上的异步快排序算法5.2.1SISD上的快排序算法5.2.2SIMD-CRCW上的快排序算法5.2.3MIMD-TC模型上的异步快排序算法2021/7/21Y.XuCopyrightUSTC5.2.1SISD上的快排序算法ProcedureQUICKSORT(A,q,r)//输入无序序列(Aq,…,Ar);输出有序序列(Aq,…,

6、Ar)beginifq

7、变量root,Lc[1..n],Rc[1..n],及待排序数组A[1..n](4)n个处理器Pi存有A[i](5)得到二叉排序树后，只要中序遍历即可得到排序序列(6)二叉排序树如下：2021/7/21Y.XuCopyrightUSTC2.SIMD-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+

8、1endfor(2)repeatforeachPi,i<>fipar-doif(Ai