并行歸并排序

1、精選優(yōu)質(zhì)文檔-傾情為你奉上串行歸并與并行歸并排序算法一、 串行歸并排序算法歸并排序是一種很容易進(jìn)行并行化的算法，因為歸并的各個數(shù)據(jù)區(qū)間都是獨立的，沒有依賴關(guān)系。并且歸并排序是一種速度比較快的排序，且是一種穩(wěn)定的排序算法，排序速度與關(guān)鍵詞初始排列無關(guān)。串行歸并排序的算法大體的可以描述為：首先將要排序的表分成兩個節(jié)點個數(shù)基本相等的子表，然后對每個子表進(jìn)行排序，最后將排好序的兩個子表合并成一個子表。在對子表進(jìn)行排序時可以將子表再分解成兩個節(jié)點數(shù)量基本相同的子表，當(dāng)子表足夠小時，也可以采用其他排序方法對子表進(jìn)行排序，然后再對排好序的子表進(jìn)行歸并操作，最后將整個表排好序。1、1算法流程圖并行歸并排序算法

2、的流程圖：1、2代碼分析#include <iostream>using namespace std;#define N 11int arrayN = 4, 67, 456, 23, 1, 78, 26, 222, 34, 432, 12 ; /待排序數(shù)組int otherN; /輔助空間,用以暫存已經(jīng)排序的數(shù)組元素void Swap(int &a, int &b)int tmp = a;a = b;b = tmp;/* array 待排序數(shù)組* begin 數(shù)組開始的下標(biāo)* end 數(shù)組最后一個元素的下標(biāo)*/void MergeSort(int *array, i

3、nt begin, int end)if(end-begin+1 > 2) MergeSort(array, begin, (end+begin)/2);MergeSort(array, (end+begin)/2+1, end);int i = begin, j = (end+begin)/2+1, k=begin;while(i<=(begin+end)/2 && j<=end) if(arrayi < arrayj)otherk+ = arrayi+;elseotherk+ = arrayj+;while(i <= (begin+end)/2

4、) otherk+ = arrayi+;while(j <= end) otherk+ = arrayj+;for(k=begin; k<=end; +k) arrayk = otherk;else if(arrayend < arraybegin) Swap(arrayend, arraybegin);void Output(int *array, int n)for(int i=0; i<n; +i)cout<<arrayi<<" "cout<<endl;int main()cout<<"

5、串行歸并排序算法"<<endl<<"the numbers are: "Output(array, N);MergeSort(array, 0, N-1);cout<<"the sorted result:"Output(array, N);int i;cin>>i;return 0;1、3運行結(jié)果1、4復(fù)雜度分析通過算法分析很容易發(fā)現(xiàn)串行歸并排序算法的時間復(fù)雜度地推公式為：這是一個時間復(fù)雜度的遞推公式，我們需要消去等號右側(cè)的T(n)，把T(n)寫成n的函數(shù)。其實符合一定條件的Recurrence

6、的展開有數(shù)學(xué)公式可以套，這里我們略去嚴(yán)格的數(shù)學(xué)證明，只是從直觀上看一下這個遞推公式的結(jié)果。當(dāng)n=1時可以設(shè)，當(dāng)n>1時可以設(shè)，我們?nèi)1和c2中較大的一個設(shè)為c，把原來的公式改為：參照主定理公式，可以知道當(dāng)n>1時，有以下等式成立：同時又有下面的等式成立：則有T(n)滿足主定理公式的第二種情況，也即是T(n)的時間復(fù)雜度為：二、 并行歸并排序算法由串行歸并排序算法可知，歸并的各個數(shù)據(jù)區(qū)間都是獨立的，沒有依賴關(guān)系。因此歸并排序是一種很容易進(jìn)行并行化的算法。其方案是先將待排序區(qū)間劃分成若干個相等的小區(qū)間，然后并行地對這些小區(qū)間進(jìn)行排序，最后再通過歸并的方法將所有排好序的小區(qū)間歸并成一個

7、有序系列。由于歸并時是一層層向上進(jìn)行的，因此需要將區(qū)間劃分成個小區(qū)間，這樣第1輪歸并時，可以將個小區(qū)間歸并成個區(qū)間。這樣過k輪歸并操作后就歸并成一個有序的大區(qū)間。這也正是并行歸并排序的算法思想。2、1算法流程圖并行歸并排序算法的思想可以通過下面的流程圖表示：2、2代碼分析功能函數(shù)頭文件：MergeSort.h#define MAX_MERGE_TURN 24 #define MIN_PARALLEL_SORT_COUNT 3#define MIN_MERGE_COUNT 2#define CACHE_LINE_SIZE 64typedef unsigned int UINT;#include&

8、lt;omp.h>#include<windows.h>#include<iostream>#include<cstdlib>#include<ctime>using namespace std;int compare(int* one, int* two)if(*one > *two)return 1;else if(*two > *one)return -1;elsereturn 0;void *GetCacheAlignedAddr(void *pAddr) int m = CACHE_LINE_SIZE; void *p

