如何并行嵌套循环找到最近的两点在OpenMP？ [英] How to parallel nested loop to find the nearest two point in OpenMP?

问题描述

此问题不是融合嵌套循环的重复。 OP希望减小最大值并同时存储两个指数。融合循环不会修复OPs问题。 OP在共享索引上仍然具有竞争条件，并且将访问减小的值，该值不会被合并直到缩减的结束（参见我的答案对于OPs问题的一个解决方案）。

我有一个2D矩阵X，X [i] [j]表示点i和j之间的距离。下面的代码是根据他们的嵌套循环中的余弦距离：

  // m，n是X的行，列分别是
 int mi， mj; 
 for（int i = 0; 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不正确记录。
 
 
 
去做吧？很多坦克！
解决方案
  max_distance 版本为每个线程并在循环后合并它们。问题是， mi 和 mj 是共享的，所以你有一个竞争条件写给他们。您需要私有版本的 mi 和 mj 以及您合并到最后。
 
 
 
下面的代码应该做你想要的。 
  #pragma omp parallel 
 {
 float max_distance_private = max_distance; 
 int mi_private，mj_private; 
 #pragma omp for 
 for（int i = 0; 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; 
} 
} 
} 
  
 
This question is not a duplicate of fusing nested loops. The OP wants to do a reduction of a maximum value and at the same time store two indices. Fusing the loops will not fix the OPs problem. The OP would still have race conditions on the shared indices and would be accessing the reduced value which does not get merged until the end of the reduction (see my answer for one solution to the OPs problem). 

I have a 2D matrix X,X[i][j] means the distance between point i and j.Following code is to find the nearest two point according to their cosine distance in nested loop:
//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;
        }
    }
}
I am new to OpenMP and want to parallel it to get the nearest two point's index i,j.
Only adding 
#pragma omp parallel for reduction(max : max_distance) 
of course not working because the i,j is not rightly recorded.

How to do it?  Many Tanks!
解决方案
The reduction on max_distance is handled by making private version for each thread and merging them after the loop.  The problem is that mi and mj are shared so you have a race condition writing to them.  You need private versions of miand mj as well which you merge in the end.

The following code should do what you want.  
#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;
        }
    }
}


                        
这篇关于如何并行嵌套循环找到最近的两点在OpenMP？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！