OpenMP 动态与引导调度
OpenMP Dynamic vs Guided Scheduling
我正在研究 OpenMP 的调度，特别是不同的类型。我了解每种类型的一般行为，但澄清一下何时在 dynamic 和 guided 调度之间进行选择会有所帮助。
Intel's docs 描述 dynamic 调度：
Use the internal work queue to give a chunk-sized block of loop
iterations to each thread. When a thread is finished, it retrieves the
next block of loop iterations from the top of the work queue. By
default, the chunk size is 1. Be careful when using this scheduling
type because of the extra overhead involved.
它还描述了 guided 调度：
Similar to dynamic scheduling, but the chunk size starts off large and
decreases to better handle load imbalance between iterations. The
optional chunk parameter specifies them minimum size chunk to use. By
default the chunk size is approximately loop_count/number_of_threads.
既然 guided 调度会在运行时动态减小块大小，我为什么要使用 dynamic 调度？
我研究过这个问题 found this table from Dartmouth:
guided 被列为具有 high 开销，而 dynamic 具有中等开销。
这最初是有道理的，但经过进一步调查，我 read an Intel article 了解了这个话题。从之前的 table 来看，我推测 guided 调度会花费更长的时间，因为在运行时（即使正确使用）分析和调整块大小。但是，在英特尔文章中指出：
Guided schedules work best with small chunk sizes as their limit; this
gives the most flexibility. It’s not clear why they get worse at
bigger chunk sizes, but they can take too long when limited to large
chunk sizes.
为什么块大小与 guided 相关的时间比 dynamic 长？缺少 "flexibility" 通过将块大小锁定得太高而导致性能损失是有道理的。但是，我不会将此描述为 "overhead"，并且锁定问题会抹黑先前的理论。
最后，文章中说到：
Dynamic schedules give the most flexibility, but take the biggest
performance hit when scheduled wrong.
dynamic 调度比 static 更优是有道理的，但为什么它比 guided 更优？我质疑的只是开销吗？
这篇somewhat related SO post解释了与调度类型相关的NUMA。这与这个问题无关，因为这些调度类型的 "first come, first served" 行为丢失了所需的组织。
dynamic 调度可能是合并的，导致性能提升，但同样的假设应该适用于 guided。
这里是英特尔文章中不同块大小的每种调度类型的时间，供参考。它只是来自一个程序的记录，一些规则适用于每个程序和机器（尤其是调度），但它应该提供总体趋势。
编辑（我的问题的核心）：
- 什么会影响
guided 调度的运行时间？具体例子？为什么在某些情况下它比 dynamic 慢？
- 我什么时候更喜欢
guided 而不是 dynamic 或相反？
- 解释完后，以上来源是否支持您的解释？他们完全矛盾吗？
What affects the runtime of guided scheduling?
需要考虑三种影响：
1。负载平衡
dynamic/guided 调度的重点是在每个循环迭代包含的工作量不同的情况下改善工作分配。基本面：
schedule(dynamic, 1) 提供 最佳负载平衡dynamic, k 将始终具有 与 guided, k
标准规定每个块的大小与未分配的迭代数除以团队中的线程数成正比，
减少到 k.
GCC OpenMP implemntation 按字面意思理解，忽略 比例 。例如，对于 4 个线程 k=1，它将进行 32 次迭代 8, 6, 5, 4, 3, 2, 1, 1, 1, 1。现在恕我直言，这真的很愚蠢：如果前 1/n 次迭代包含超过 1/n 的工作，则会导致严重的负载不平衡。
Specific examples? Why is it slower than dynamic in some cases?
好的，让我们看一个简单的例子，其中内部工作随着循环迭代而减少：
#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);
}
}
执行看起来像这样1:
如您所见，guided 在这里确实很糟糕。 guided 对于不同类型的工作分配会做得更好。也可以不同地实施引导。 clang 中的实现（IIRC 源于 Intel）是 much more sophisticated。我真的不明白 GCC 天真的实现背后的想法。在我看来，如果您将 1/n 工作分配给第一个线程，它会有效地破坏动态负载平衡的目的。
2。开销
现在，由于访问共享状态，每个动态块都会对性能产生一些影响。 guided 每个块的开销会比 dynamic 略高，因为需要做更多的计算。但是，guided, k 的动态块总数将少于 dynamic, k。
开销也将取决于实现，例如它是使用原子还是锁来保护共享状态。
3。缓存和 NUMA 效果
假设在循环迭代中写入一个整数向量。如果每隔一个迭代由不同的线程执行，则向量的每个第二个元素将由不同的核心写入。这真的很糟糕，因为这样做会竞争包含相邻元素的缓存行（错误共享）。如果您的块大小 and/or 不能很好地与缓存对齐，那么您在 "edges" 块处的性能会很差。这就是为什么您通常更喜欢大的 nice (2^n) 块大小。 guided 可以平均给你更大的块大小，但不能 2^n（或 k*m）。
This answer（您已经引用过）详细讨论了 dynamic/guided 调度在 NUMA 方面的缺点，但这也适用于 locality/caches。
不要猜测，测量
考虑到各种因素和预测细节的难度，我只能建议测量您的特定应用程序，在您的特定系统上，在您的特定配置中，使用您的特定编译器。不幸的是，没有完美的性能可移植性。我个人认为，guided.
尤其如此
When would I favor guided over dynamic or vice-versa?
如果您对开销/每次迭代的工作量有具体了解，我会说 dynamic, k 通过选择好的 k 为您提供最稳定的结果。特别是，您不必太依赖实现的巧妙程度。
另一方面，guided 可能是一个很好的初步猜测，具有合理的开销/负载平衡比率，至少对于巧妙的实施而言。如果您知道以后的迭代时间更短，请特别注意 guided。
请记住，还有 schedule(auto)，它可以完全控制 compiler/runtime，以及 schedule(runtime)，它允许您 select 调度策略运行时间。
Once this has been explained, do the sources above support your explanation? Do they contradict at all?
对源代码（包括这个 anser）持保留态度。您发布的图表和我的时间线图片都不是科学上准确的数字。结果差异很大，而且没有误差线，它们可能只是用这些非常少的数据点到处都是。此外，该图表结合了我提到的多种效果，但没有公开 Work 代码。
[来自英特尔文档]
By default the chunk size is approximately loop_count/number_of_threads.
这与我观察到 icc 能更好地处理我的小示例相矛盾。
1：使用GCC 6.3.1，Score-P / Vampir 进行可视化，两个交替功函数进行着色。
我正在研究 OpenMP 的调度，特别是不同的类型。我了解每种类型的一般行为，但澄清一下何时在 dynamic 和 guided 调度之间进行选择会有所帮助。
Intel's docs 描述 dynamic 调度：
Use the internal work queue to give a chunk-sized block of loop iterations to each thread. When a thread is finished, it retrieves the next block of loop iterations from the top of the work queue. By default, the chunk size is 1. Be careful when using this scheduling type because of the extra overhead involved.
它还描述了 guided 调度：
Similar to dynamic scheduling, but the chunk size starts off large and decreases to better handle load imbalance between iterations. The optional chunk parameter specifies them minimum size chunk to use. By default the chunk size is approximately loop_count/number_of_threads.
既然 guided 调度会在运行时动态减小块大小，我为什么要使用 dynamic 调度？
我研究过这个问题 found this table from Dartmouth:
guided 被列为具有 high 开销，而 dynamic 具有中等开销。
这最初是有道理的，但经过进一步调查，我 read an Intel article 了解了这个话题。从之前的 table 来看，我推测 guided 调度会花费更长的时间，因为在运行时（即使正确使用）分析和调整块大小。但是，在英特尔文章中指出：
Guided schedules work best with small chunk sizes as their limit; this gives the most flexibility. It’s not clear why they get worse at bigger chunk sizes, but they can take too long when limited to large chunk sizes.
为什么块大小与 guided 相关的时间比 dynamic 长？缺少 "flexibility" 通过将块大小锁定得太高而导致性能损失是有道理的。但是，我不会将此描述为 "overhead"，并且锁定问题会抹黑先前的理论。
最后，文章中说到：
Dynamic schedules give the most flexibility, but take the biggest performance hit when scheduled wrong.
dynamic 调度比 static 更优是有道理的，但为什么它比 guided 更优？我质疑的只是开销吗？
这篇somewhat related SO post解释了与调度类型相关的NUMA。这与这个问题无关，因为这些调度类型的 "first come, first served" 行为丢失了所需的组织。
dynamic 调度可能是合并的，导致性能提升，但同样的假设应该适用于 guided。
这里是英特尔文章中不同块大小的每种调度类型的时间，供参考。它只是来自一个程序的记录，一些规则适用于每个程序和机器（尤其是调度），但它应该提供总体趋势。
编辑（我的问题的核心）：
- 什么会影响
guided调度的运行时间？具体例子？为什么在某些情况下它比dynamic慢？ - 我什么时候更喜欢
guided而不是dynamic或相反？ - 解释完后，以上来源是否支持您的解释？他们完全矛盾吗？
What affects the runtime of guided scheduling?
需要考虑三种影响：
1。负载平衡
dynamic/guided 调度的重点是在每个循环迭代包含的工作量不同的情况下改善工作分配。基本面：
schedule(dynamic, 1)提供 最佳负载平衡dynamic, k将始终具有 与guided, k 相同或更好的 负载平衡
标准规定每个块的大小与未分配的迭代数除以团队中的线程数成正比，
减少到 k.
GCC OpenMP implemntation 按字面意思理解，忽略 比例 。例如，对于 4 个线程 k=1，它将进行 32 次迭代 8, 6, 5, 4, 3, 2, 1, 1, 1, 1。现在恕我直言，这真的很愚蠢：如果前 1/n 次迭代包含超过 1/n 的工作，则会导致严重的负载不平衡。
Specific examples? Why is it slower than dynamic in some cases?
好的，让我们看一个简单的例子，其中内部工作随着循环迭代而减少：
#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);
}
}
执行看起来像这样1:
如您所见，guided 在这里确实很糟糕。 guided 对于不同类型的工作分配会做得更好。也可以不同地实施引导。 clang 中的实现（IIRC 源于 Intel）是 much more sophisticated。我真的不明白 GCC 天真的实现背后的想法。在我看来，如果您将 1/n 工作分配给第一个线程，它会有效地破坏动态负载平衡的目的。
2。开销
现在，由于访问共享状态，每个动态块都会对性能产生一些影响。 guided 每个块的开销会比 dynamic 略高，因为需要做更多的计算。但是，guided, k 的动态块总数将少于 dynamic, k。
开销也将取决于实现，例如它是使用原子还是锁来保护共享状态。
3。缓存和 NUMA 效果
假设在循环迭代中写入一个整数向量。如果每隔一个迭代由不同的线程执行，则向量的每个第二个元素将由不同的核心写入。这真的很糟糕，因为这样做会竞争包含相邻元素的缓存行（错误共享）。如果您的块大小 and/or 不能很好地与缓存对齐，那么您在 "edges" 块处的性能会很差。这就是为什么您通常更喜欢大的 nice (2^n) 块大小。 guided 可以平均给你更大的块大小，但不能 2^n（或 k*m）。
This answer（您已经引用过）详细讨论了 dynamic/guided 调度在 NUMA 方面的缺点，但这也适用于 locality/caches。
不要猜测，测量
考虑到各种因素和预测细节的难度，我只能建议测量您的特定应用程序，在您的特定系统上，在您的特定配置中，使用您的特定编译器。不幸的是，没有完美的性能可移植性。我个人认为，guided.
When would I favor guided over dynamic or vice-versa?
如果您对开销/每次迭代的工作量有具体了解，我会说 dynamic, k 通过选择好的 k 为您提供最稳定的结果。特别是，您不必太依赖实现的巧妙程度。
另一方面，guided 可能是一个很好的初步猜测，具有合理的开销/负载平衡比率，至少对于巧妙的实施而言。如果您知道以后的迭代时间更短，请特别注意 guided。
请记住，还有 schedule(auto)，它可以完全控制 compiler/runtime，以及 schedule(runtime)，它允许您 select 调度策略运行时间。
Once this has been explained, do the sources above support your explanation? Do they contradict at all?
对源代码（包括这个 anser）持保留态度。您发布的图表和我的时间线图片都不是科学上准确的数字。结果差异很大，而且没有误差线，它们可能只是用这些非常少的数据点到处都是。此外，该图表结合了我提到的多种效果，但没有公开 Work 代码。
[来自英特尔文档]
By default the chunk size is approximately loop_count/number_of_threads.
这与我观察到 icc 能更好地处理我的小示例相矛盾。
1：使用GCC 6.3.1，Score-P / Vampir 进行可视化，两个交替功函数进行着色。