OpenMP 动态调度 vs 导向式调度

Question

OpenMP 动态调度 vs 导向式调度

c++multithreadingparallel-processingopenmpscheduling

39

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

Intel的文档描述了dynamic调度：

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

它还描述了guided调度：

类似于动态调度，但块大小从大到小递减，以更好地处理迭代之间的负载不平衡。可选的块参数指定要使用的最小块大小。默认情况下，块大小约为loop_count/number_of_threads。

由于guided调度在运行时动态减少块大小，那么我为什么要使用dynamic调度呢？

我研究了这个问题，并在Dartmouth的这个表格中找到了答案:

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

这原本是有道理的，但经过进一步调查，我在Intel文章中阅读到了相关内容。从前面的表格可以看出，我猜测 guided 调度会需要更长的时间，因为在运行时需要对块大小进行分析和调整（即使使用正确）。然而，在这篇Intel文章中指出：

对于小的块大小，引导式调度表现最佳；这样可以获得最大的灵活性。不清楚为什么它们的表现在较大的块大小下会变差，但当限制到大块大小时，它们可能需要太长时间。

为什么块大小会影响 guided 比 dynamic 更耗时呢？如果将块大小锁定得太高，缺乏“灵活性”会导致性能损失，这是有道理的。但我不会将其描述为“开销”，而且锁定问题会否定之前的猜想。

最后，在文章中指出：

动态调度提供最大的灵活性，但当调度错误时会带来最大的性能损失。

对于 dynamic 调度比 static 更优秀，这是有道理的，但为什么它比 guided 更优秀呢？我是否只是在质疑开销呢？

这个与某种程度相关的SO帖子解释了与调度类型相关的NUMA。虽然这些调度类型的“先到先服务”行为会导致所需的组织被丢失，但这与本问题无关。

dynamic 调度可能是聚合的，从而提高性能，但相同的假设也适用于 guided。

以下是来自Intel文章的各种调度类型在不同块大小下的时间记录，供参考。这只是一个程序的记录，并且一些规则在不同的程序和机器上适用不同（特别是在调度方面），但它应该提供一般趋势。

编辑（我的问题的核心）：

guided调度的运行时间受什么影响？具体举例说明？为什么在某些情况下比dynamic慢？
何时会优先选择guided或dynamic，反之亦然？
一旦解释清楚，上述来源是否支持您的解释？它们是否存在矛盾之处？

- Matt Goodrich

我在理解你的问题核心方面遇到了一些困难。你能否尝试将其聚焦到更具体的方面？ - Zulan

是的，我不确定你具体在问什么。 - amchacon

2

@Zulan 我试图在问题底部列出我想知道的所有内容。如果这仍然对一个问题来说太多或令人困惑，请告诉我。 - Matt Goodrich

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Zulan · Accepted Answer

影响guided scheduling运行时间的因素有哪些？

需要考虑三个方面：

1. 负载平衡

动态/导引调度的核心目标是在循环迭代中每次包含的工作量不同的情况下，提高工作分配的效率。基本上：

- `schedule(dynamic, 1)` 提供了最优的负载平衡 - `dynamic, k` 的负载平衡总是等同或更好于 `guided, k`

标准规定每个块的大小与未分配的迭代次数除以团队中的线程数成比例，逐渐减少到 `k`。 GCC OpenMP实现字面上理解，忽略了比例。例如，对于4个线程，k=1，它将迭代32次，如下所示：8, 6, 5, 4, 3, 2, 1, 1, 1, 1。在我看来，这真的很愚蠢：如果前1 / n次迭代包含超过1 / n的工作量，它会导致负载不平衡。

具体例子？为什么在某些情况下比dynamic更慢？

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

#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 中的实现（我IRC来自Intel）更为复杂。我真的不理解GCC背后的天真实现的想法。在我看来，如果将1/n的工作交给第一个线程，它实际上会击败动态负载平衡的目的。

2.开销

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

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

3.缓存和NUMA效应

假设在您的循环迭代中写入一个整数向量。如果每隔一秒迭代由不同的线程执行，则向量的每个第二个元素将由不同的核心写入。这非常糟糕，因为这样做会竞争包含相邻元素的缓存行（伪共享）。如果您具有较小的块大小和/或不适合缓存的块大小，则在块的“边缘”处性能不佳。这就是为什么通常更喜欢大而好的（2 ^ n ）块大小的原因。guided可以给您平均较大的块大小，但不是 2 ^ n （或 k * m ）。此答案（您已经引用），详细讨论了动态/引导调度在NUMA方面的劣势，但这也适用于局部性/缓存。

不要猜测，要衡量

考虑到各种因素以及难以预测的具体情况，我只能建议在您特定的系统、配置和编译器上测量您的特定应用程序。不幸的是，没有完美的性能可移植性。我个人认为，对于guided来说，这尤其正确。

我何时会更喜欢guided而不是dynamic，反之亦然？

如果您对迭代的开销/工作有具体的了解，我会说选择一个好的k，dynamic, k会给您最稳定的结果。特别是，您不需要过多依赖于实现的聪明程度。

另一方面，如果您知道后续迭代时间较短，则guided可能是一个合理的第一选择，具有合理的开销/负载平衡比率，至少对于一个聪明的实现来说。如果您知道后续迭代时间较短，请特别小心guided。

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

一旦这个问题被解释清楚了，上述来源是否支持您的解释？它们是否存在任何矛盾？

请谨慎对待这些来源，包括这个回答。你发布的图表和我的时间轴图片都不是科学准确的数字。结果存在巨大差异，并且没有误差条，它们可能只是在这些非常少的数据点上到处乱跑。此外，该图表结合了我提到的多种效应，而没有披露“Work”代码。

[来自英特尔文档]

默认情况下，块大小约为循环计数/线程数。

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

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