C OpenMP并行冒泡排序

我在C中使用OpenMP实现了并行冒泡排序算法（ Odd-Even转置排序 ）。 然而，在我测试它之后，它比串行版本慢了（大约10％），尽管我有一个4核处理器（2个真正的x 2，因为英特尔超线程）。 我已经检查过核心是否实际使用过，我可以在运行程序时以100％的比例看到它们。 因此我认为我在实现算法时犯了一个错误。

我使用linux与内核2.6.38-8-generic。

这是我编译的方式：

gcc -o bubble-sort bubble-sort.c -Wall -fopenmp或

gcc -o bubble-sort bubble-sort.c -Wall -fopenmp用于串行版本

这就是我的运行方式：

./bubble-sort out_10000

 #include  #include  #include  #include  int main() { int i, n, tmp, *x, changes; int chunk; scanf("%d ", &n); chunk = n / 4; x = (int*) malloc(n * sizeof(int)); for(i = 0; i < n; ++i) scanf("%d ", &x[i]); changes = 1; int nr = 0; while(changes) { #pragma omp parallel private(tmp) { nr++; changes = 0; #pragma omp for \ reduction(+:changes) for(i = 0; i  x[i+1] ) { tmp = x[i]; x[i] = x[i+1]; x[i+1] = tmp; ++changes; } } #pragma omp for \ reduction(+:changes) for(i = 1; i  x[i+1] ) { tmp = x[i]; x[i] = x[i+1]; x[i+1] = tmp; ++changes; } } } } return 0; 

}

稍后编辑：

在我做出你建议的更改之后，它似乎现在运行良好。 它也可以很好地扩展（我在8个物理内核上也进行了测试 – >对于一组150k的数字，它花了21s，远远低于一个核心）。 但是，如果我自己设置OMP_SCHEDULE环境变量，性能会降低……

Answer 1

您应该对其进行分析并检查线程花费时间的位置。

一个可能的原因是并行区域不断创建和销毁; 取决于OpenMP实现，它可能导致重新创建线程池，尽管良好的实现应该可以处理这种情况。

一些小事要刮掉：
– ok似乎完全没必要，您只需将循环退出条件更改为i ;
- 显然屏障是不必要的 - 首先，你把它放在平行区域之外，这是没有意义的; 第二，OpenMP并行区域和循环最后有隐含的障碍;
- 在while循环中至少组合两个随后的并行区域：

 #pragma omp parallel private(tmp) { #pragma omp for bla-bla for (i=0; i