我使用 OpenMP 在 C 中实现了并行冒泡排序算法(奇偶转置排序)。然而,在我测试它之后,它比串行版本慢(大约 10%),尽管我有一个 4 核处理器(2 real x 2,因为 Intel 超线程)。我已经检查过内核是否实际被使用,并且在运行程序时我可以看到它们每个都是 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 个物理核心上进行了测试 -> 一组 150k 的数字用了 21 秒,这远远少于一个核心)。但是,如果我自己设置 OMP_SCHEDULE 环境变量,性能会降低......