(完整word版)并行計算實驗快速排序的并行算法

1、3.1 實驗?zāi)康呐c要求1 、熟悉快速排序的串行算法2、熟悉快速排序的并行算法3、實現(xiàn)快速排序的并行算法3.2 實驗環(huán)境及軟件單臺或聯(lián)網(wǎng)的多臺 PC機，LinUX操作系統(tǒng)，MPI系統(tǒng)。3.3 實驗內(nèi)容1、快速排序的基本思想2、單處理機上快速排序算法3、快速排序算法的性能4、快速排序算法并行化5、描述了使用2m個處理器完成對n個輸入數(shù)據(jù)排序的并行算法。6、 在最優(yōu)的情況下并行算法形成一個高度為log n的排序樹7、完成快速排序的并行實現(xiàn)的流程圖8、完成快速排序的并行算法的實現(xiàn)3.4 實驗步驟3.4.1 、 快速排序( Quick Sort )是一種最基本的排序算法，它的基本思想是：在當(dāng)前無序區(qū) R

2、1， n 中取一個記錄作為比較的“基準”(一般取第一個、最后一個或中間位置的元素) ，用此基準將當(dāng) 前的無序區(qū)R1 , n劃分成左右兩個無序的子區(qū)R1 , i-1和Ri , n(1 i n)，且左邊的無序子區(qū)中記錄的所有關(guān)鍵字均小于等于基準的關(guān)鍵字， 右邊的無序子區(qū)中記錄的所有關(guān)鍵字均大于等于基準 的關(guān)鍵字；當(dāng) R1, i-1和Ri , n非空時，分別對它們重復(fù)上述的劃分過程，直到所有的無序子區(qū) 中的記錄均排好序為止。3.4.2、輸入：輸出：單處理機上快速排序算法無序數(shù)組 data1,n有序數(shù)組 data1,nBegincall procedure quicksort(data,1,n) En

3、d procedure quicksort(data,i,j) Begin(1) if (ij) then(1.1) r = partition(data,i,j)(1.2) quicksort(data,i,r-1);(1.3) quicksort(data,r+1,j); end ifEndpivo=data l i=k-1 for j=k to l-1 doprocedure partition(data,k, l) Begin(1)(2) if dataj pivo theni=i+1exchange datai and dataj end if end for(4) exchange

4、datai+1 and data l(5) return i+1 End3.4.3 、快速排序算法的性能主要決定于輸入數(shù)組的劃分是否均衡，而這與基準元素的選擇密切相關(guān)。在最壞的情況下，劃分的結(jié)果是一邊有 n-1 個元素，而另一邊有 0 個元素(除去被選中的基準元素) 。 如果每次遞歸排序中的劃分都產(chǎn)生這種極度的不平衡，那么整個算法的復(fù)雜度將是 (n2)。在最好的情況下，每次劃分都使得輸入數(shù)組平均分為兩半，那么算法的復(fù)雜度為0(nlog n)。在一般的情況下該算法仍能保持 0( nlogn)的復(fù)雜度，只不過其具有更高的常數(shù)因子。3.4.4 、快速排序算法并行化的一個簡單思想是，對每次劃分過后所得

5、到的兩個序列分別使用兩個處 理器完成遞歸排序。例如對一個長為 n 的序列，首先劃分得到兩個長為 n/2 的序列，將其交給兩個處 理器分別處理；而后進一步劃分得到四個長為 n/4 的序列，再分別交給四個處理器處理；如此遞歸下 去最終得到排序好的序列。 當(dāng)然這里舉的是理想的劃分情況， 如果劃分步驟不能達到平均分配的目的， 那么排序的效率會相對較差。345、描述了使用2m個處理器完成對n個輸入數(shù)據(jù)排序的并行算法。 快速排序并行算法輸入： 無序數(shù)組 data1,n ，使用的處理器個數(shù) 2m輸出： 有序數(shù)組 data1,nBeginpara_quicksort (data,1,n,m,0)End pro

