C OpenMP并行冒泡排序

Question

我在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 < 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的数字,它花了21s,远远低于一个核心).但是,如果我自己设置OMP_SCHEDULE环境变量,性能会降低......

Answer 1

您应该分析它并检查线程在哪里花费了时间。

一个可能的原因是平行区域不断地被创建和破坏；根据 OpenMP 实现，它可能会导致重新创建线程池，尽管好的实现可能应该处理这种情况。

一些需要删除的小事情：
-ok似乎完全没有必要，您可以将循环退出条件更改为i<n-1;
- 显式屏障是不必要的 - 首先，你把它放在并行区域之外，所以它没有意义；其次，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 ) {...}
}