OpenMP的实现让我的代码变得很慢

我想通过使用openMP让我的quicksort工作并行。在执行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和我停止之前printf主计时器。线程数量被定义为10（我用我的电脑上的4,2和1尝试过）。排序的列表，包括0之间1个000 000随机整数后我的结果 - 100：

时间（无OPENMP）是介乎6.48004 - 5.32001

使用OpenMP时间是介乎11.8309和10.6239（2-4线程）这怎么可能是真的？

来源

2013-02-08 Max Mansour

https://fgiesen.wordpress.com/2013/01/31/cores-dont-like-to-share/也许是首发。 – akira

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

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

元素列表被分成2项任务：

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

以及各自的“任务”，然后一次又一次地分裂，再次：

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

现在，CPU喜欢处理紧密在一起的数据。但是，如果每个内核一起处理数据PRETTY closeley，则可能是一个内核写入与另一个内核上的数据位于同一缓存行的大块数据。由于您不希望核心彼此写入数据，因此第一次写入将使其他核心中的数据无效，因此其他核心必须再次获取大块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多处理器支持”。

整个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-08 13:14:30 akira

OpenMP的实现让我的代码变得很慢

回答

相关问题