OpenMP性能

Question

首先，我知道这类问题经常被问到，所以让我在开头说我已经尽可能多地阅读了，我仍然不知道这是什么交易。

我已经并行了一个巨大的外部循环。循环迭代的次数不同，通常在20-150个之间，但是循环体做了大量的工作，调用了许多本地密集的线性代数例程(如代码是源代码的一部分，而不是外部依赖项)。在循环体中有对这些例程的1000+调用，但是它们都是完全独立的，所以我认为它将是并行性的主要候选。循环代码是C++，但是它调用了许多用C语言编写的子程序。

代码看起来像这样；

<declare and initialize shared variables here>
#ifdef _OPENMP
#pragma omp parallel for                            \
  private(....)\
  shared(....)              \
  firstprivate(....) schedule(runtime)
#endif
  for(tst = 0; tst < ntest; tst++) {

     // Lots of functionality (science!)
     // Calls to other deep functions which manipulate private variables only
     // Call to function which has 1000 loop iterations doing matrix manipulation
     // With no exaggeration, there are probably millions 
     // of for-loop iterations in this body, in the various functions called. 
     // They also do lots of mallocing and freeing
     // Finally generated some calculated_values

     shared_array1[tst] = calculated_value1;
     shared_array2[tst] = calculated_value2;
     shared_array3[tst] = calculated_value3;

 } // end of parallel and for

// final tidy up

我认为，不应该有任何同步-线程访问共享变量的唯一时间是shared_arrays，并且它们访问那些数组中的唯一点，这些数组是由tst索引的。

问题是，当我增加线程数量时(在多核集群上！)我们看到的速度(我们调用这个循环5次)如下；

              Elapsed time   System time
 Serial:        188.149          1.031
 2 thrds:       148.542          6.788
 4 thrds:       309.586        424.037       # SAY WHAT?
 8 thrds:       230.290        568.166  
16 thrds:       219.133        799.780 

值得注意的是系统时间在2到4个线程之间的巨大跳跃，以及当我们从2到4个线程之间运行的时间加倍，然后慢慢减少。

我尝试了大量的OMP_SCHEDULE参数，但都没有成功。这与每个线程经常使用malloc/new和free/delete有关吗？这一直是运行与8 8GBs内存-但我想这不是一个问题。坦率地说，系统时间的巨大增加使得线程看起来可能会阻塞，但我不知道为什么会发生这种情况。

UPDATE 1我真的认为错误共享将是问题所在，所以重写代码，以便循环将其计算值存储在线程本地数组中，然后将这些数组复制到共享数组的末尾。遗憾的是，这并没有产生任何影响，尽管我自己也几乎不相信。

按照@cmeerw的建议，我运行了strace -f，在初始化之后，只有数百万行

[pid 58067] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58066] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)
[pid 58065] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)
[pid 57684] <... futex resumed> )       = 0
[pid 58067] <... futex resumed> )       = 0
[pid 58066] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58065] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58067] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58066] <... futex resumed> )       = 0
[pid 57684] futex(0x35ca58bb40, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid 58065] <... futex resumed> )       = 0
[pid 58067] <... futex resumed> )       = 0
[pid 57684] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)
[pid 58066] futex(0x35ca58bb40, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid 58065] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58066] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)
[pid 57684] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58065] <... futex resumed> )       = 0
[pid 58066] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 57684] <... futex resumed> )       = 0
[pid 58067] futex(0x35ca58bb40, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid 58066] <... futex resumed> )       = 0
[pid 58065] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58067] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)
[pid 58066] futex(0x35ca58bb40, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid 57684] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58065] <... futex resumed> )       = 0
[pid 58067] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58066] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)
[pid 57684] <... futex resumed> )       = 0
[pid 58067] <... futex resumed> )       = 0
[pid 58066] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58065] futex(0x35ca58bb40, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid 58066] <... futex resumed> )       = 0
[pid 58065] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)
[pid 58066] futex(0x35ca58bb40, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid 57684] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 58067] futex(0x35ca58bb40, FUTEX_WAIT_PRIVATE, 2, NULL <unfinished ...>
[pid 58066] <... futex resumed> )       = -1 EAGAIN (Resource temporarily unavailable)
[pid 58065] futex(0x35ca58bb40, FUTEX_WAKE_PRIVATE, 1 <unfinished ...>
[pid 57684] <... futex resumed> )       = 0

有人知道什么是什么吗？看起来线程的上下文切换方式太频繁了，还是只是阻塞和解除阻塞？当我将相同的实现设置为strace时，OMP_NUM_THREADS设置为0，这一点都没有得到。比较而言，使用1个线程时生成的日志文件为486 KB，使用4个线程时生成的日志文件为266 MB。

换句话说，并行版本调用一个额外的4170104行日志文件.

更新2

正如Tom建议的那样，我尝试将线程绑定到特定的处理器，但没有结果。我们使用的是OpenMP 3.1，所以我使用export OMP_PROC_BIND=true设置了环境变量。相同大小的日志文件和相同的时间框架。

更新3

情节更复杂了。到目前为止，我只对集群进行了分析，我通过Macports安装了GNU GCC 4.7，并第一次在我的Macbook上编译(用openMP) (当启用OpenMP时，苹果的GCC-4.2.1抛出一个编译器错误，这就是为什么到目前为止我还没有在本地并行编译和运行它)。在Macbook上，你基本上看到了你预期的趋势

                C-code time
 Serial:         ~34 seconds
 2 thrds:        ~21 seconds
 4 thrds:        ~14 seconds
 8 thrds:        ~12 seconds
16 thrds:         ~9 seconds

