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

考虑以下代码：

#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

我获得了以下运行时间：

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

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

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

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

预先感谢您的帮助！

当迭代依赖于另一个循环时，不应使用塌陷子句。看了解 openmp 中的折叠子句 https://stackoverflow.com/questions/28482833/understanding-the-collapse-clause-in-openmp/28483812#28483812.

在您的情况下，由于对称性，您正在遍历矩阵的下三角形（不包括对角线）。这将迭代次数大约减少了一半。如果你想融合/折叠双环，你可以像这样手动完成（参见结尾）这个答案 https://stackoverflow.com/a/33836073/2542702更多细节）。

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 from [0,n)即完整矩阵而不是一半矩阵。