c - OpenMP 实现使我的代码变慢

Question

我正在尝试使用 openMP 使我的快速排序并行工作。实现 openMP 后，我尝试使快速排序更快地工作失败了，并且我的快速排序对数组的排序速度几乎慢了一倍。我的 openMP 实现代码:

void quickSort( int a[], int l, int r) {
    int j;
    if( l < r ) {
#pragma omp parallel
        {
            j = partition( a, l, r);
#pragma omp sections
            {
#pragma omp section
                {
                    quickSort( a, l, j-1);
                }
#pragma omp section
                {
                    quickSort( a, j+1, r);
                }
            }
        }
    }
}

整个排序发生在方法分区中，如果您对它的工作原理感兴趣，这里提供了它的代码:

int partition( int a[], int l, int r) {
    int pivot, i, j, t;
    pivot = a[l];
    i = l; j = r+1;     
    while(1) {  
        do ++i; while( a[i] <= pivot && i <= r );
        do --j; while( a[j] > pivot );
        if( i >= j ) break;
        t = a[i]; a[i] = a[j]; a[j] = t;
    }
    t = a[l]; a[l] = a[j]; a[j] = t;
    return j;
}

在调用 QuickSort 之前，我在 main 中花了一些时间，并且在 main 中的 printf 之前停止计时器。线程数定义为 10(我在我的电脑上尝试过 4,2 和 1)。对包含 1 000 000 个 0 - 100 之间的随机整数的列表进行排序后的结果:

时间(没有 openMP)在 6.48004 - 5.32001 之间

使用 openMP 时间介于 11.8309 和 10.6239 之间(使用 2-4 个线程)这怎么可能是真的？

Answer 1

快速排序的总体思路是这样的:

[......................]

该元素列表分为 2 个任务:

[..........][..........]

然后，每个“任务”都会一次又一次地拆分:

[..][..][..][..][..][..]

现在，CPU 喜欢处理紧密相连的数据。但是，当每个核心非常紧密地一起处理数据时，可能会出现这样的情况:一个核心写入的数据 block 与另一个核心上的数据位于同一缓存行上。由于您不希望核心互相写入数据，因此第一次写入将使其他核心中的数据无效，因此其他核心必须再次获取内存块。

|--- cache line ---|
[..][..][..][..][..][..]
 ^   ^   ^   ^
 |   |   |   |
 c1  c2  c3  c4

因此，无论哪个核心首先写入属于该缓存行的数据，都会使所有其他核心的数据无效。由于您使小任务 [..] 非常接近，因此会增加大量无效缓存行和从内存中重新获取数据的机会。这里更好地解释了效果

http://fgiesen.wordpress.com/2013/01/31/cores-dont-like-to-share

另请阅读http://lwn.net/Articles/252125/ ，特别是“3.3.4 多处理器支持”。

在非并行版本中，整个使缓存无效不会发生(经常)，因为只有一个核心在处理数据。

因此，一个可能的解决方案是不要拆分任务，直到任务太小而无法由核心有效处理为止。您必须考虑的另一个影响是:OpenMP 必须为每个任务执行一些管理开销。如果任务太小，您还可以增加开销与工作比率。

Google 吐出的基于 OpenMP 的快速排序是:

http://berenger.eu/blog/c-openmp-a-shared-memory-quick-sort-with-openmp-tasks-example-source-code/

愿这能激励你。