2

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!

Z boson
  • 32,619
  • 11
  • 123
  • 226
Treper
  • 3,539
  • 2
  • 26
  • 48
  • Are you aware that this problem can be solved in O(n lg n) time for common distance metrics? https://en.wikipedia.org/wiki/Closest_pair_of_points_problem – Fred Foo May 30 '14 at 08:24
  • If you want to stick with this algorithm, you may want to have a look at the `collapse` clause of the loop construct. – Massimiliano May 30 '14 at 08:33
  • Sorry.I didn't mention the distance metric is cosine distance.O(nlgn) algorithm seems only apply to Euclidean Space. – Treper May 30 '14 at 08:38
  • @Massimiliano, since j depends on i will collapse still work? In any case, fusing the loops won't fix his problem. – Z boson May 30 '14 at 11:50
  • @Zboson 1. I found no point in the standard preventing the fused loop to work, but I may be missing something 2. I agree there are more problems in the snippet – Massimiliano May 30 '14 at 15:47
  • @Massimiliano, yeah, I found nothing in the standard saying it would not fuse it either but I would be surprised if it works. GCC gives a warning. But I have not tried it. I'm not even sure how to manually to it but I have an idea. – Z boson May 31 '14 at 21:46
  • @Massimiliano, in case you're interested http://stackoverflow.com/questions/24013832/fusing-a-triangle-loop – Z boson Jun 03 '14 at 11:19
  • @Massimiliano, this question has nothing to do whatsoever with `collapse`. Why was it closed? – Z boson Jun 10 '14 at 10:44

1 Answers1

3

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;
        }
    }
}
Z boson
  • 32,619
  • 11
  • 123
  • 226