c++ - 如何在 OpenMP 中并行嵌套循环找到最近的两点？

Question

这个问题不是融合嵌套循环的重复问题。 OP 想要减少最大值并同时存储两个索引。融合循环并不能解决 OP 问题。 OP 在共享索引上仍然存在竞争条件，并且将访问减少的值，该值在减少结束之前不会合并(请参阅我的答案，了解 OP 问题的一种解决方案)。

我有一个二维矩阵X，X[i][j]表示i点和j点之间的距离。以下代码是在嵌套循环中根据余弦距离找到最近的两点:

//m,n is the rows,columns of X respectively
int mi,mj;
for(int i=0;i<m;i++)
{
    for(int j=i+1;j<n;j++)
    {
        float distance = cosine_distance(i,j);
        if(distance>max_distance)
        {
            max_distance=distance;
            mi=i;
            mj=j;
        }
    }
}

我是 OpenMP 新手，想要将其并行化以获得最近的两点索引 i,j。 仅添加

#pragma omp parallel for reduction(max : max_distance) 

当然不起作用，因为 i,j 没有正确记录。

怎么做呢？许多坦克!

Answer 1

max_distance 的减少是通过为每个线程创建私有(private)版本并在循环后合并它们来处理的。问题是 mi 和 mj 是共享的，因此写入它们时存在竞争条件。您还需要 mi 和 mj 的私有(private)版本，并最终合并它们。

以下代码应该可以完成您想要的操作。

#pragma omp parallel
{
    float max_distance_private = max_distance;
    int mi_private, mj_private;
    #pragma omp for
    for(int i=0;i<m;i++) {
        for(int j=i+1;j<n;j++) {
            float distance = cosine_distance(i,j);
            if(distance>max_distance_private) {
                max_distance_private=distance;
                mi_private=i;
                mj_private=j;
             }
        }
    }
    #pragma omp critical 
    {
        if(max_distance_private>max_distance) {
            max_distance = max_distance_private;
            mi = mi_private;
            mj = mj_private;
        }
    }
}