插入排序OpenMP

我正在嘗試爲插入排序編寫OpenMP解決方案，但我遇到了問題，使它並行運行並給出正確的結果:)。有沒有什麼辦法讓插入排序它並行運行。插入排序OpenMP

這裏是我的代碼：

void insertionsort(int *A, int num) 
{ 

// clock_t start, stop; 
// 
// start=clock(); 
int k; 
#pragma omp parallel for shared(A) private(k) 
for(int n = 1; n < num; n++) 
{ 
    int key = A[n]; 
    k = n; 
#pragma omp critical 

    for(;k>0 && A[k-1]> key;k--) 
    { 
     A[k] = A[k-1]; 
    } 



    A[k] = key; 


} 
// stop=clock(); 
// cas = (double)(stop-start)/CLOCKS_PER_SEC; 
}

來源

2012-12-16 Mite Ristovski

使用'clock（）'來測量線程化程序的運行時間是錯誤的。它爲您提供累計的CPU時間，這意味着所有線程的CPU時間。改用'omp_get_wtime（）'。在這個話題中，這個「關鍵」區域基本上是將你的「並行」循環串連起來，因爲外面的工作量實際上沒有。 –

您不能並行插入排序算法這樣。正如您從內部循環條件A[k-1]> key;中可以看到的，此算法假定對於陣列的位置k中給定的key，如果實際的鍵大於存儲在陣列先前位置上的鍵，則應停止swap。因此，該算法假定k以下的位置上的按鍵是已經排序的。

當你介紹並行化時，例如兩個線程，線程0將從數組的開頭開始，線程1將從一半開始。問題是根據算法的假設，前半部分沒有排序，因此會導致問題。

讓我給你舉一個例子，一個array = [-1,2,-3,4,-5,6,-7,8] 2個線程排序：讓我們來解決下令給定執行（在現實中是不確定性）

1）主題0取K = 1和鍵= 2;陣列狀態[-1,2,-3,4,-5,6,-7,8]
2）線程1需要k = 5和key = 6;陣列狀態[-1,2,-3,4,-5,6,-7,8]
3）線程0需要k = 2和鍵= -3;陣列狀態[-3,-1,2,4,-5,6,-7,8]
4）線程1需要k = 6和key = -7;陣列狀態[-7,-3,-1,2,4,-5,6,8]
5）線程0需要k = 3和key = 2;陣列狀態[-7,-3,-1,2,4,-5,6,8]
6）線程1需要k = 7和key = 8;陣列狀態[-7,-3,-1,2,4,-5,6,8]
7）線程0需要k = 4和鍵= 4;陣列狀態[-7,-3,-1,2,4,-5,6,8]

最終結果：[-7,-3,-1,2,4,-5,6,8]

在4行線程1從6位置取鍵-7和在陣列從位置1 to 6篩選所有的元件的端部使（包括）一個位置到正確的，所以現在-5位於-7的舊位置。因爲，-7（6）的舊位置將永遠不會再比較-5將保持不可變。因此，使算法不被排序。

一個簡單但不好的解決方案是將OpenMP ordered子句添加到parallel for構造中。但是，使用這將使您的代碼基本上是一個順序的。

另一個可能的解決方案，雖然我不是100％確定它可以適合您的情況，但可以通過常規採樣使您的算法變得平行。你可以看到here這個後一種技術的例子適用於quicksort。

算法的結構不是直接並行化並實現加速的最好方法。由於內部循環的每次迭代都是相互依賴的，因此需要使用方法來確定互斥，從而導致開銷。你有更好的排序算法，你可以直接並行化，通常是那些使用分治策略的算法，如Radix Sort或Quick Sort等。

來源

2012-12-17 06:36:21 dreamcrash

插入排序OpenMP

回答

相關問題