我正在尝试并行化 (OpenMP) 一些科学 C++ 代码，其中大部分 (>95%) 的 CPU 时间花在计算 N 阶的讨厌(且不可避免)O(N^2) 交互上~ 200 种不同的颗粒。该计算重复 1e10 个时间步长。我用 OpenMP 尝试了各种不同的配置，每一个都比串行代码慢一些(至少一个数量级)，并且随着额外的内核的添加，扩展性很差。

下面是相关代码的草图，具有代表性的虚拟数据层次结构 Tree->Branch->Leaf。每个 Leaf 对象存储自己的位置和当前和前三个时间步长的速度，等等。然后每个 Branch 存储一组 Leaf 对象，每个 Tree 存储一组 Branch 对象。这种数据结构非常适合复杂但 CPU 密集度较低的计算，这些计算也必须在每个时间步执行(需要几个月才能完善)。

#include <omp.h>

#pragma omp parallel num_threads(16) // also tried 2, 4 etc - little difference - hoping that placing this line here spawns the thread pool at the onset rather than at every step
{
while(i < t){
    #pragma omp master
    {
       /* do other calculations on single core, output etc.  */
       Tree.PreProcessing() 
       /* PreProcessing can drastically change data for certain conditions, but only at 3 or 4 of the 1e10 time steps */
       Tree.Output()
    }
    #pragma omp barrier
    #pragma omp for schedule(static) nowait
    for(int k=0; k < size; k++){
         /* do O(N^2) calc that requires position of all other leaves */
         Tree.CalculateInteraction(Branch[k]) 
    }
    /* return to single core to finish time step */
    #pragma omp master
    {
        /* iterate forwards */
        Tree.PropagatePositions()
        i++
    }
    #pragma omp barrier
}

很简单，CPU-hog 函数就是这样做的:

void Tree::CalculateInteraction(Leaf* A){
// for all branches B in tree{
       // for all leaves Q in B{
          if(condition between A and Q){skip}
          else{
                // find displacement D of A and Q 
                // find displacement L of A and "A-1"
                // take cross product of the two displacements
                // add the cross-product to the velocity of leaf A 
                for(int j(0); j!=3; j++){
                    A->Vel[j] += constant * (D_cross_L)[j];
                }

我的问题是，这种性能下降是由于 openMP 线程管理开销占主导地位，还是数据层次结构的设计没有考虑并行性？

我应该注意到，并行的每个步骤都比串行的时间长得多，这不是一些初始化开销问题；这两个版本已经针对需要 1 小时和 10 小时的计算进行了测试，并最终希望应用于可能需要 30 小时的串行计算(为此即使速度提高 2 倍也会非常有益)。此外，可能值得一提的是，我将 g++ 5.2.0 与 -fopenmp -march=native -m64 -mfpmath=sse -Ofast -funroll-loops 一起使用。

我是 OpenMP 的新手，所以非常感谢任何提示，如果有任何需要澄清的地方，请告诉我。

最佳答案

感谢您提供原始来源的链接!我已经能够在两个平台上编译并获得一些统计数据:带有 icpc 15.0 和 g++ 4.9.0 的 Xeon E5-2670；在 Core i7-4770 上，使用 g++ 4.8.4。

在 Xeon 上，icpc 和 g++ 生成的代码都随线程数缩放。我运行了一个缩短的(3e-7 秒)模拟，该模拟源自分发版中的 run.in 文件:

Xeon E5-2670 / icpc 15.0
threads   time   ipc
---------------------
1         17.5   2.17
2         13.0   1.53
4          6.81  1.53
8          3.81  1.52

Xeon E5-2670 / g++ 4.9.0
threads   time   ipc
---------------------
1         13.2   1.75
2          9.38  1.28
4          5.09  1.27
8          3.07  1.25

在 Core i7 上，我确实看到了您使用 g++ 4.8.4 观察到的丑陋缩放行为:

Core i7-4770 / g++ 4.8.4
threads   time   ipc
---------------------
1          8.48  2.41
2         11.5   0.97
4         12.6   0.73

第一个观察结果是某些特定于平台的因素会影响缩放。

我查看了 point.h和 velnl.cpp文件，并注意到您正在使用 vector<double>用于存储 3-d​​ vector 数据的变量，包括许多临时变量。这些都将访问堆，并且是潜在的争用源。 Intel 的 openmp 实现使用线程本地堆来避免堆争用，也许 g++ 4.9 也这样做，而 g++-4.8.4 没有？

我 fork 了项目(github 上的 halfflat/vfmcppar)并修改了这些文件以使用 std::array<double,3>对于这些 3-d vector ；这恢复了缩放比例，并且还提供了更快的运行时间:

Core i7-4770 / g++ 4.8.4
std::array implementation
threads   time   ipc
---------------------
1          1.40  1.54
2          0.84  1.35
4          0.60  1.11

我没有在适当长度的模拟上运行这些测试，因此由于设置和 i/o 开销，一些缩放很可能会丢失。

要点是任何共享资源都会阻碍可扩展性，包括堆。

关于c++ - OpenMP 代码远比串行慢 - 内存或线程开销瓶颈？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31947412/