python - OpenMP/Cython 中的空闲线程是否可以用于并行化工作 block 的剩余部分？

Question

我是 OpenMP 的新手，并使用它来并行化 for 循环(准确地说，我在 Cython 中使用 prange)。

但是，操作非常不均匀，因此在 for 循环的一个 block 完成之前，有相当多的空闲线程。

我想知道是否有一种方法可以访问空闲线程，以便我可以使用它们来并行处理瓶颈操作。

Answer 1

这个问题归结为完美调度任务的问题，这对于一般情况来说是相当困难的，所以通常会退回到启发式方法。

OpenMP 提供了不同的调度启发式方法，可以通过 schedule 参数选择 prange ( documentation )。

让我们看下面的例子:

%%cython -c=/openmp --link-args=/openmp
cdef double calc(int n) nogil:
    cdef double d=0.0
    cdef int i
    for i in range(n):
        d+=0.1*i*n
    return d

def single_sum(int n):
    cdef int i
    cdef double sum = 0.0
    for i in range(n):
        sum += calc(i)
    return sum

calc 的评估需要 O(n)，因为符合 IEEE 754 的编译器无法优化 for 循环。

现在让我们用prange替换range:

...
from cython.parallel import prange   
def default_psum(int n):
    cdef int i
    cdef double sum = 0.0
    for i in prange(n, nogil=True, num_threads=2):
        sum += calc(i)
    return sum

我选择将线程数限制为 2，以使效果更显着。现在，比较我们看到的运行时间:

N=4*10**4
%timeit single_sum(N) #no parallelization
# 991 ms ± 2.37 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit default_psum(N) #parallelization
# 751 ms ± 11.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

没有我们想要的那么多改进(即我们想要加速 2)!

它是 OpenMP-provider 的一个实现细节，当它没有明确设置时选择哪个时间表 - 但很可能它将是 “static” 而没有定义 chunksize .在这种情况下，范围减半，一个线程成为第一个，快速的一半，而另一个线程成为第二个，其中几乎所有的工作都必须完成——所以很大一部分工作最终没有并行化。

实现更好平衡的更好策略是给第一个线程i=0，给第二个线程i=1，i=2 再次回到第一个，依此类推。对于 "static"-schedule，这可以通过将 chunksize 设置为 1 来实现:

def static_psum1(int n):
    cdef int i
    cdef double sum = 0.0
    for i in prange(n, nogil=True, num_threads=2, schedule="static", chunksize=1):
        sum += calc(i)
    return sum

我们几乎达到了 2 的最大可能加速:

%timeit static_psum1(N)
# 511 ms ± 13.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

选择最佳调度是调度开销(在上面的示例中不是很高)和最佳工作平衡之间的权衡 - 只有在分析问题(和硬件!)之后才能实现最佳权衡手。

下面是上面例子针对不同调度策略和不同线程数的一些时序:

(schedule,chunksize)        N=2                  N=8
single-threaded            991 ms               991 ms
(default)                  751 ms               265 ms
static                     757 ms               274 ms
static,1                   511 ms               197 ms
static,10                  512 ms               166 ms
dynamic,1                  509 ms               158 ms
dynamic,10                 509 ms               156 ms
guided                     508 ms               158 ms

---

只有在理论上至少有可能实现良好平衡时，尝试使用不同的时间表才有意义。

如果有一个任务占用了 90% 的运行时间，那么无论使用哪种调度策略，都不可能提高性能。在这种情况下，大任务本身应该并行化，遗憾的是 Cython 对 OpenMP 的支持有点缺乏(例如参见 SO-post )，因此最好用纯 C 编写代码，然后用 Cython 包装生成的功能。