时间戳

首页 > 解决方案 > 使用 OpenMP 并行化快速排序

c++ - 使用 OpenMP 并行化快速排序

问题描述

我正在尝试使用 OpenMP 来并行化快速排序（对于具有不同整数的数组）。我已经有一个工作实现（我测试了多个线程的输出，它似乎工作）。问题是我没有看到任何加速，即使对于大型阵列，这让我相信我的实现是不正确的。由于实际实现是正确的，但并行性似乎并没有产生预期的加速，我将只展示代码的并行化：

void parallel_randomized_quicksort(vector<int>& A, int start, int end){
  if ((end-start) is too small){
    run a serial sorting algorithm
  }else{
    pick a random pivot x and partition A around that pivot.
    k = index of x in A
    #pragma omp parallel
    {
      #pragma omp single nowait
      {
        parallel_randomized_quicksort(A,start,k-1);
      }
      #pragma omp single nowait
      {
        parallel_randomized_quicksort(A,k+1,end);
      }
    }
  }
}

如果这是正确的，应该会有一些加速，因为左右分区可以并行递归，这是我的代码的目标。为什么我没有注意到加速？

编辑：执行时间使用以下方法测量： 

double start_time = omp_get_wtime();
  parallel_randomized_quicksort(A,0,A.size()-1);
  double time = omp_get_wtime() - start_time;

数组是不同的整数。数组的大小从 100 到 1,000,000 不等。对于较小的阵列，时间以毫秒为单位，对于较大的阵列，时间以几秒钟为单位。通常，如果数组小于 32，我将使用简单的串行算法，如插入排序。

标签： c++openmp

解决方案

推荐阅读