可以使用OpenMP / Cython中的空闲线程来并行化工作块的其余部分吗？

Question

我是OpenMP的新手，并使用它并行化一个for循环（准确地说，我在Cython中使用prange）。

但是，操作非常不均匀，因此，有很多空闲线程，直到完成for循环的一个块为止。

我想知道是否存在访问空闲线程的方法，以便可以使用它们并行化瓶颈操作。

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循环。

现在让我们将range替换为prange：

...
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提供程序的实现细节，如果未明确设置时间表，则选择该时间表-但很可能是"static"而未定义chunksize。在这种情况下，范围减半，一个线程成为第一个快速的一半，而另一个线程则成为第二个线程，几乎所有工作都必须完成-因此大部分工作最终都不会并行化。

获得更好平衡的更好策略是将i=0赋予第一个线程，将i=1赋予第二个线程，再将i=2赋予第一个线程，依此类推。通过将"static"设置为1，可以实现chunksize计划：

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