OpenMP代码远比串行内存或线程开销瓶颈慢？

Question

我正在尝试并行化(OpenMP)一些科学的C++代码,其中大部分(> 95%)的CPU时间用于计算令人讨厌(且不可避免)的O(N ^ 2)交互,以便订购N~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的新手,所以任何提示都将不胜感激,如果有任何问题需要澄清,请告诉我.

Answer 1

感谢您提供原始来源的链接！我已经能够在两个平台上编译并获取一些统计数据：带有 icpc 15.0 和 g++ 4.9.0 的 Xeon E5-2670；以及配备 g++ 4.8.4 的 Core i7-4770。

在 Xeon 上，icpc 和 g++ 都生成随线程数量扩展的代码。我运行了一个从发行版中的 run.in 文件派生的缩短版（3e-7 秒）模拟：

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​​ 矢量数据，包括许多临时数据。这些都将访问堆，并且是潜在的争用源。Intel 的 openmp 实现使用线程本地堆来避免堆争用，也许 g++ 4.9 也是如此，而 g++-4.8.4 则不然？

我分叉了该项目（halfflat/vfmcppar在 github 上）并修改了这些文件以用于std::array<double,3>这些 3-d 向量；这可以恢复缩放，并且还可以提供更快的运行时间：

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 开销，一些缩放很可能会丢失。

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