并行计算-多媒体课件-并行算法设计与分析-ch05Sorting and Selecting in Asynchronous
Title,This is our 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bullet,This is our next 1st Level Bullet,This is our 2nd level bullet,This is our 3rd level bullet,*,Y.Xu Copyright USTC,Parallel Algorithms,*,/Ch5,Parallel Algorithms,Chapter,5,Sorting and Selecting,in As,ynchron,ous,2024/10/15,Y.Xu Copyright USTC,主要内容,5.1 MIMD-CREW,模型上的异步枚举排序算法,5.2 MIMD-TC,模型上的异步快排序算法,5.3,分布式,k-,选择算法,2024/10/15,Y.Xu Copyright USTC,5.1 MIMD-CREW,模型上的异步枚举排序算法,5.1.1 MIMD,异步,算法的基本框架,5.1.2,异步枚举排序算法,5.1.3,示例,5.1.4,时间分析,2024/10/15,Y.Xu Copyright USTC,5.1.1 MIMD,异步,算法的基本框架,开始时所有处理器空闲，用某个开始算法，,产生一些过程或进程,(,算法的一段,),，进入进程,等待队列；,若有空闲的机器，分配进程；进程执行完之后，,机器进入等待；,若无等待进程，机器空闲，排队进入等待状态。
注：,SIMD,每个时刻各处理器执行的操作相同,2024/10/15,Y.Xu Copyright USTC,5.1.2,异步枚举排序算法,1.,输入待排序数组,X1.n,，输出已排序数组,T1.n,2.,算法：,MIMD-CREW,枚举排序,begin (2.2)for j=1 to n do,(1)for i=1 to n do if,Xi,Xj,then k=k+1,create process i else if(,Xi,=,Xj,and ij)then k=k+1,end for end if,(2)process i:(2.3)TK+1=,Xi,(2.1)k=0 end,注：算法生成,n,个进程，第,i,个进程计算,X,中比,x,i,小的元素数,k,，将,x,i,置于,SM,数组,Tk+1,，各进程间无通讯要求，可互相独立完成2024/10/15,Y.Xu Copyright USTC,5.1.3,异步枚举排序算法示例,输入,X=8,6,6,7,9,，,p(n,)=2,，,P1,生成,5,个进程，设进程调度按,FIFO,，,P1,与,P2,首先执行进程,1,和进程,2,(1),进程内的运算,(,假定各操作时间相同，,X,数组已在本地,),k=0,X(i,),Xj,X(i,)=,Xj,ij,k=k+1,Tk+1=,Xi,(2),进程,1,：,(3),进程,2,：,1+3+3+3+3+3+1=17,类似地，进程,3(18),，进程,4(13),，进程,5(15),2024/10/15,Y.Xu Copyright USTC,5.1.4,异步枚举排序算法的时间分析,1.,假定：第,(1),步之前无任何进程启动；,可在常数时间内解决读冲突；,不考虑进程间的调度时间,2.MIMD-,异步枚举排序算法时间,n,个进程：每个进程时间,O(n,),2024/10/15,Y.Xu Copyright USTC,主要内容,5.1 MIMD-CREW,模型上的异步枚举排序算法,5.2 MIMD-TC,模型上的异步快排序算法,5.3,分布式,k-,选择算法,2024/10/15,Y.Xu Copyright USTC,5.2 MIMD-TC,模型上的异步快排序算法,5.2.1 SISD,上的,快排序,算法,5.2.2 SIMD,-CRCW,上的快排序算法,5.2.3,MIMD-TC,模型上的异步快排序算法,2024/10/15,Y.Xu Copyright USTC,5.2.1 SISD,上的,快排序,算法,Procedure QUICKSORT(A,q,r),/,输入无序序列,(,A,q,A,r,);,输出有序序列,(,A,q,A,r,),begin,if qr then,(1)x=,A,q,(2)s=q,(3)for i=q+1 to r do,if,A,i,x,then,(,i)s,=s+1,(,ii)swap(,A,s,A,i,),end if,(4)swap(,A,q,A,s,),(5),QUICKSORT(A,q,s),(6),QUICKSORT(A,s+1,r),end,2024/10/15,Y.Xu Copyright USTC,5.2.2 SIMD,-CRCW,上的快排序算法,1.,算法说明,(1)SIMD,-CRCW,上的快排序算法的核心是构造二叉排序树。
2),排序树的树根为,root,，左孩子为,Lcroot,，右孩子为,Rcroot,(3)SM,变量,root,Lc1.n,Rc1.n,及待排序数组,A1.n,(4)n,个处理器,Pi,存有,Ai,(5),得到二叉排序树后，只要中序遍历即可得到排序序列,(6),二叉排序树如下：,2024/10/15,Y.Xu Copyright USTC,2.SIMD-CRCW,上的快排序二叉树构造算法,输入：,A1.n,到,SM,，,n,个处理器，并且,Ai,保存在,P,i,的,LM,中,输出：二叉排序树,root,Lc1.n,Rc1.n,在,SM,中,begin,(1)for each P,i,par-do,(1.1)root=i,(1.2)f,i,=root,(1.3)Lc,i,=,Rc,i,=n+1,end for,(2)repeat for each P,i,i,f,i,par-do,if(A,i,A,fi,)or(A,i,=,A,fi,and i,f,i,)then,(2.1),Lc,fi,=i,(2.2)if i=,Lc,fi,then exit else,f,i,=,L,c,fi,end if,else,(2.3)R,c,fi,=i,(2.4)if i=,R,c,fi,then exit else,f,i,=,R,c,fi,end if,end if,end repeat,end,5.2.2 SIMD,-CRCW,上的快排序算法,/Pi,将处理器号,i,并发写入,SM,变量,root,，,root,的值是不确定的,/Pi,并发读入,root,到,LM,变量,fi,中,/,Lci,和,Rci,初始化，使得不指向任何处理器,/A,i,是,LM,变量,A,fi,是,SM,变量,;(A,i,=,A,fi,and i0,的最大整数,f,，在根的第,f,个子树中找第,j,个元素,递归地找下去；,将划分元素,m,根结点,所有结点,每个进程,i,将,B,i,分成,BL,i,BE,i,BG,i,计算,依据,m,|BL|,|BE|,|BG|,之间的关系,(,同算法,1),，确定下一步的调用,需加上：将信息播送到所有结点,根据,B,k,做递归调用,2024/10/15,Y.Xu Copyright USTC,5.3.3,确定,k-,选择算法,1.,SISD,上的确定,k-,选择算法,2.,分布式确定,k-,选择算法,2024/10/15,Y.Xu Copyright USTC,5.3.3,确定,k-,选择算法,1.,SISD,上的确定,k-,选择算法,算法,3:,|B|,较小，用排序求；,将,B,分成每,5,个一组；,求每组的中值,:,中值集,M;,求,M,的中值,m,划分元；,同算法,1,中,；,同算法,1,中,；,2024/10/15,Y.Xu Copyright USTC,5.3.3,确定,k-,选择算法,2.,分布式确定,k-,选择算法,算法,4,：,求,|B|,当,|B|,足够小时，送入根结点，排序求,k-,元素,;,每个进程按,5,个元素一组分组，每个结点从其子结点,接收零头，每,5,个一组分组，再把零头送往父结点；,局部求,5,个元素的中值；,以,M,为输入，递归调用求,M,的中值,m;,同算法,1,中的,；,2024/10/15,Y.Xu Copyright USTC,End of Chapter 5,2024/10/15,Y.Xu Copyright USTC,。
