并行計算-多媒體課件-并行算法設計與分析-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,異步,算法的基本框架,開始時所有處理器空閑，用某個開始算法，,產生一些過程或進程,(,算法的一段,),，進入進程,等待隊列；,若有空閑的機器，分配進程；進程執(zhí)行完之后，,機器進入等待；,若無等待進程，機器空閑，排隊進入等待狀態(tài)。,注：,SIMD,每個時刻各處理器執(zhí)行的操作相同,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,首先執(zhí)行進程,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,并發(fā)寫入,SM,變量,root,，,root,的值是不確定的,/Pi,并發(fā)讀入,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,