OpenMP性能

Question

首先,我知道经常会问这种[类型]问题,所以让我先说一下我尽可能多地阅读,但我仍然不知道这笔交易是什么.

我已经并行化了一个巨大的外部for循环.循环迭代次数各不相同,通常在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的事实有关吗？这一直是用8GB的内存运行 - 但我猜这不是问题.坦率地说,系统时间的大幅增加使得它看起来像线程可能会阻塞,但我不知道为什么会发生这种情况.

更新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)(Apple的GCC-4.2.1在启用OpenMP时抛出编译器错误,这就是为什么我直到现在还没有在本地并行编译和运行它.在Macbook上,您基本上可以看到您期望的趋势

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

我们看到两端的回报渺茫,尽管这并不奇怪,因为我们在这个测试数据上迭代的几个数据集有<16个成员(因此,我们生成16个线程,比如for-loop7个迭代) .

那么,现在问题仍然存在 - 为什么集群的性能会如此糟糕地降低.我今晚要尝试不同的四核linuxbox.该集群使用GNU-GCC 4.6.3编译,但我不能相信它本身会产生这样的差异吗？

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

更新4

天啊.我决定将我的Macbook Pro引导到Ubuntu(12.04)并重新运行代码.它全部运行(这有点令人放心)但我看到了在集群上看到的相同,奇怪的坏性能行为,以及数百万次futex调用的相同运行.鉴于我在Ubuntu和OSX中的本地机器之间的唯一区别是软件(我使用相同的编译器和库 - 可能是glibcOSX和Ubuntu 没有不同的实现!)我现在想知道这是否适用于Linux如何安排/分配线程.无论如何,在我的本地机器上使一切都变得容易一百万次,所以我要继续前进ltrace -f,看看我能找到什么.我为forks()一个单独的进程编写了一个关于簇的工作,并在运行时给出了完美的1/2,所以它绝对有可能让并行性变得......

Answer 1

因此,在进行了一些相当广泛的分析之后(感谢这篇关于gprof和gdb时间采样信息的帖子),其中包括编写一个大包装函数来生成用于分析的生产级代码,很明显,在绝大多数情况下,当我使用gdb中止了正在运行的代码并backtrace在STL <vector>调用中运行堆栈,以某种方式操作向量.

代码将一些向量parallel作为私有变量传递给该部分,这似乎工作正常.然而,在拔出所有向量并用数组替换它们(以及其他一些jiggery-pokery以使其工作)后,我看到了显着的加速.使用小型的人工数据集,速度接近完美(即,当您将一半时间的线程数加倍时),而对于真实数据集,速度提升并不是那么好,但这在上下文中完全有意义代码如何工作.

似乎无论出于何种原因(可能是实现中的一些静态或全局变量STL<vector>？),当有循环并行移动数十万次迭代时,会出现一些深层锁定,这种情况发生在Linux(Ubuntu 12.01和CentOS 6.2)中但不是在OSX中.

我真的很感兴趣,为什么我看到这种差异.是不是STL的实现方式有所不同(OSX版本是在GNU GCC 4.7下编译的,与Linux版本一样),还是与上下文切换有关(如Arne Babenhauserheide所建议的那样)

总之,我的调试过程如下:

• 从内部R进行初步分析以确定问题

• 确保没有static变量充当共享变量

• 与异形strace -f和ltrace -f其在识别锁定的罪魁祸首真的很有帮助

• 与异形valgrind寻找任何错误

• 尝试了各种组合的计划类型(自动,引导,静态,动态)和块大小.

• 尝试将绑定线程连接到特定处理器

• 通过为值创建线程本地缓冲区来避免错误共享,然后在结束时实现单个同步事件 for-loop

• 删除所有mallocing与freeing从并行区域内-没有这个问题不禁也提供了一个小加速

• 尝试过各种体系结构和操作系统 - 最终没有真正帮助,但确实表明这是一个Linux与OSX问题,而不是超级计算机与桌面系统

• 构建一个使用fork()调用实现并发的版本- 在两个进程之间具有工作负载.这减少了OSX和Linux上的时间,这很好

• 构建了一个数据模拟器来复制生产数据负载

• gprof分析

• gdb时间采样分析(中止和回溯)

• 注释掉矢量操作

• 如果这不起作用,Arne Babenhauserheide的链接看起来可能在OpenMP的内存碎片问题上有一些关键的东西