3

我正在尝试通过使用 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）。我在对 0 - 100 之间的 1 000 000 个随机整数的列表进行排序后的结果：

时间（没有 openMP）在 6.48004 - 5.32001 之间

openMP 时间在 11.8309 和 10.6239 之间（有 2-4 个线程） 这怎么可能呢？

4

1 回答 1

3

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

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

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

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

然后将每个“任务”一次又一次地拆分：

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

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

|--- 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 多处理器支持”。

在您的非并行版本中，这一切invalidating the cache不会（经常）发生，因为只有一个核心在积极处理数据。

因此，一个可能的解决方案是不要拆分任务，直到它们太小而无法由核心有效处理。您必须考虑的另一个影响：OpenMP 必须对management overhead每个任务执行一些操作。如果任务太小，您也可以增加overhead vs work比率。

谷歌吐出的基于 OpenMP 的快速排序是：

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

愿那能启发你。

于 2013-02-08T13:14:30.363 回答