OpenMP遞歸併行性（QuickSort）

我一直在嘗試使用OpenMP並行化快速排序，但似乎我在該部分做了一些錯誤，因爲越多的線程使用它越慢！OpenMP遞歸併行性（QuickSort）

我知道總會有開銷包括在內，但是巨大列表中線程數量的增加會讓它更快，而且不會更慢（我的情況）。

這裏是代碼享受！

#include <omp.h> 

double start_time, end_time; 

#include <stdio.h> 
#define MAXSIZE 10000 /* maximum array size */ 
#define MAXWORKERS 8 /* maximum number of workers */ 

int numWorkers; 
int size; 
int doge[MAXSIZE]; 
void breakdown(int, int); 

/* read command line, initialize, and create threads */ 
int main(int argc, char *argv[]) { 
srand(time(NULL)); 
int i; 

/* read command line args if any */ 
size = (argc > 1)? atoi(argv[1]) : MAXSIZE; 
numWorkers = (argc > 2)? atoi(argv[2]) : MAXWORKERS; 
if (size > MAXSIZE) size = MAXSIZE; 
if (numWorkers > MAXWORKERS) numWorkers = MAXWORKERS; 

for(i = 0;i<size;i++){ 
    doge[i] = 1+rand()%99; 
} 

omp_set_num_threads(numWorkers); 

start_time = omp_get_wtime(); 
#pragma omp parallel 
{ 
    #pragma omp single nowait 
    { 
     breakdown(0, size); 
    } 
} 

end_time = omp_get_wtime(); 

for(i = 0;i<size;i++){ 
    printf("%d ", doge[i]); 
} 
printf("it took %g seconds\n", end_time - start_time); 
    } 

    void breakdown(int from, int to){ 

if(to-from < 2){ 
    return; 
} 
int left, right, temp; 
int i_pivot = from + rand()%(to-from); 
int pivot = doge[i_pivot]; 

left = from; 
right = to; 
while (left <= right){ 
    if (doge[left] > pivot){ 
     /* swap left element with right element */ 
     temp = doge[left]; 
     doge[left] = doge[right]; 
     doge[right] = temp; 
     if (right == i_pivot) 
      i_pivot = left; 
     right--; 
    } 
    else 
     left++; 
} 
/* place the pivot in its place (i.e. swap with right element) */ 
temp = doge[right]; 
doge[right] = pivot; 
doge[i_pivot] = temp; 

#pragma omp task 
{ 
    breakdown(from, right - 1); 
} 
#pragma omp task 
{ 
    breakdown(right + 1, to); 
} 
//implicit DOGE 
    }

我相信我已經做了parallalization錯總之.. 這些行：

#pragma omp parallel 
{ 
    #pragma omp single nowait 
    { 
     breakdown(0, size); 
    } 
}

和

#pragma omp task 
{ 
    breakdown(from, right - 1); 
} 
#pragma omp task 
{ 
    breakdown(right + 1, to); 
}

任何幫助將是公爵

來源

2014-02-20 David Ekermann

如果所有線程都可以一次運行（多個處理器核心，沒有數據重疊等），或者如果進程涉及等待狀態（例如I/O）並且可以工作，則增加線程數量僅會提高性能在等待期間在另一個線程上完成。它不會自動地改進所有機器和任務，甚至在大多數機器和任務上。 – keshlam

是的，我同意這一點，但在這種情況下，我運行在一個4核（超線程x2）機器上，列表非常大，所以我應該能夠看到某種改進，因爲快速排序是平行的。 –

只有當線程真正獨立時，纔會導致額外的緩存刷新，並且在不同的內核中運行（這取決於實現的細節）。基本上，除非你知道硬件和語言的實現細節，否則「應該」在這裏是太強大了。 – keshlam

你有沒有嘗試更大的陣列？ 10000沒有什麼，應該立即排序，你需要數以百萬計的數字，讓它運行至少幾秒鐘。

來源

2014-03-23 22:50:35 user2849936

是的，我嘗試了很多10000以上的尺寸（我改變了MAXSIZE）。 –

你的CPU有多少核心？ – user2849936

12 + HyperThreading技術上很好24. –

OpenMP遞歸併行性（QuickSort）

回答

相關問題