使用 OpenMP 计算直方图 [英] Calculate the histogram with OpenMP

问题描述

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

I want to parallelize this code getting the best performance. "histogram" stores number of appareances of a certain colour (there are 10 different colours, so the size of histogram is 10). "img" is an array which stores a certain image information. In each index of img is stored a colour (int value, range 0..9). This is the code:

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

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

I tried this but the performance is so bad (worse than serial execution):

#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]]++;
  }
}

有什么建议吗?谢谢.

推荐答案

我已经在这里详细介绍了如何做到这一点并行填充直方图(数组缩减)使用 OpenMP 而不使用临界区

I already went into detail on how to to this here Fill histograms (array reduction) in parallel with OpenMP without using a critical section

它与数组缩减相同.OpenMP 在 C/C++ 中没有内置支持(但在 Fortran 中有)，所以你必须自己做.

It's the same as an array reduction. OpenMP does not have built in support for this in C/C++ (but it does in Fortran) so you have to do it yourself.

简单的解决方案是创建直方图的私有版本，并行填充它们，然后将它们合并为一个临界区中的直方图.在您的情况下，您可以这样做:

The easy solution is to create private version of the histogram, fill them in parallel, and them merge them into one histogram in a critical section. In your case you can do that like this:

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

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

It's possible to merge in parallel as well but that's more complicated. See the first link I mentioned for more details.

这篇关于使用 OpenMP 计算直方图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！