OpenMP动态与引导式调度

Question

我正在研究OpenMP的调度,特别是不同的类型.我理解每种类型的一般行为,但澄清将有助于何时选择dynamic和guided安排.

英特尔的文档描述了dynamic调度:

使用内部工作队列为每个线程提供一个块大小的循环迭代块.线程完成后,它会从工作队列的顶部检索下一个循环迭代块.默认情况下,块大小为1.使用此调度类型时要小心,因为涉及额外的开销.

它还描述了guided调度:

与动态调度类似,但块大小从大开始减小以更好地处理迭代之间的负载不平衡.可选的chunk参数指定它们使用的最小大小块.默认情况下,块大小约为loop_count/number_of_threads.

由于guided调度在运行时动态地减少了块大小,为什么我会使用dynamic调度？

我研究过这个问题,从达特茅斯找到了这张桌子:

guided被列为具有high开销,同时dynamic具有中等开销.

这最初是有意义的,但经过进一步调查,我读了一篇关于该主题的英特尔文章.从上一张表中可以看出,guided由于在运行时分析和调整块大小(即使正确使用),理论调度也会花费更长的时间.但是,在英特尔文章中它指出:

引导时间表最适合小块大小作为其限制; 这提供了最大的灵活性.目前尚不清楚为什么它们在更大的块尺寸下会变得更糟,但是当它们被限制在大块尺寸时它们可能会花费太长时间.

为什么块大小与guided花费更长时间相关dynamic？通过将块大小锁定得太高而导致性能损失缺乏"灵活性"是有意义的.但是,我不会将其描述为"开销",锁定问题会破坏先前的理论.

最后,它在文章中说明:

动态计划提供了最大的灵活性,但在计划错误时可以获得最大的性能影响.

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

这个有点相关的SO帖子解释了与调度类型相关的NUMA.这与此问题无关,因为所需的组织因这些调度类型的"先到先得"行为而丢失.

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

以下是英特尔文章中不同块大小的每种调度类型的时序,以供参考.它只是来自一个程序的记录,一些规则适用于每个程序和机器(特别是调度),但它应该提供一般趋势.

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

• 是什么影响了guided调度的运行时间？具体例子？为什么它比dynamic某些情况慢？
• 我什么时候会偏爱guided,dynamic反之亦然？
• 一旦解释了这个,上面的来源是否支持您的解释？他们完全矛盾吗？

Answer 1

是什么影响了引导式调度的运行时？

需要考虑三种效果:

1.负载平衡

动态/引导调度的重点是在每个循环迭代不包含相同工作量的情况下改进工作分配.从根本上说:

• 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的工作,则会导致负载不平衡.

具体例子？在某些情况下,为什么它比动态慢？

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

#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源于英特尔)的实现要复杂得多.我真的不明白GCC天真实施背后的想法.在我看来,如果你给1/n第一个线程工作,它有效地破坏了动态负载消除的目的.

2.开销

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

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

3.缓存和NUMA效果

假设在循环迭代中写入整数向量.如果每个第二次迭代要由不同的线程执行,则向量的每个第二个元素将由不同的核心写入.这真的很糟糕,因为通过这样做,他们竞争包含相邻元素的缓存行(虚假共享).如果您的小块大小和/或块大小不能很好地与缓存对齐,则会在块的"边缘"处获得不良性能.这就是为什么你通常喜欢大的nice(2^n)块大小.guided可以平均给你更大的块大小,但不能2^n(或k*m).

这个答案(你已经引用过),详细讨论了NUMA方面的动态/引导调度的缺点,但这也适用于locality/caches.

不要猜测,衡量

鉴于预测细节的各种因素和难度,我只建议使用您的特定编译器在您的特定系统,特定配置中测量您的特定应用程序.不幸的是,没有完美的性能可移植性.我个人认为,这尤其如此guided.

我什么时候会喜欢引导动态,反之亦然？

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

另一方面,guided可能是一个很好的初步猜测,具有合理的开销/负载平衡比,至少对于一个聪明的实现.guided如果您知道以后的迭代时间更短,请特别小心.

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

一旦解释了这个,上面的来源是否支持您的解释？他们完全矛盾吗？

拿一些来源,包括这个anser,用一粒盐.您发布的图表和我的时间线图片都不是科学上准确的数字.结果存在巨大差异,并且没有误差条,它们可能只是在这些极少数据点的地方.此图表结合了我提到的多种效果,但没有透露Work代码.

[来自英特尔文档]

默认情况下,块大小约为loop_count/number_of_threads.

这与我的观察结果相矛盾,即icc更好地处理我的小例子.

^{1:使用GCC 6.3.1,Score-P/Vampir进行可视化,两个交替的工作功能用于着色.}