C++ OpenMP：嵌套循环，其中内部迭代器依赖于外部迭代器

Question

考虑以下代码：

#include <iostream>
#include <chrono>
#include <vector>
#include <numeric>
#include <cmath>
#include <omp.h>

using namespace std;

typedef std::chrono::steady_clock myclock;

double measure_time(myclock::time_point begin, myclock::time_point end)
{
    return std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count()/(double)1e6;
}

int main()
{
    int n = 20000;
    vector<double> v(n);
    iota(v.begin(), v.end(), 1.5);

    vector< vector<double> > D(n, vector<double>(n,0.0));

    myclock::time_point begin, end;

    begin = myclock::now();

    //#pragma omp parallel for collapse(2)
    //#pragma omp parallel for
    for(size_t i = 0; i < n - 1; i++){
        for(size_t j = i+1; j < n; j++){
            double d = sqrt(v[i]*v[i] + v[j]*v[j] + 1.5*v[i]*v[j]);
            D[i][j] = d;
            D[j][i] = d;
        }
    }

    end= myclock::now();
    double time = measure_time(begin, end);
    cout<<"Time: "<<time<<" (s)"<<endl;
    return 0;
}

用于编译：

g++ -std=c++11 -fopenmp -o main main.cpp

我获得了以下运行时间：

• 与#pragma omp parallel for collapse(2)：7.9425（秒）
• 与#pragma omp parallel for：3.73262（s）
• 没有 OpenGM：11.0935（秒）

系统设置：Linux Mint 18.3 64位，g++ 5.4.0，四核处理器。

我希望第一个比第二个更快（仅并行化外循环）并且比第三个快得多。

请问我做错了什么？第一个和第二个都在所有 8 个线程上运行。

预先感谢您的帮助！

Answer 1

当迭代依赖于另一个循环时，不应使用塌陷子句。请参阅了解 openmp 中的折叠子句。

在您的情况下，由于对称性，您正在遍历矩阵的下三角形（不包括对角线）。这将迭代次数大约减少了一半。如果您想融合/折叠双循环，您可以像这样手动完成（有关更多详细信息，请参阅此答案的末尾）。

for(size_t k=0; k<n*(n-1)/2; k++) {
    size_t i = k/n, j = k%n;
    if(j<=i) i = n - i - 2, j = n - j - 1;
    double d = sqrt(v[i]*v[i] + v[j]*v[j] + 1.5*v[i]*v[j]);
    D[i][j] = d;
    D[j][i] = d;
}

我认为大多数人认为折叠循环会带来更好的性能，但事实往往并非如此。根据我的经验，大多数时候性能没有差异，但在某些情况下，由于缓存问题，性能会更差。在某些情况下效果更好。你必须测试一下自己。

至于为什么您的代码在使用崩溃子句时速度慢了一倍，我只能猜测，因为内部循环的效果未指定，您的 OpenMP 实现是从j整个[0,n)矩阵而不是一半矩阵运行的。