6、cedure para_quicksort (data,i,j,m,id)Begin(j-i) k or m=0 thenPid call quicksort (data,i,j)(1) if(1.1)Pid: r= patrition( data,i,j)P id send datar+1,m-1 to Pid+2m-1 para_quicksort(data,i,r-1,m-1,id) para_quicksort(data,r+1,j,m-1,id+2m-1) Pid+2m-1 send datar+1,m-1 back to Pid end ifelse(1.2)(1.3)(1.4)(

7、1.5)(1.6)End346、在最優(yōu)的情況下該并行算法形成一個高度為log n的排序樹，其計算復(fù)雜度為0(n),通信復(fù)雜度也為0(n)。同串行算法一樣，在最壞情況下其計算復(fù)雜度降為0(n2)。正常情況下該算法的計算復(fù)雜度也為 0 (n) ，只不過具有更高的常數(shù)因子。347、完成快速排序的并行實現(xiàn)的流程圖初始化MP l_l nit (&argc, &argv);MP I_Comm_ra nk(M PI_COMM_WORLD,&M yID);MP I_Comm_size(M PI_COMM_WORLD,&SumlD);*處理機(MylD=0)獲取待排序數(shù)組的長度動態(tài)生成待排序序列從根處理器將數(shù)據(jù)

8、序列廣播到其他處理器MP I_Bcast*調(diào)度執(zhí)行排序 para_QuickSort(data,0,DataSize-1,m,0,MylD);id+ex p2(m-1)由第id號處理器劃分數(shù)據(jù)，并將后一部分數(shù)據(jù)發(fā)送到處理器(1.2) Pid: r=patrition(data,i,j)r=P artiti on( data,start,e nd);4(1.3)Pid send datar+1,e nd to P (id+2m-1)MP l_Se nd(&MyLe ngth,1, MP l_INT,id+ex p2(m-1),MylD, MP l_COMM_WORLD);MP I_Se nd(d

9、ata+葉1,MyLe ngth, MP I_INT,id+ex p2(m-1),MylD, MP I_COMM_WORLD);J-處理器id+exp2(m-1)接受處理器id發(fā)送的消息遞歸調(diào)用并行排序用2m-1個處理器對start-(r-1)的數(shù)據(jù)進行遞歸排序用2m-1個處理器對(r+1)-end的數(shù)據(jù)進行遞歸排序?qū)⑴判蚝玫臄?shù)據(jù)由處理器id+exp2(m-1)發(fā)回id號處理器*/int GetDataSize(); para_QuickSort(int *data,int start,int end,int m,int id,int MyID); QuickSort(int *data,in

10、t start,int end);int Partition(int *data,int start,int end);int exp2(int num);int log2(int num);ErrMsg(char *msg); main(int argc,char *argv) int DataSize;int *data;/*MyID表示進程標志符；SumID表示組內(nèi)進程數(shù)*/int MyID, SumID;int i, j;int m, r;MPI_Status status;/* 啟動 MPI 計算 */MPI_Init(&argc,&argv);/*MPl_COMM_WOR是D1 信

11、子 */* 確定自己的進程標志符 MyID*/ MPI_Comm_rank(MPI_COMM_WORLD,&MyID);/* 組內(nèi)進程數(shù)是 SumID*/MPI_Comm_size(MPI_COMM_WORLD,&SumID);*/* 根處理機 (MyID=0) 獲取必要信息，并分配各處理機進行工作 if(MyID=0)/* 獲取待排序數(shù)組的長度 */DataSize=GetDataSize(); data=(int *)malloc(DataSize*sizeof(int); /* 內(nèi)存分配錯誤 */ if(data=0)ErrMsg(Malloc memory error!); /* 動態(tài)

12、生成待排序序列 */ srand(396);for(i=0;iDataSize;i+)datai=(int)rand();printf(%10d,datai);printf(n);m=log2(SumlD); /調(diào)用函數(shù)：求以2為底的SumID的對數(shù)/*/* 從根處理器將數(shù)據(jù)序列廣播到其他處理器/*1 表示傳送的輸入緩沖中的元素的個數(shù)/* MPI_INT 表示輸入元素的類型 ,/* 0 表示 root processor 的 ID MPI_Bcast(&DataSize,1,MPI_INT,0,MPI_COMM_WORLD);/*ID 號為 0 的處理器調(diào)度執(zhí)行排序 */ para_Quick

13、Sort(data,0,DataSize-1,m,0,MyID);*/*/*/*/*ID 號為 0 的處理器打印排序完的有序序列 */ if(MyID=0)printf(實際應(yīng)用處理器數(shù)： %dn ,exp2(m-1);for(i=0;iDataSize;i+) printf(%10d,datai); printf(n); MPI_Finalize();return 0;/ 結(jié)束計算并行快速排序，對起止位置為start和end的序列，使用2的m次幕個處理器進行排序* 函數(shù)名 : para_QuickSort* 功能：*輸入：無序數(shù)組data1,n，使用的處理器個數(shù)2m* 輸出：有序數(shù)組 dat

14、a1,n */para_QuickSort(int *data,int start,int end,int m,int id,int MyID) int i, j;int r;int MyLength;int *tmp;MPI_Status status;MyLength=-1;/* 如果可供選擇的處理器只有一個，那么由處理器/*(1.1) Pid call quicksort(data,i,j) */ if(m=0)if(MyID=id)QuickSort(data,start,end);return;id 調(diào)用串行排序，對應(yīng)于算法步驟 (1.1)*/id+exp2(m-1) ，對應(yīng)于算法步

15、驟/* 由第 id 號處理器劃分數(shù)據(jù)，并將后一部分數(shù)據(jù)發(fā)送到處理器(1.2,1.3)*/*(1.2) Pid: r=patrition(data,i,j)*/ if(MyID=id)/*將當(dāng)前的無序區(qū)R1 , n劃分成左右兩個無序的子區(qū)R1 , i-1和Ri , n(1 i 0)*/* 在下面添加一條語句para_QuickSort(data,start,r-1,m-1,id,MyID);/*用2m-1個處理器對(r+1)-end的數(shù)據(jù)進行遞歸排序*/j=MyLength;MPI_Bcast(&j,1,MPI_INT,id,MPI_COMM_WORLD); /*(1.5) para_quick

16、sort(data,r+1,j,m-1,id+2m-1)*/ if(j0)/* 在下面添加一條語句 */ para_QuickSort(tmp,0,MyLength-1,m-1,id+exp2(m-1),MyID);/* 將排序好的數(shù)據(jù)由處理器 id+exp2(m-1) 發(fā)回 id 號處理器，對應(yīng)于算法步驟 (1.6)*/ /*(1.6) P(id+2m-1) send datar+1,m-1 back to Pid */ if(MyID=id+exp2(m-1) & (MyLength!=0)MPI_Send(tmp,MyLength,MPI_INT,id,id+exp2(m-1),MPI_

17、COMM_WORLD);if(MyID=id) & (MyLength!=0)MPI_Recv(data+r+1,MyLength,MPI_INT,id+exp2(m-1),id+exp2(m-1),MPI_COMM_WORLD,&status);/*函數(shù)名 : QuickSort功能：對起止位置為 start 和 end 的數(shù)組序列，進行串行快速排序。 輸入：無序數(shù)組 data1,n返回：有序數(shù)組 data1,n*/QuickSort(int *data,int start,int end) int r; int i;if(startend)r=Partition(data,start,en

18、d);QuickSort(data,start,r-1);QuickSort(data,r+1,end);return 0;/* 函數(shù)名 : Partition* 功能：* 輸入：* 返回 :對起止位置為 start 和 end 的數(shù)組序列，將其分成兩個非空子序列， 其中前一個子序列中的任意元素小于后個子序列的元素。無序數(shù)組 data1,n兩個非空子序列的分界下標*/int Partition(int *data,int start,int end)int pivo; int i, j;int tmp;pivo=dataend;i=start-1;/*i（ 活動指針 ）*/*for(j=sta

19、rt;jend;j+) if(dataj0)num-;i=i*2;return i;函數(shù)名 : log2功能： 輸入： 返回:求以2為底的num的對數(shù) int 型數(shù)據(jù) num以2為底的num的對數(shù)*/int log2(int num) int i, j;i=1;j=2;while(jnum) i-;return i;/* 函數(shù)名 : GetDataSize* 功能：讀入待排序序列長度*/ int GetDataSize() int i;while(TRUE)printf(Input the Data Size :); scanf(%d,&i);*/* 讀出正確的 i ，返回；否則，繼續(xù)要求輸入

20、 if(i0) & (iRp irun -np Input the Data Slse ：9 1331424828268魯歴使3藝的處理器個數(shù); 侯逋排序啟的序列；1331424S301941756220739301942S4B019964175&2199642668&282082846028789E:hywDebuffnpirun np Input the Dat38129912S05287982635排序后525 3S6 1056S 12922 1996428268Size ：5石4248 26$09 15410 22456 12504 275529140175&

21、2 1201870&5 129ja 25&G 105&5 253&9Z8789 i277S 243375779 210S8 316S3 2060030194 1961 195322613 1S48S 228&0 2313926&86317941958 113G8 23&567&67217228466 2G8093751 11172 23506 25429&335詢64525 1S407 14900 眈0 5271 3206?的處理器個數(shù): 的序列12994248 11363 149B024337264301331SZ71 11172 1S41Q 20899 253&9 287891958533

22、5 12B38 17562 210SS 25429 287982610577? 12S04 1S407 22456 2磁& 30194217270& 12505 1S488 玄2時 2G&8G 21&3Z6357667 1277S 1?Q81 23139 2&809 31743751?140 12618 19532 23S0G 27S52 3209E: shywKDebuffnpipun -np Input the Data Size 13314248序后的序列11331424817562堆個Z87B93019426&86175622S78930194E： JiywDebu“mpirun np

23、 Input the Data Size ：10 4248 2080910133128208謹詈的序列1331287894248 301941756228?的301942&S62846019t4175621?9642680?26&86Z820826480，并了解了實現(xiàn)快速排序的并行流程3.6實驗總結(jié) 通過這次實驗，我 熟悉快速排序的串行算法和并行算法 圖。但是在實際的操作過程中也遇到了不少問題。最后是在同學(xué)的幫助下完成的。一、枚舉排序算法說明：枚舉排序 ( Enumeration Sort )是一種最為簡單的排序算法，通常也被叫做秩排序( Rank Sort )。該算法的基本思想是：對每一個要

24、排序的元素統(tǒng)計小于它的所有元素的個數(shù)，從而得到該元素在整個序列中的位置。其時間復(fù)雜度為o(n八2)。其偽代碼為：輸入為： a1, a2 , . , an輸出為： b1, b2 , ., bn for i =1 to n do1)k =12)for j = 1 to n doif a aj thenendifendfor3)bk = ak= k + 16.8.endfor算法思想很簡單，現(xiàn)將其主要代碼總結(jié)如下：1 、數(shù)組自動生成，隨機生成長度為 n 的數(shù)組：1.1:void array_builder(int *a, int n)2.3.2:4.5.3:int i;7.4:9.5:srand(i

25、nt)time(0);10.6:11.12.3.2:13.7:for(i = 0; i n; i+)14.15.8:a = (int)rand() % 100;16.9:17.18.19.10:return;20.21.11:復(fù)制代碼2、取得每個元素在數(shù)組中的秩， 即統(tǒng)計每個元素按小于它的其他所有元素的個1.數(shù)：1: int *get_array_elem_position(int *init_array, intarray_length, int start, int size)2.4.5.3:int i,j,k;6.7.4:int *position;8.9.5:10.11.6:posit

26、ion = (int *)my_malloc(sizeof(int) * size);12.13.7:for(i = start; i start+size; i+)14.15.8:k = 0;16.17.9:for(j = 0; j array_length; j+)18.19.10:if(init_array j)25. 13:k+;25.26.27.14:28.29.15:30.31.16:positioni-start = k;32.33.17:34.35.18:36.37.19:return position;38.39.20:2.5.5.3:復(fù)制代碼其中 my_malloc 函數(shù)的作用為動態(tài)分配大小為 size 的空間，如分配失敗， 則終 止程序：1.1:void *my_malloc(int malloc_size)3.2:void *buffer;6.3.4.7. 4:if(buffer = (void *)malloc(size_t)malloc_size)= NULL)8.9.5:printf(malloc failure);10.11.6:exit(EXIT_FAILURE);12.7:13.14.8:15.16.17.9: