并行計(jì)算-多媒體課件-并行算法設(shè)計(jì)與分析-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,主要內(nèi)容,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,時(shí)間分析,2024/10/15,Y.Xu Copyright USTC,5.1.1 MIMD,異步,算法的基本框架,開(kāi)始時(shí)所有處理器空閑，用某個(gè)開(kāi)始算法，,產(chǎn)生一些過(guò)程或進(jìn)程,(,算法的一段,),，進(jìn)入進(jìn)程,等待隊(duì)列；,若有空閑的機(jī)器，分配進(jìn)程；進(jìn)程執(zhí)行完之后，,機(jī)器進(jìn)入等待；,若無(wú)等待進(jìn)程，機(jī)器空閑，排隊(duì)進(jìn)入等待狀態(tài)。,注：,SIMD,每個(gè)時(shí)刻各處理器執(zhí)行的操作相同,2024/10/15,Y.Xu Copyright USTC,5.1.2,異步枚舉排序算法,1.,輸入待排序數(shù)組,X1.n,，輸出已排序數(shù)組,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,個(gè)進(jìn)程，第,i,個(gè)進(jìn)程計(jì)算,X,中比,x,i,小的元素?cái)?shù),k,，將,x,i,置于,SM,數(shù)組,Tk+1,，各進(jìn)程間無(wú)通訊要求，可互相獨(dú)立完成。,2024/10/15,Y.Xu Copyright USTC,5.1.3,異步枚舉排序算法示例,輸入,X=8,6,6,7,9,，,p(n,)=2,，,P1,生成,5,個(gè)進(jìn)程，設(shè)進(jìn)程調(diào)度按,FIFO,，,P1,與,P2,首先執(zhí)行進(jìn)程,1,和進(jìn)程,2,(1),進(jìn)程內(nèi)的運(yùn)算,(,假定各操作時(shí)間相同，,X,數(shù)組已在本地,),k=0,X(i,),Xj,X(i,)=,Xj,ij,k=k+1,Tk+1=,Xi,(2),進(jìn)程,1,：,(3),進(jìn)程,2,：,1+3+3+3+3+3+1=17,類(lèi)似地，進(jìn)程,3(18),，進(jìn)程,4(13),，進(jìn)程,5(15),2024/10/15,Y.Xu Copyright USTC,5.1.4,異步枚舉排序算法的時(shí)間分析,1.,假定：第,(1),步之前無(wú)任何進(jìn)程啟動(dòng)；,可在常數(shù)時(shí)間內(nèi)解決讀沖突；,不考慮進(jìn)程間的調(diào)度時(shí)間,2.MIMD-,異步枚舉排序算法時(shí)間,n,個(gè)進(jìn)程：每個(gè)進(jìn)程時(shí)間,O(n,),2024/10/15,Y.Xu Copyright USTC,主要內(nèi)容,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),/,輸入無(wú)序序列,(,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.,算法說(shuō)明,(1)SIMD,-CRCW,上的快排序算法的核心是構(gòu)造二叉排序樹(shù)。,(2),排序樹(shù)的樹(shù)根為,root,，左孩子為,Lcroot,，右孩子為,Rcroot,(3)SM,變量,root,Lc1.n,Rc1.n,及待排序數(shù)組,A1.n,(4)n,個(gè)處理器,Pi,存有,Ai,(5),得到二叉排序樹(shù)后，只要中序遍歷即可得到排序序列,(6),二叉排序樹(shù)如下：,2024/10/15,Y.Xu Copyright USTC,2.SIMD-CRCW,上的快排序二叉樹(shù)構(gòu)造算法,輸入：,A1.n,到,SM,，,n,個(gè)處理器，并且,Ai,保存在,P,i,的,LM,中,輸出：二叉排序樹(shù),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,將處理器號(hào),i,并發(fā)寫(xiě)入,SM,變量,root,，,root,的值是不確定的,/Pi,并發(fā)讀入,root,到,LM,變量,fi,中,/,Lci,和,Rci,初始化，使得不指向任何處理器,/A,i,是,LM,變量,A,fi,是,SM,變量,;(A,i,=,A,fi,and i0,的最大整數(shù),f,，在根的第,f,個(gè)子樹(shù)中找第,j,個(gè)元素,遞歸地找下去；,將劃分元素,m,根結(jié)點(diǎn),所有結(jié)點(diǎn),每個(gè)進(jìn)程,i,將,B,i,分成,BL,i,BE,i,BG,i,計(jì)算,依據(jù),m,|BL|,|BE|,|BG|,之間的關(guān)系,(,同算法,1),，確定下一步的調(diào)用,需加上：將信息播送到所有結(jié)點(diǎn),根據(jù),B,k,做遞歸調(diào)用,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,個(gè)一組；,求每組的中值,:,中值集,M;,求,M,的中值,m,劃分元；,同算法,1,中,；,同算法,1,中,；,2024/10/15,Y.Xu Copyright USTC,5.3.3,確定,k-,選擇算法,2.,分布式確定,k-,選擇算法,算法,4,：,求,|B|,當(dāng),|B|,足夠小時(shí)，送入根結(jié)點(diǎn)，排序求,k-,元素,;,每個(gè)進(jìn)程按,5,個(gè)元素一組分組，每個(gè)結(jié)點(diǎn)從其子結(jié)點(diǎn),接收零頭，每,5,個(gè)一組分組，再把零頭送往父結(jié)點(diǎn)；,局部求,5,個(gè)元素的中值；,以,M,為輸入，遞歸調(diào)用求,M,的中值,m;,同算法,1,中的,；,2024/10/15,Y.Xu Copyright USTC,End of Chapter 5,2024/10/15,Y.Xu Copyright USTC,