9、Ret = (void *)(UINT)pAddr+m-1)&(-m); return pRet;/* 串行歸并函數(shù)歸并好的數(shù)據(jù)存放在輸出參數(shù)ppNewData中param void *ppData - 待歸并的數(shù)據(jù) param int nStart1 - 第個區(qū)間的開始位置(包括nStart1) param int nEnd1 - 第個區(qū)間的結(jié)束位置(包括nEnd1) param int nStart2 - 第個區(qū)間的開始位置(包括nStart2) param int nEnd2 - 第個區(qū)間的結(jié)束位置(包括nEnd2) param COMPAREFUNC func - 比較函數(shù) p

10、aram void *ppNewData - 存放歸并后的數(shù)據(jù) return void* - 返回歸并后的數(shù)據(jù)指針(等于ppNewData) */ int* Serial_Merge(int *ppData, int nStart1, int nEnd1, int nStart2, int nEnd2, int(*func)(int*, int*) , int *ppNewData) int i, j, k; i = nStart1; j = nStart2; k = nStart1; for( i = nStart1; i <= nEnd1;) for ( ; j <= nEnd

11、2; j+ ) if ( (*func)(ppDatai, ppDataj) < 0 ) ppNewDatak = ppDatai; +k;i+;break; else ppNewDatak = ppDataj; +k; /如果j已經(jīng)到了尾部if ( j > nEnd2 ) for ( ; i <= nEnd1; i+ ) ppNewDatak = ppDatai; +k; break; if ( i > nEnd1 ) for ( ; j <= nEnd2; j+ ) ppNewDatak = ppDataj; +k; for(i = nStart1; i &l

12、t;= nEnd2; i+)ppDatai = ppNewDatai;return ppData; /* 串行歸并排序函數(shù)param void *ppData - 待排序數(shù)據(jù) param int nBegin - 排序區(qū)間的開始位置 param int nEnd - 排序區(qū)間的結(jié)束位置 param COMPAREFUNC func - 數(shù)據(jù)大小比較函數(shù) return void - 無 */ void Serial_MergeSort(int *ppData, int nBegin, int nEnd, int(*func)(int*, int*) if ( nEnd - nBegin <

13、 MIN_MERGE_COUNT ) int* temp;if(*ppDatanBegin > *ppDatanEnd)temp = ppDatanBegin;ppDatanBegin = ppDatanEnd;ppDatanEnd = temp;return; int* tempData = new int*nEnd - nBegin + 1;int i;int tmpInt = 0;for(i = 0; i < nEnd - nBegin + 1; i+)tempDatai = &tmpInt;int nMid = (nBegin + nEnd) >> 1;

14、 /除以Serial_MergeSort(ppData, nBegin, nMid, func); Serial_MergeSort(ppData, nMid+1, nEnd, func); Serial_Merge(ppData, nBegin, nMid, nMid+1, nEnd, func, tempData); /* 并行歸并快速排序函數(shù)param void *ppData - 待排序數(shù)據(jù) param int nLen - 待排序數(shù)據(jù)長度 param COMPAREFUNC func - 數(shù)據(jù)比較回調(diào)函數(shù) return void - 無 */ void Parallel_MergeS

15、ort(int *ppData, int nLen, int(*func)(int*, int*) int i, k; int nStep; int nLoopCount; int nCore; int nStart1, nEnd1; if ( nLen < MIN_PARALLEL_SORT_COUNT ) Serial_MergeSort(ppData, 0, nLen - 1, func ); return; nCore = omp_get_num_procs(); int nCount = nLen / MIN_PARALLEL_SORT_COUNT; int nTurn = M

16、AX_MERGE_TURN; nLoopCount = 1 << nTurn; /nLoopCount等于的nTurn次方while ( nLoopCount > nCount ) nLoopCount = nLoopCount >> 1; /除以-nTurn; /判斷nTurn是否為奇數(shù)if ( (nLoopCount > nCore) && (nTurn > 0x1) && (nTurn & 0x1) = 0x1) ) -nTurn; /把nTurn變成偶數(shù)，便于后面不拷貝數(shù)據(jù)nLoopCount = nLo

17、opCount >> 1; nStep = nLen / nLoopCount; int *p = new intnLoopCount*2 + CACHE_LINE_SIZE; int *pnPos = (int *)GetCacheAlignedAddr(p); /將數(shù)據(jù)分成nLoopCount個小區(qū)間，并行地對每個區(qū)間進(jìn)行串行排序#pragma omp parallel for private(nStart1, nEnd1) num_threads(nCore) for ( i = 0; i < nLoopCount; i+) nStart1 = i * nStep; n

18、End1 = nStart1 + nStep - 1; if ( i = nLoopCount - 1 ) nEnd1 = nLen - 1; Serial_MergeSort(ppData, nStart1, nEnd1, func); pnPosi + i = nStart1; pnPosi + i + 1 = nEnd1; /對排好序的各個相鄰區(qū)間進(jìn)行并行歸并操作int *pp = new int *nLen + CACHE_LINE_SIZE; int * ppOutData = (int *)GetCacheAlignedAddr(int *)pp); int * ppMergeDa

