C OpenMP并行冒泡排序
C OpenMP并行冒泡排序
提问于 2011-11-03 23:39:44
我使用OpenMP用C语言实现了并行冒泡排序算法(Odd-Even transposition sort)。然而，在我测试之后，它比串行版本慢(大约10%)，尽管我有一个4核处理器(2个实数x 2，因为英特尔超线程)。我已经检查了内核是否真的被使用了，在运行程序时我可以看到每个内核都是100%的。因此，我认为我在算法的实现中犯了一个错误。
我使用的是内核为2.6.38-8-generic的linux。
我是这样编译的：
gcc -o bubble-sort bubble-sort.c -Wall -fopenmp或
串行版本的gcc -o bubble-sort bubble-sort.c -Wall -fopenmp
我是这样运行的：
./bubble-sort < in_10000 > out_10000
#include <omp.h>
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
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 < n - 1; i = i + 2)
{
if(x[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 < n - 1; i = i + 2)
{
if( x[i] > x[i+1] )
{
tmp = x[i];
x[i] = x[i+1];
x[i+1] = tmp;
++changes;
}
}
}
}
return 0;
}稍后编辑：
在我做了您建议的更改后，它现在似乎工作得很好。它的伸缩性也很好(我也在8个物理核心上进行了测试，->在一组15万个数字上花费了21秒，远远少于在一个核心上)。但是，如果我自己设置OMP_SCHEDULE环境变量，性能就会下降……
回答 1
Stack Overflow用户
回答已采纳
发布于 2011-11-04 05:03:56
您应该对其进行分析，并检查线程将时间花在哪里。
一个可能的原因是并行区域不断地被创建和销毁；根据OpenMP实现的不同，这可能会导致重新创建线程池，尽管好的实现可能会处理这种情况。
一些需要刮掉的小东西：
ok似乎完全没有必要，您只需将循环退出条件更改为i<n-1;- explicit屏障是不必要的-首先，您将其放在并行区域之外，因此它没有任何意义；其次，OpenMP并行区域和循环在末尾具有隐式屏障；
- 在while循环中至少组合了两个后续的并行区域：
#pragma omp parallel private(tmp)
{
#pragma omp for bla-bla
for (i=0; i<n-1; i+=2 ) {...}
#pragma omp for bla-bla
for (i=1; i<n-1; i+=2 ) {...}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/7997684
复制相关文章
相似问题
腾讯云开发者
