c - 使用OpenMP计算直方图

Question

我想并行处理此代码以获得最佳性能。 “直方图”存储某种颜色的外观数(有10种不同的颜色，因此直方图的大小为10)。 “img”是存储特定图像信息的数组。在img的每个索引中存储一种颜色(int值，范围0..9)。这是代码:

for( i=0; i<N1; i++ ){
  for( j=0; j<N2; j++ ){
    histogram[ img[i][j] ]  = histogram[ img[i][j] ] + 1;
  }
}

我试过了，但是性能太差了(比串行执行差):

#pragma omp parallel for schedule(static, N1/nthreads) private(i,j)
for(i=0; i<N1; i++){
  for(j=0; j<N2; j++)
  {
    #pragma omp atomic
    histogram[img[i][j]]++;
  }
}

有什么建议？谢谢。

Answer 1

我已经在这里详细介绍了如何
Fill histograms (array reduction) in parallel with OpenMP without using a critical section

它与数组归约相同。 OpenMP在C / C++中没有对此的内置支持(但在Fortran中是)，因此您必须自己做。

一种简单的解决方案是创建直方图的私有版本，并行填充它们，然后将它们合并到关键部分中的一个直方图中。在您的情况下，您可以这样做:

int i, histogram[10];
for(i=0; i<10; i++) histogram[i] = 0;
#pragma omp parallel
{
    int i, j, histogram_private[10];
    for(i=0; i<10; i++) histogram_private[i] = 0;
    #pragma omp for nowait
    for(i=0; i<N1; i++) {
       for(j=0; j<N2; j++) {    
           histogram_private[img[i][j]]++;
       }
    }      
    #pragma omp critical 
    {
        for(i=0; i<10; i++) histogram[i] += histogram_private[i];
    }
}

也可以并行合并，但这更加复杂。有关更多详细信息，请参见我提到的第一个链接。