c - OpenMP 递归并行性 (QuickSort)

Question

我一直在尝试使用 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
  }

简而言之，我相信我的并行化是错误的。 这些行:

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

并且

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

任何帮助都将是doge

Answer 1

您尝试过更大的数组吗？ 10000 不算什么，应该立即排序，你需要数百万个数字才能让它运行至少几秒钟。