使用 OpenMP 进行缩减：线性合并或日志（线程数）合并

我有一个关于 OpenMP 缩减的一般性问题，这个问题困扰了我一段时间。我的问题是关于将部分金额合并到归约中。它可以线性地完成，也可以作为线程数的对数完成。

假设我想减少一些功能double foo(int i)。有了 OpenMP，我就可以这样做。

double sum = 0.0;    
#pragma omp parallel for reduction (+:sum)
for(int i=0; i<n; i++) {
    sum += f(i);
}

但是，我声称以下代码同样有效。

double sum = 0.0;
#pragma omp parallel
{
    double sum_private = 0.0;
    #pragma omp for nowait
    for(int i=0; i<n; i++) {
        sum_private += f(i)
    }
    #pragma omp critical
    {
        sum += sum_private;
    }
}

不是，第二个代码案例实际上具有相同的性能，但它更通用。它可以处理我定义的任何运算符，而归约构造仅适用于普通旧数据类型的一些基本运算符。

我们假设有t线程。我之所以声称第二种方法同样快，是因为与并行循环相比，合并部分和的时间可以忽略不计。进行部分求和的时间与n/t合并总和的时间为t。所以只要n>>t或执行并行循环所需的时间（如果foo与求和相比很慢）足够大，合并可以忽略不计。

我听说可以将部分总和合并O(log(t))。然而，出于所有实际目的，我不认为这有什么帮助。 OpenMP 中的最大物理核心数量为 50 个，我们假设为 64 个。与并行循环相比，以 64 个步骤或 8 个二进制步骤合并 64 个值不会有太大区别。此外，合并某种二叉树中的值可能会产生比仅进行线性合并更大的开销，因此它甚至不一定更快。

什么时候将部分和合并到O(log(t))有帮助过吗？第一个代码案例何时比第二个代码案例具有性能优势？

我认识一些同事O(log(t))在带有 OpenCL 的 GPU 上（通过为每个二进制合并运行几次内核），但我还没有看到任何证据表明它比仅仅线性合并更好。

Edit:吉姆·考尼（Jim Cownie）希望看到实际测试而不是声称。下面是结果和代码。这是在具有四个物理内核的 Xeon E5-1620 (Sandy Bridge) 上通过 MSVC2012 64 位发布模式完成的。第一种情况和第二种情况都比不使用 OpenMP 时快大约 4.45 倍。

结果：

without OpenMP time 1.787158 s
first case     time 0.400462 s
second case    time 0.400456 s

代码：

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>

double foo(int i) {
    double fi = i;
    return 1.0*fi/(1+fi*fi);
}

double reduce(int n) {
    double sum = 0.0f;
    for(int i=0; i<n; i++) {
        sum += foo(i);
    }
    return sum;
}

double reduce_omp(int n) {
    double sum = 0.0f;
    #pragma omp parallel for reduction(+:sum)
    for(int i=0; i<n; i++) {
        sum += foo(i);
    }
    return sum;
}

double reduce_omp2(int n) {
    double sum = 0.0f;
    #pragma omp parallel 
    {
        double sum_private = 0.0f;
        #pragma omp for nowait
        for(int i=0; i<n; i++) {
            sum_private += foo(i);
        }
        #pragma omp critical 
        {
            sum+= sum_private;
        }
    }
    return sum;
}

int main() {
    int n,r;
    double sum, dtime;
    n = 1<<28;
    r = 1;

    dtime = omp_get_wtime();
    for(int i=0; i<r; i++) sum = reduce(n);
    dtime = omp_get_wtime() - dtime;
    printf("time %f, sum %f\n", dtime, sum);

    reduce_omp(n);  //warm omp up

    dtime = omp_get_wtime();
    for(int i=0; i<r; i++) sum = reduce_omp(n);
    dtime = omp_get_wtime() - dtime;
    printf("time %f, sum %f\n", dtime, sum);

    dtime = omp_get_wtime();
    for(int i=0; i<r; i++) sum = reduce_omp2(n);
    dtime = omp_get_wtime() - dtime;
    printf("time %f, sum %f\n", dtime, sum);


}

OpenMP 实现将根据实现者对其运行的硬件的具体特征的了解来决定减少的最佳方法。在 CPU 数量较少的系统上，它可能会进行线性减少。在具有数百或数千个核心的系统（例如 GPU、Intel Phi）上，它可能会减少 log(n)。

对于非常大的问题，减少所花费的时间可能并不重要，但对于较小的问题，它可能会增加总运行时间的几个百分点。在许多情况下，您的实施可能同样快，但我怀疑它会更快，所以为什么不让 OpenMP 决定最佳缩减策略呢？