19、ta = ppData; int * ppTempOutData = ppOutData; int * ppSwap; nStep = 2; for ( k = 0; k < nTurn; k+ ) #pragma omp parallel for num_threads(nCore) for ( i = 0; i < nLoopCount-1; i += 2 ) int nPos = i * nStep; Serial_Merge(ppMergeData, pnPosnPos, pnPosnPos+1, pnPosnPos+nStep, pnPosnPos+nStep+1,fun

20、c, ppTempOutData); pnPosnPos+1 = pnPosnPos+nStep+1; nLoopCount = nLoopCount >> 1; /除以nStep += nStep; ppSwap = ppMergeData; ppMergeData = ppTempOutData; ppTempOutData = ppSwap; /將數(shù)據(jù)寫回到ppData中，如果nTurn為偶數(shù)則下面的判斷內(nèi)的循環(huán)不會被執(zhí)行if ( ppMergeData = ppOutData ) #pragma omp parallel for num_threads(nCore) for

21、 ( i = 0; i < nLen; i+ ) ppDatai = ppOutDatai; delete p; delete pp; return; 測試文件：Test.cpp#include"MergeSort.h"/test MergeSortvoid testFunc(int size)Sleep(1000);/防止srand取同樣的值int i;int cost;SYSTEMTIME lpsystimeStr;SYSTEMTIME lpsystimeEnd;int* ppDataForSerial = new int*size;int* ppDataForP

22、arallel = new int*size;int* tempArrForSerial = new intsize;int* tempArrForParallel = new intsize;srand(unsigned int)time(0);for(i = 0; i < size; i+)tempArrForSeriali = rand();tempArrForParalleli = tempArrForSeriali;ppDataForSeriali = tempArrForSerial + i;ppDataForParalleli = tempArrForParallel +

23、i;cout << "測試" << size << "個數(shù)字串行歸并算法：" << endl;GetLocalTime(&lpsystimeStr); printf("開始時間：%u年%u月%u日星期%u %u:%u:%u:%un",lpsystimeStr.wYear,lpsystimeStr.wMonth,lpsystimeStr.wDay,lpsystimeStr.wDayOfWeek,lpsystimeStr.wHour,lpsystimeStr.wMinute,lpsy

24、stimeStr.wSecond,lpsystimeStr.wMilliseconds); Serial_MergeSort(ppDataForSerial, 0, size - 1, compare);GetLocalTime(&lpsystimeEnd); printf("結(jié)束時間：%u年%u月%u日星期%u %u:%u:%u:%un",lpsystimeEnd.wYear,lpsystimeEnd.wMonth,lpsystimeEnd.wDay,lpsystimeEnd.wDayOfWeek,lpsystimeEnd.wHour,lpsystimeEnd.w

25、Minute,lpsystimeEnd.wSecond,lpsystimeEnd.wMilliseconds); cost = lpsystimeEnd.wMilliseconds - lpsystimeStr.wMilliseconds;if(cost <= 0)cost = cost + (lpsystimeEnd.wSecond - lpsystimeStr.wSecond) * 1000;cout << "共耗時：" << cost << "ms。" << endl;cout <<

26、 "串行歸并排序后前個數(shù)字："for(i = 0; i < 10; i+)if(0 = i % 6)cout << endl;cout << *ppDataForSeriali << " "cout << endl;cout << endl;cout << "測試" << size << "個數(shù)字并行歸并算法：" << endl;GetLocalTime(&lpsystimeStr); prin

27、tf("開始時間：%u年%u月%u日星期%u %u:%u:%u:%un",lpsystimeStr.wYear,lpsystimeStr.wMonth,lpsystimeStr.wDay,lpsystimeStr.wDayOfWeek,lpsystimeStr.wHour,lpsystimeStr.wMinute,lpsystimeStr.wSecond,lpsystimeStr.wMilliseconds); Parallel_MergeSort(ppDataForParallel, size, compare);GetLocalTime(&lpsystimeEn

28、d); printf("結(jié)束時間：%u年%u月%u日星期%u %u:%u:%u:%un",lpsystimeEnd.wYear,lpsystimeEnd.wMonth,lpsystimeEnd.wDay,lpsystimeEnd.wDayOfWeek,lpsystimeEnd.wHour,lpsystimeEnd.wMinute,lpsystimeEnd.wSecond,lpsystimeEnd.wMilliseconds); cost = lpsystimeEnd.wMilliseconds - lpsystimeStr.wMilliseconds;if(cost <= 0)cost = cost + (lpsystimeE