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);
                }
            }
        }
    }
}

整个排序过程发生在 partition 方法中，如果您对它的工作方式感兴趣，这里是代码：

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 函数中的 printf 之前停止计时器。 线程数量定义为10（我已在我的电脑上尝试过4、2和1）。在对包含100万个介于0-100之间的随机整数的列表进行排序后，我的结果如下：

没有使用 OpenMP 的时间在6.48004至5.32001之间。

使用 OpenMP 的时间在11.8309至10.6239之间（使用2-4个线程）。

这是怎么回事？

- Max Mansour

---

https://fgiesen.wordpress.com/2013/01/31/cores-dont-like-to-share/ 可能是一个好的起点。 - akira

Answer 1

快速排序的一般思想是：

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

那个元素列表被分成了两个任务：

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

每个“任务”都会被再次分割，一遍又一遍。

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

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

|--- 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都必须进行一些管理开销。如果任务太小，则还会增加开销与工作比率。

谷歌搜索出来的基于OpenMP的快速排序算法：

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

愿它激励着你。

- akira