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

Question

我试图并行化(OpenMP)一些科学的C++代码，其中大量(>95%)的CPU时间用于计算N~200阶不同粒子的讨厌(且不可避免的) O(N^2)交互作用。此计算重复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线程管理开销占主导地位，还是由于设计的数据层次结构没有考虑并行性？

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

我是OpenMP的新手，所以任何技巧都会非常感谢，如果有什么需要澄清的话，请告诉我。

Answer 1

感谢您提供到原始源的链接！我已经能够在两个平台上编译和获取一些统计数据:带有icpc 15.0和g++ 4.9.0的XeonE5-2670；以及带有g++ 4.8.4的Corei7-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

在核心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>变量存储三维矢量数据，包括许多临时变量。这些都将访问堆，并且是一个潜在的争用源。Intel的openmp实现使用线程本地堆来避免堆争用，也许g++ 4.9也是这样，而g++-4.8.4没有吗？

我对这个项目(github上的halfflat/vfmcppar)进行了分叉，并修改了这些文件，使其对这些三维向量使用std::array<double,3>；这将恢复缩放，并提供更快的运行时间：

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

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

Answer 2

您的问题很可能是错误共享，因为您对节点使用了链接列表。使用该内存布局，您不仅在每次将树遍历到另一个节点(如halfflat所述)时都会遇到缓存丢失的问题。

一个更严重的问题是，从不同线程访问和修改的树节点实际上可能在内存中关闭。如果它们共享缓存行，这意味着错误共享(或缓存ping-pong)会导致不同线程之间共享的缓存线的重复同步。

解决这两个问题的办法是避免链接数据结构。它们几乎总是造成低效率的原因。在您的示例中，解决方案是首先使用最少的数据(只需要定义树所需的数据)构建链接列表树，然后将其映射到另一棵不使用链接列表并可能包含更多数据的树。这就是我所做的，树遍历也是相当快的(树遍历永远不可能真的快，因为缓存丢失是不可避免的，即使是在相邻的姐妹节点上，因为父子访问不能同时是连续的)。如果按照旧树的顺序将粒子添加到新树中(这样可以避免缓存丢失)，则可以为树的构建获得显著的速度(factor>2)。

Answer 3

性能测量工具(如Linux )可能会为您提供一些关于缓存性能或争用的信息；优化的第一步是度量！

尽管如此，我的猜测是，这是一个数据布局问题，再加上速度更新的实现:在任何给定时间，每个线程都试图加载与(本质上)随机叶相关联的数据，这是缓存破坏的一种方法。与叶子相关的数据有多大，它们是否被安排在内存中相邻？

如果它确实是一个缓存问题(做度量！)然后，可以通过平铺N^2问题来解决这一问题:与其累积所有其他叶子所贡献的速度增量，不如将它们分批累积起来。考虑将N个叶子分割成K个批，以便进行此计算，其中每一批叶数据都符合(例如)您的缓存的一半。然后迭代批次的K^2对(A，B)，执行交互步骤，即计算批B中所有叶子对批A中叶子的贡献，这应该可以在A中的叶子上并行完成，而不需要破坏缓存。

进一步的收益可以通过确保叶子被安排成连续的记忆批处理。