OpenMP中的并行合并排序

我在本文中看到了并行合并排序的算法。 这是代码：

void mergesort_parallel_omp (int a[], int size, int temp[], int threads) { if ( threads == 1) { mergesort_serial(a, size, temp); } else if (threads > 1) { #pragma omp parallel sections { #pragma omp section mergesort_parallel_omp(a, size/2, temp, threads/2); #pragma omp section mergesort_parallel_omp(a + size/2, size - size/2, temp + size/2, threads - threads/2); } merge(a, size, temp); } // threads > 1 } 

我在多核上运行它。 发生的事情是，在树的叶子上，2个线程并行运行。 完成工作后，其他两个线程开始，依此类推。 即使我们有所有叶节点的免费核心。

我认为原因是这个OpenMP代码不会在并行区域内创建并行区域。 我对么？

Answer 1

“我认为原因是OpenMP无法在并行区域内创建并行区域”

您可以拥有平行区域的平行区域。

OpenMP并行区域可以彼此嵌套 。 如果禁用嵌套并行性 ，则由线程在并行区域内遇到并行构造创建的新团队仅包含遇到的线程 。 如果启用了嵌套并行性 ，则新团队可能包含多个线程 （ 源 ）。

为了正确运行代码，您需要调用omp_set_nested(1)和omp_set_num_threads(2) 。

可以通过设置OMP_NESTED环境变量或调用omp_set_nested（）函数来启用或禁用嵌套并行性

Answer 2

这个问题的现代答案是使用任务而不是部分。 任务在OpenMP 3.0（2009）中添加，比嵌套并行和部分更好/更容易，因为嵌套并行可能导致超额订阅（比可用的CPU更活跃的线程），这会导致显着的性能下降。 对于任务，您有一组线程匹配CPU的数量，并且将处理任务。 因此，您不需要使用threads参数进行手动处理。 一个简单的解决方案如下所示：

 // span parallel region outside once outside void mergesort_omp(...) { #pragma omp parallel #pragma omp single mergesort_parallel_omp(...) } void mergesort_parallel_omp (int a[], int size, int temp[]) { #pragma omp task mergesort_parallel_omp(a, size/2, temp); mergesort_parallel_omp(a + size/2, size - size/2, temp + size/2); #pragma omp taskwait merge(a, size, temp); } 

但是，为太小的工作块创建任务仍然存在问题，因此基于工作粒度来限制并行性是有用的，例如：

 void mergesort_parallel_omp (int a[], int size, int temp[]) { if (size < size_threshold) { mergesort_serial(a, size, temp); return; } #pragma omp task mergesort_parallel_omp(a, size/2, temp); mergesort_parallel_omp(a + size/2, size - size/2, temp + size/2); #pragma omp taskwait merge(a, size, temp); } 

Answer 3

也许我完全忽略了这一点……但是如果你想在2个以上的线程上执行，你是否意识到你需要设置环境变量OMP_NUM_THREADS？