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

英特尔的文档 https://software.intel.com/en-us/articles/openmp-loop-scheduling描述dynamic日程安排：

使用内部工作队列给出块大小的循环块 每个线程的迭代。当一个线程完成时，它会检索 从工作队列顶部开始的下一个循环迭代块。经过 默认情况下，块大小为1。使用此调度时要小心 类型，因为涉及额外的开销。

它还描述了guided日程安排：

与动态调度类似，但块大小一开始就很大并且 减少以更好地处理迭代之间的负载不平衡。这 可选的块参数指定要使用的最小大小块。经过 默认块大小约为loop_count/number_of_threads。

Since guided调度在运行时动态减少块大小，为什么我会使用dynamic安排？

我研究过这个问题并且从达特茅斯找到这张桌子 https://www.dartmouth.edu/~rc/classes/intro_openmp/schedule_loops.html:

guided被列为具有high开销，同时dynamic具有中等开销。

这最初是有道理的，但经过进一步调查，我阅读英特尔文章 https://software.intel.com/en-us/articles/performance-obstacles-for-threading-how-do-they-affect-openmp-code关于这个话题。根据上表，我推测guided由于在运行时分析和调整块大小（即使使用正确），调度将花费更长的时间。然而，英特尔文章中指出：

引导式调度以小块大小为限制时效果最佳；这 提供最大的灵活性。目前尚不清楚为什么他们的表现会变得更糟 更大的块大小，但是当限制为大时，它们可能需要很长时间 块大小。

为什么块大小与guided花费的时间长于dynamic？由于缺乏“灵活性”，通过将块大小锁定得太高而导致性能损失是有道理的。然而，我不会将其描述为“开销”，并且锁定问题会质疑先前的理论。

最后，文章中指出：

动态时间表提供了最大的灵活性，但也占用了最大的空间 当计划错误时，性能会受到影响。

这是有道理的dynamic调度比更优化static，但为什么它比guided？我所质疑的只是开销吗？

This 有点相关的SO帖子 https://stackoverflow.com/questions/10850155/openmp-for-schedule解释与调度类型相关的 NUMA。这与这个问题无关，因为这些调度类型的“先到先服务”行为会丢失所需的组织。

dynamic调度可能是合并的，导致性能提高，但同样的假设应该适用于guided.

以下是英特尔文章中不同块大小的每种调度类型的时序，以供参考。它只是来自一个程序的记录，并且某些规则适用于每个程序和机器（尤其是调度），但它应该提供总体趋势。

EDIT（我的问题的核心）：

• 什么影响了运行时间guided安排？具体例子？为什么比慢dynamic在某些情况下？
• 我什么时候会青睐guided over dynamic或相反亦然？
• 解释完毕后，上述来源是否支持您的解释？它们完全矛盾吗？

什么影响引导调度的运行时间？

需要考虑三个影响：

1.负载均衡

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

• schedule(dynamic, 1)提供最佳负载平衡
• dynamic, k总会有相同或更好负载均衡比guided, k

该标准规定每个块的大小是成比例的未分配迭代的数量除以团队中的线程数量， 减少到k.

The GCC OpenMP 实施 https://github.com/gcc-mirror/gcc/blob/1cb6c2eb3b8361d850be8e8270c597270a1a7967/libgomp/iter.c从字面上理解，忽略成比例的。例如，对于 4 个线程，k=1，它将进行 32 次迭代8, 6, 5, 4, 3, 2, 1, 1, 1, 1。现在恕我直言，这真的很愚蠢：如果前 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);
    }
}

The execution looks like this¹:

如你看到的，guided这里确实很糟糕。guided对于不同类型的工作分配会做得更好。也可以以不同的方式实施引导。 clang 中的实现（IIRC 源自 Intel）是更加复杂 https://github.com/llvm-mirror/openmp/blob/9c1e6c9bc10be652b92c40129c43c027aadc57b6/runtime/src/kmp_dispatch.cpp。我真的不明白 GCC 幼稚的实现背后的想法。在我看来，如果您给出，它实际上就违背了动态负载平衡的目的1/n工作到第一个线程。

2. 开销

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

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

3. 缓存和 NUMA 效果

假设在循环迭代中写入整数向量。如果每隔一个迭代由不同的线程执行，则向量的每个第二个元素都将由不同的内核写入。这真的很糟糕，因为这样做会竞争包含相邻元素的缓存行（错误共享）。如果您的块大小较小和/或块大小与缓存不能很好地对齐，则块的“边缘”性能会很差。这就是为什么你通常更喜欢大的好（2^n) 块大小。guided平均可以给你更大的块大小，但不是2^n (or k*m).

这个答案 https://stackoverflow.com/a/10852852/620382（您已经引用过），详细讨论了 NUMA 方面的动态/引导调度的缺点，但这也适用于局部性/缓存。

不要猜测，要测量

考虑到各种因素和预测细节的难度，我只能建议使用特定的编译器在特定的系统上、特定的配置中测量特定的应用程序。不幸的是没有完美的性能可移植性。我个人认为，这对于guided.

我什么时候会喜欢引导而不是动态，反之亦然？

如果您对每次迭代的开销/工作量有具体的了解，我会说dynamic, k选择好的产品会给您最稳定的结果k。特别是，您不太依赖于实现的巧妙程度。

另一方面，guided可能是一个很好的初步猜测，具有合理的开销/负载平衡比，至少对于巧妙的实现而言。要特别小心guided如果您知道以后的迭代时间会更短。

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

解释完毕后，上述来源是否支持您的解释？它们完全矛盾吗？

对来源（包括这只雁）持保留态度。您发布的图表和我的时间线图片都不是科学上准确的数字。结果存在巨大差异，并且没有误差线，它们可能会因为这些很少的数据点而到处都是。该图表还结合了我提到的多种效果，但没有透露Work code.

[来自英特尔文档]

默认情况下，块大小约为loop_count/number_of_threads。

这与我的观察相矛盾，即 icc 可以更好地处理我的小例子。

^{1: Using GCC 6.3.1, Score-P / Vampir for visualization, two alternating work functions for coloring.}