OpenMP 代码远比串行慢 - 内存或线程开销瓶颈？
OpenMP code far slower than serial - memory or thread overhead bottleneck?
我正在尝试并行化 (OpenMP) 一些科学 C++ 代码，其中 CPU 时间的大部分 (>95%) 花在了计算一个令人讨厌的（且不可避免的）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 的新手，所以非常感谢任何提示，如果有任何需要澄清的地方，请告诉我。
性能测量工具（如 Linux perf）可能会为您提供一些有关缓存性能或争用的信息；优化的第一步是衡量！
也就是说，我的猜测是这是一个数据布局问题以及速度更新的实现：每个线程在任何给定时间都试图加载与（本质上）随机叶关联的数据，这是缓存抖动的秘诀。叶子关联的数据有多大，在内存中是否相邻排列？
如果它确实是一个缓存问题（做测量！）那么它很可能通过平铺 N^2 问题来解决：而不是累积所有其他叶子贡献的速度增量，它们可以分批累积。出于此计算的目的，考虑将 N 个叶子分成 K 个批次，其中每批叶子数据适合（比方说）缓存的一半。然后迭代K^2对(A,B)批次，执行交互步骤，即计算批次B中所有叶子对批次A中叶子的贡献，这应该可以并行完成在 A 中的叶子上，而不破坏缓存。
确保叶子在内存中分批连续排列，可以获得更多收益。
您的问题很可能是虚假共享，因为您对节点使用了链表。使用这种内存布局，您不仅几乎每次将树走到另一个节点时都会遇到缓存未命中的问题（如 halfflat 所述）。
一个更严重的问题是，从不同线程访问和修改的树节点实际上可能在内存中很接近。如果它们共享一个缓存行，这意味着 false sharing（或 cache ping-pong）导致重复重新同步不同缓存行之间共享的缓存行线程。
这两个问题的解决方案是避免链接数据结构。它们几乎总是效率低下的原因。在您的情况下，解决方案是首先构建一个具有最少数据的链表树（仅定义树所需的数据），然后将其映射到另一个不使用链表且可能包含更多数据的树。这就是我所做的，树遍历相当快（树遍历永远不会真正快，因为即使有连续的姐妹节点，缓存未命中也是不可避免的，因为父女访问不能同时连续）。如果按照旧树的顺序将粒子添加到新树中（这避免了缓存未命中），则可以为树构建获得显着的加速（因子> 2）。
感谢您提供 link 原始来源！我已经能够在两个平台上编译并获得一些统计数据：带有 icpc 15.0 和 g++ 4.9.0 的 Xeon E5-2670；在 Core i7-4770 上，g++ 4.8.4.
在 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 开销，一些缩放很可能会丢失。
要点是任何共享资源都会阻碍可扩展性，包括堆。
可能与性能无关，但现在编写的代码具有奇怪的并行化结构。
我怀疑它能否产生正确的结果，因为 parallel 中的 while 循环没有障碍（omp master 没有障碍， omp for nowait 也有没有障碍）。
因此，(1) 线程可能会在主线程完成 Tree.PreProcessing() 之前开始 omp for 循环，某些线程实际上可能会在主线程工作之前执行 omp for 任意次数在单个预处理步骤上； (2) master 可能 运行 Tree.PropagatePositions() 在其他线程完成 omp for 之前； (3)不同的线程可能运行不同的时间步长； (4) 理论上主线程可能会在某些线程甚至进入并行区域之前完成 while 循环的所有步骤，因此 omp for 循环的某些迭代可能根本不会执行。
还是我遗漏了什么？
我正在尝试并行化 (OpenMP) 一些科学 C++ 代码，其中 CPU 时间的大部分 (>95%) 花在了计算一个令人讨厌的（且不可避免的）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 的新手，所以非常感谢任何提示，如果有任何需要澄清的地方，请告诉我。
性能测量工具（如 Linux perf）可能会为您提供一些有关缓存性能或争用的信息；优化的第一步是衡量！
也就是说，我的猜测是这是一个数据布局问题以及速度更新的实现：每个线程在任何给定时间都试图加载与（本质上）随机叶关联的数据，这是缓存抖动的秘诀。叶子关联的数据有多大，在内存中是否相邻排列？
如果它确实是一个缓存问题（做测量！）那么它很可能通过平铺 N^2 问题来解决：而不是累积所有其他叶子贡献的速度增量，它们可以分批累积。出于此计算的目的，考虑将 N 个叶子分成 K 个批次，其中每批叶子数据适合（比方说）缓存的一半。然后迭代K^2对(A,B)批次，执行交互步骤，即计算批次B中所有叶子对批次A中叶子的贡献，这应该可以并行完成在 A 中的叶子上，而不破坏缓存。
确保叶子在内存中分批连续排列，可以获得更多收益。
您的问题很可能是虚假共享，因为您对节点使用了链表。使用这种内存布局，您不仅几乎每次将树走到另一个节点时都会遇到缓存未命中的问题（如 halfflat 所述）。
一个更严重的问题是，从不同线程访问和修改的树节点实际上可能在内存中很接近。如果它们共享一个缓存行，这意味着 false sharing（或 cache ping-pong）导致重复重新同步不同缓存行之间共享的缓存行线程。
这两个问题的解决方案是避免链接数据结构。它们几乎总是效率低下的原因。在您的情况下，解决方案是首先构建一个具有最少数据的链表树（仅定义树所需的数据），然后将其映射到另一个不使用链表且可能包含更多数据的树。这就是我所做的，树遍历相当快（树遍历永远不会真正快，因为即使有连续的姐妹节点，缓存未命中也是不可避免的，因为父女访问不能同时连续）。如果按照旧树的顺序将粒子添加到新树中（这避免了缓存未命中），则可以为树构建获得显着的加速（因子> 2）。
感谢您提供 link 原始来源！我已经能够在两个平台上编译并获得一些统计数据：带有 icpc 15.0 和 g++ 4.9.0 的 Xeon E5-2670；在 Core i7-4770 上，g++ 4.8.4.
在 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 开销，一些缩放很可能会丢失。
要点是任何共享资源都会阻碍可扩展性，包括堆。
可能与性能无关，但现在编写的代码具有奇怪的并行化结构。
我怀疑它能否产生正确的结果，因为 parallel 中的 while 循环没有障碍（omp master 没有障碍， omp for nowait 也有没有障碍）。
因此，(1) 线程可能会在主线程完成 Tree.PreProcessing() 之前开始 omp for 循环，某些线程实际上可能会在主线程工作之前执行 omp for 任意次数在单个预处理步骤上； (2) master 可能 运行 Tree.PropagatePositions() 在其他线程完成 omp for 之前； (3)不同的线程可能运行不同的时间步长； (4) 理论上主线程可能会在某些线程甚至进入并行区域之前完成 while 循环的所有步骤，因此 omp for 循环的某些迭代可能根本不会执行。
还是我遗漏了什么？