使用 OpenMP 计算直方图

Question

我想并行化此代码以获得最佳性能。 “histogram”存储某种颜色出现的次数（有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

我已经在这里详细介绍了如何做到这一点 与 OpenMP 并行填充直方图（数组缩减），无需使用关键部分

与数组缩减相同。 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];
    }
}

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

Answer 2

使用 OpenMP 4.5，您可以简单地在 C: 中使用数组缩减

int histogram[BINS] = {0};
#pragma omp parallel for reduction(+:hist)
for(i=0; i<N1; i++) {
   for(j=0; j<N2; j++) {    
       histogram[img[i][j]]++;
   }
}

Answer 3

您想要创建一种“减少”，因此每个线程应该有自己的直方图数组，并且您必须在第二个循环中合并所有直方图......请参见下面的伪代码：

histogram = new int[256];
histogram_thread = new int[nbthread * 256];

#pragma omp parallel 
for(i=0; i<N1; i++){
  current_thread_id = omp_get_thread_num();
  for(j=0; j<N2; j++)
  {
    histogram_thread[current_thread_id*256 + img[i][j]]++;
  }
}

//merge
for(unsigned int ui = 0 ; ui < 256 ; ++ui)
{ 
   for(int t=0; t<nbthread ; ++t) 
   {
      histogram [i] += histogram_thread[t * 256 + i];
   }
}

delete [] histogram_thread;

Answer 4

我遇到了同样的问题，制作了一种算法，对图像（在 [0;255] 区域中具有 RGB 值）应用自动色阶变换来调整对比度。

这是我的直方图部分的解决方案：

int hist[256] = {0};

#pragma omp parallel shared(img, hist)
{
    int hist_thread[256] = {0};
    #pragma omp for schedule(static)
    for (int i = 0; i < img.data_size; i++) {
        hist_thread[img.data[i]]++;
    }
    for (int i = 0; i < 256; i++) {
        #pragma omp atomic
        hist[i] += hist_thread[i];
    }
}