粒子模拟的并行化OpenMP代码性能差

Question

我正在尝试并行化基于粒子的模拟代码，并且体验基于OpenMP的方法的性能较差。我的意思是:

• 使用Linux工具top显示CPU使用率，OpenMP-threads运行CPU的平均使用率为50%。
• 随着线程数量的增加，速度收敛到1.6倍左右。收敛速度非常快，也就是说，我使用2个线程达到了1.5的速度提升。

下面的伪代码演示了实现的所有并行区域的基本模板。请注意，在单个时间步骤中，将执行如下所示样式的5个并行区域。基本上，作用在粒子i < N上的力是邻近粒子j < NN(i)若干场性质的函数。

omp_set_num_threads(ncpu);
#pragma omp parallel shared( quite_a_large_amount_of_readonly_data, force )
{
   int i,j,N,NN;
   #pragma omp for 
    for( i=0; i<N; i++ ){             // Looping over all particles
       for ( j=0; j<NN(i); j++ ){     // Nested loop over all neighbors of i
          // No communtions between threads, atomic regions,
          // barriers whatsoever.
          force[i] += function(j);
       }
    }
}

我正试图找出观察到的瓶颈的原因。我最初天真的猜测:

如前所述，线程之间共享了大量用于只读访问的内存。很有可能不同的线程试图同时读取相同的内存位置。这会造成瓶颈吗?我应该让OpenMP分配私有副本吗?

Answer 1

N有多大，NN(i)有多密集?

你说没有共享，但是force[i]可能和force[i+1]在同一个缓存行。这就是所谓的虚假分享，可能非常有害。OpenMP应该批处理的东西在一起，以弥补这一点，所以有一个足够大的N，我不认为这将是你的问题。

如果NN(i)不是CPU密集型的，您可能会遇到简单的内存瓶颈——在这种情况下，向它投入更多的内核并不能解决任何问题。

Answer 2

假设force[i]是4或8字节数据的普通数组，那么毫无疑问，您肯定有虚假共享。

假设函数(j)是独立计算的，您可能想要这样做:

    for( i=0; i<N; i+=STEP ){             // Looping over all particles
       for ( j=0; j<NN(i); j+=STEP ){     // Nested loop over all neighbors of i
          // No communtions between threads, atomic regions,
          // barriers whatsoever.
       calc_next(i, j);
       }
    }

void calc_next(int i, int j)
{
    int ii, jj;
    for(ii = 0; ii < STEP; ii++)
    {
        for(jj = 0; jj < STEP; jj++)
        {
            force[i+ii] = function(j+jj);
        }
    }
}

这样，你在一个线程上计算一堆东西，在另一个线程上计算一堆东西，每一堆东西之间的距离足够远，你不会得到错误的共享。

如果你不能这样做，试着用其他方式把它分开，这样每次都要计算更大的部分。

Answer 3

正如其他人所说，force上的虚假分享可能是一个原因。用这种简单的方法试试

#pragma omp for 
for( i=0; i<N; i++ ){
   int sum = force[i];
   for ( j=0; j<NN(i); j++ ){
      sum += function(j);
   }
   force[i] = sum;
}

从技术上讲，force[i] = sum仍然有可能进行虚假共享。但是，这是极不可能发生的，因为另一个线程将访问force[i + N/omp_num_threads()*omp_thread_num()]，这离force[i]相当远。

如果可伸缩性仍然很差，尝试使用诸如英特尔并行放大器(或VTune)之类的分析器来查看每个线程需要多少内存带宽。如果是这样的话，在你的电脑里多放一些内存:)这将真正提高内存带宽。