Рекурсивный параллелизм OpenMP (QuickSort)

Question

Я пытался распараллелить Quick Sort с помощью OpenMP, но кажется, что я сделал что-то не так в этой части, так как больше потоков использовало медленнее!

Я знаю, что всегда есть накладные расходы, но увеличение количества потоков в гигантском списке должно сделать его быстрее и не медленнее (мой случай).

Вот код, который понравится!

#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); 
} 

Любая помощь будет доже

Answer 1

ли вам попробуйте большой массив? 10000 - это ничего, что нужно сортировать мгновенно, и вам нужны миллионы чисел, чтобы заставить его работать как минимум несколько секунд.