我们看到分叉返回到终点，但这并不令人惊讶，因为我们在这个测试数据上迭代的数据集有<16个成员(因此，我们正在为一个for-loop生成16个线程，比如一个具有7次迭代的线程)。

所以，现在的问题仍然存在--为什么集群的性能会如此严重的下降。今晚我要试穿另一个四核线箱。这个集群是用GNU 4.6.3编译的，但我不敢相信它本身会带来如此大的变化？

集群上既没有安装ltrace，也没有安装GDB (由于各种原因，我无法安装它们)。如果linuxbox提供了类似集群的性能，我将在那里运行相应的ltrace分析。

更新4

哦天啊。我决斗启动我的Macbook Pro到Ubuntu (12.04)，并重新运行代码。这一切都在运行(这有点让人放心)，但我看到了集群上相同的、奇怪的、性能不好的行为，以及数百万个futex调用的相同运行。考虑到我在Ubuntu中的本地机器和OSX中的唯一不同是软件(而且我使用的是相同的编译器和库--想必OSX和Ubuntu没有不同的glibc实现！)我现在想知道这是否与Linux如何调度/分发线程有关。无论如何，在我的本地机器上，一切都变得简单了一百万倍，所以我将继续进行ltrace -f，看看我能找到什么。我为集群编写了一份工作，其中forks()分离了一个单独的进程，并在运行时给出了一个完美的1/2，所以绝对有可能实现并行性.

Answer 1

因此，经过一些相当广泛的分析(感谢这个伟大的职位提供关于gprof的信息和使用gdb进行时间采样)，其中涉及编写一个大型包装函数来生成用于分析的生产级代码之后，很明显，在我用gdb中止运行的代码并运行backtrace时，堆栈处于STL <vector>调用中，在某种程度上操作向量。

代码将一些向量作为私有变量传递到parallel部分，这些变量似乎工作得很好。然而，在提取出所有的向量并用数组替换它们之后(以及一些其他的抖动-戳以使其工作)，我看到了一个显著的速度。对于小的、人工的数据集，速度提高几乎是完美的(也就是说，您将线程数量增加了一半时间)，而对于实际数据集，速度则不太好，但这完全符合代码工作方式的上下文。

似乎是出于任何原因(可能是STL<vector>实现中的一些静态或全局变量？)当循环并行地遍历数十万次迭代时，会有一些深度级别锁定，这在Linux (Ubuntu12.01和CentOS 6.2)中发生，但在OSX中却没有。

我真的很想知道为什么我会看到这种差异。STL是如何实现的(OSX版本与Linux版本一样是在GNU GCC 4.7下编译的)，还是与上下文切换有关(如Arne Babenhauserheide建议的那样)？

总之，我的调试过程如下；

• 从R内部进行初始分析以确定问题
• 确保没有static变量充当共享变量
• 使用strace -f和ltrace -f进行描述，这确实有助于识别锁定是罪魁祸首。
• 使用valgrind进行分析以查找任何错误
• 尝试了各种组合，用于调度类型(自动、引导、静态、动态)和块大小。
• 尝试将线程绑定到特定处理器
• 通过为值创建线程本地缓冲区来避免错误共享，然后在for-loop结束时实现单个同步事件。
• 从并行区域中删除了所有的mallocing和freeing -没有帮助解决这个问题，但确实提供了一个小的总体加速
• 在各种架构和OSses上进行了尝试--最终并没有真正的帮助，但是确实表明这是Linux和OSX之间的问题，而不是超级计算机和桌面计算机的问题。
• 构建一个使用fork()调用实现并发的版本--具有两个进程之间的工作负载。这使OSX和Linux的时间减少了一半，这是很好的。
• 构建了一个数据模拟器来复制生产数据负载。
• gprof剖面图
• gdb时间采样分析(中止和回溯)
• 注释向量运算
• 如果这不起作用，Arne Babenhauserheide链接看起来很可能在OpenMP内存碎片问题上有一些关键的东西。

Answer 2

如果没有重要的分析，很难确切地知道发生了什么，但是性能曲线似乎表明了虚假共享.

线程使用不同的对象，但这些对象恰好在内存中非常接近，它们落在同一条高速缓存线上，而缓存系统将它们作为一个块来处理，该块由一个硬件写锁有效地保护，硬件写锁一次只能容纳一个核心。

多布斯博士关于这一主题的伟大文章

http://www.drdobbs.com/go-parallel/article/217500206?pgno=1

特别是，这些例程正在执行大量malloc/free操作这一事实可能会导致这种情况。

一种解决方案是使用基于池的内存分配器，而不是默认的分配器，这样每个线程都倾向于从不同的物理地址范围分配内存。

Answer 3

由于线程实际上不交互，所以只需将代码更改为多处理即可。您只需要在最后传递消息，并且可以保证线程不需要同步任何东西。

下面是python3.2-代码，它基本上就是这样做的(出于性能原因，您可能不希望在python中这样做--或者将for -循环放入C-函数并通过cython绑定。您将从代码中了解为什么我在Python中显示它)：

from concurrent import futures
from my_cython_module import huge_function
parameters = range(ntest)
with futures.ProcessPoolExecutor(4) as e:
    results = e.map(huge_function, parameters)
    shared_array = list(results)

就这样。将进程数量增加到可以放入集群中的作业数量，并让每个进程只提交和监视作业，以扩展到任意数量的调用。

没有交互的巨大功能和小的输入值几乎需要多处理。一旦你有了这一点，切换到MPI (几乎无限制的缩放)并不太难。

在技术方面，Linux中的AFAIK上下文交换机相当昂贵(拥有大量内核空间内存的单块内核)，而在OSX或Hurd (Mach微内核)上则便宜得多。这可能解释了你在Linux上看到的大量系统时间，而不是OSX上的大量系统时间。