c++ - OpenMP动态与引导式计划

我正在研究OpenMP的调度，特别是不同类型的调度。我了解每种类型的一般行为，但澄清一下何时在dynamic和guided调度之间进行选择会有所帮助。

Intel's docs描述dynamic调度:



它还描述了guided调度:



由于guided调度会在运行时动态减小块大小，因此为什么要使用dynamic调度？

我研究了这个问题和found this table from Dartmouth:



列出guided具有high开销，而dynamic则具有中等开销。

最初这是有道理的，但经过进一步调查，我对该主题进行了read an Intel article设置。从上一张表中，我理论上的guided调度将花费更长的时间，因为在运行时(即使正确使用时)也会对块大小进行分析和调整。但是，在英特尔文章中指出:



为什么块大小与guided花费比dynamic更长的时间有关？缺乏“灵活性”会通过将块大小锁定得太大而导致性能损失，这是有道理的。但是，我不会将其描述为“开销”，并且锁定问题会使先前的理论失去信誉。

最后，在文章中对此进行了说明:



使dynamic调度比static更优化是有意义的，但是为什么它比guided更优化呢？只是我在质疑的开销吗？

此somewhat related SO post解释与调度类型有关的NUMA。这与该问题无关，因为所需的组织因这些调度类型的“先到先得”行为而丢失。
dynamic调度可能会合并，从而导致性能提高，但是对于guided来说，同样的假设也应适用。

这是英特尔文章中提供的跨不同块大小的每种调度类型的时间，以供引用。它只是来自一个程序的记录，并且某些规则对每个程序和计算机(特别是在计划中)的适用方式有所不同，但它应该提供总体趋势。



编辑(我的问题的核心):

是什么影响guided调度的运行时间？具体的例子？为什么在某些情况下它比dynamic慢？

什么时候比guided更喜欢dynamic，反之亦然？

在解释了这些内容之后，以上来源是否支持您的解释？他们有矛盾吗？

最佳答案

需要考虑三个影响:

1.负载平衡

动态/引导式调度的重点是在并非每个循环迭代都包含相同数量的工作的情况下改善工作分配。从根本上讲:

schedule(dynamic, 1)提供最佳负载平衡

dynamic, k将始终具有相同或更好的负载平衡，而不是guided, k

该标准要求每个块的大小为，比例为，即未分配的迭代次数除以团队中的线程数，
减少到k。

GCC OpenMP implemntation从字面上接受此值，而忽略了比例。例如，对于4个线程k=1，它将作为8, 6, 5, 4, 3, 2, 1, 1, 1, 1进行32次迭代。现在恕我直言，这确实很愚蠢:如果前1/n迭代包含工作量的1/n以上，则会导致严重的负载不平衡。



好的，让我们看一个简单的示例，其中内部工作随循环迭代而减少:

#include <omp.h>

void work(long ww) {
    volatile long sum = 0;
    for (long w = 0; w < ww; w++) sum += w;
}

int main() {
    const long max = 32, factor = 10000000l;
    #pragma omp parallel for schedule(guided, 1)
    for (int i = 0; i < max; i++) {
         work((max - i) * factor);
    }
}

执行如下所示:



如您所见，guided在这里确实很糟糕。 guided对于不同类型的工作分配将做得更好。也可以采用不同的引导方式。 clang中的实现(IIRC源自Intel)是much more sophisticated。我真的不理解GCC天真的实现背后的想法。在我看来，如果将1/n工作分配给第一个线程，它将有效地消除动态负载平衡的目的。

2.开销

现在，由于访问共享状态，每个动态块都会对性能产生一些影响。每个块的guided开销将比dynamic稍高，因为还有更多的计算要做。但是，guided, k的总动态块少于dynamic, k。

开销也将取决于实现方式，例如是否使用原子或锁来保护共享状态。

3.缓存效应和NUMA效应

假设您在循环迭代中写入整数 vector 。如果第二次迭代要由不同的线程执行，则 vector 的第二个元素将由不同的内核写入。这样做确实很糟糕，因为这样做会使它们竞争包含相邻元素的缓存行(错误共享)。如果块大小较小和/或块大小无法很好地与缓存对齐，则块的“边缘”会导致性能下降。这就是为什么您通常会选择较大的尼斯(2^n)块大小。 guided平均可以为您提供更大的块大小，但2^n(或k*m)则不能。

This answer(您已经引用过)从NUMA的角度详细讨论了动态/引导式调度的缺点，但这也适用于位置/缓存。

不要猜测，测量

考虑到各种因素和难以预测的细节，我仅建议您使用特定的编译器在特定的系统，特定的配置下测量特定的应用程序。不幸的是，没有完美的性能可移植性。我个人认为，guided尤其如此。



如果您对开销/每次迭代的工作有特定的了解，我想说dynamic, k通过选择一个好的k可以为您提供最稳定的结果。特别是，您不太依赖实现的巧妙程度。

另一方面，至少对于一个聪明的实现，guided可能是一个不错的第一选择，具有合理的开销/负载平衡比。如果您知道以后的迭代时间更短，请特别注意guided。

请记住，还有schedule(auto)和schedule(runtime)，它可以完全控制编译器/运行时，它可以在运行时选择调度策略。



用一粒盐拿起包括该分析药在内的各种来源。您发布的图表和我的时间轴图片都不是科学上准确的数字。结果差异很大，没有误差线，可能只有很少的数据点到处都是。该图表还结合了我提到的多种效果，而没有公开Work代码。

[摘自Intel docs]



这与我的观点相矛盾，后者认为icc可以更好地处理我的小例子。

1:使用GCC 6.3.1，Score-P/Vampir进行可视化，两个交替的工作功能进行着色。