为什么我的 OpenMP 并行快速排序比顺序快速排序慢得多？

Question

我在Windows上用VSCode G++ -fopenmp编译。我目前试图证明并行快速排序确实比顺序快速排序更快，但无济于事。我已将线程数更改为 2（减少可能的开销），并且还更改了生成的数字量 (10,100,10000,100000)，但所有这些都不起作用。下面是 10000 个数据的结果时间（彼此甚至不接近……慢了 500 倍）。 并行时间：4.555 串行时间：0.0071298

下面是一些代码片段，这是完整的代码。

分区：

int partition(vector<int> &data, int p, int r){
    int pivot = data[p];
    int left = p;
    int right = r;
    while (left < right){
        while (left < r && data[left] <= pivot) ++left;
        while (right >= 0 && data[right] > pivot) --right;
        if (left < right && left <r && right >= 0)
        {
            std::swap(data[left], data[right]);
        }
    }

    if (left < right && left <r && right >= 0)
    {
        std::swap(data[left], data[right]);
    }
    data[p] = data[right];
    data[right] = pivot;
    return right;
}

并行快速排序：

void ParallelQuickSort (vector<int> &dataList,  int nLower, int nUpper)                                                                                             
{
    if (nLower < nUpper)
    {
        int nSplit = partition (dataList, nLower, nUpper);
        omp_set_num_threads(2);
        #pragma omp parallel sections
        {
            #pragma omp section                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       
            ParallelQuickSort (dataList, nLower, nSplit - 1);

            #pragma omp section
            ParallelQuickSort (dataList, nSplit + 1, nUpper);
        }
    }
}

串行快速排序

void SerialQuickSort(vector<int> &dataList,  int nLower, int nUpper)
{
    if (nLower < nUpper)
    {
        int nSplit = partition (dataList, nLower, nUpper);                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   
        SerialQuickSort (dataList, nLower, nSplit - 1);
        SerialQuickSort (dataList, nSplit + 1, nUpper);
    }
}

上面测量运行时间/启动函数的函数（不确定我的问题是否与此有关，所以我想我只是将其上传到这里）：

void start_parallel_quicksort(vector<int> &vec,double &parallel_run_time)
{
    double parallel_start_time;
    parallel_start_time=omp_get_wtime();
    #pragma omp parallel
    {
        #pragma omp single nowait
        ParallelQuickSort(vec,0,VEC_SIZE-1);
    }
    parallel_run_time=omp_get_wtime()-parallel_start_time;
}

void start_serial_quicksort(vector<int> &vec, duration<double> &serial_run_time)
{
    auto serial_start_time = high_resolution_clock::now();
    SerialQuickSort(vec,0,VEC_SIZE-1);
    auto serial_end_time=high_resolution_clock::now();
    serial_run_time=serial_end_time-serial_start_time;
}

如果有人能帮助我，我将不胜感激。我在 stackoverflow 上搜索并尝试了所有能找到的方法，但都无济于事——没有人在这两种方法之间有如此巨大的差距。预先感谢！

Answer 1

正如评论中所述，OpenMP 任务更适合这种算法。你只需要修改

ParallelQuickSort

例程：

void ParallelQuickSort (vector<int> &dataList,  int nLower, int nUpper)                                                                                             
{
    if (nLower < nUpper)
    {
        int nSplit = partition (dataList, nLower, nUpper);
        if (nUpper - nLower >= 128) {
            #pragma omp task default(shared)
            ParallelQuickSort (dataList, nLower, nSplit - 1);
        } else {
            ParallelQuickSort (dataList, nLower, nSplit - 1);
        }
        ParallelQuickSort (dataList, nSplit + 1, nUpper);
        #pragma omp taskwait
    }
}

评论：

• 一旦对段进行分区，只需为其中一个分区创建一个额外的任务，而另一个任务可以由当前任务处理
• 您需要一个阈值来决定是否必须创建新任务，原因有两个：
  • 任务创建开销可能会隐藏小分区的任何并行化优势
  • 要排序的段很小，2个分区可能属于同一个缓存行（64和128字节），并且在不同核心之间同步缓存行的成本非常高。

您必须尝试各种阈值（我在代码中放置了任意 128 个元素）才能查看哪一个是最佳的。