Critical Section inside for loop in Openmp

I have the following code:

#pragma omp parallel for private(dist,i,j)
for(k=0;k<K;k++)
{
 //some code 
 for(i=0;i<N;i++)
    {
      #pragma omp critical
       {
        if(min_dist[i]>dist[i])//The point i belongs to the cluster k
        {
         newmembership[i]=k;
         min_dist[i]=dist[i];
        }
       }
    dist[i]=0;
    }
}

dist is a private variable whereas newmemebership and min_dist is a shared variable.For my test case the code still works if we run the code without adding the critical section construct.To the best of my understanding,it should not as two threads might be running on the same value of i and might modify the min_dist[i] and newmembership[i] leading to conflict.

Please explain whether it is necessary to add the critical section construct and also is there a better way to implement the above ie using locks or semaphores ?

Solution

Removing the critical section would be a data race. Consider the following execution:

(min_dist[42] == 100)
time | Thread 0                       | Thread 1
----------------------------------------------------------------------
  0  | k = 13                         | 
  1  | i = 42                         | k = 14
  2  | dist[i] = 50                   | i = 42
  3  | min_dist[i] > dist[i] ==> true | dist[i] = 75
  4  | newmembership[i] = 13          | min_dist[i] > dist[i] ==> true
  5  | min_dist[i]=50                 | newmembership[i] = 14
  6  | ...                            | min_dist[i]=75

So you end up with a non-minmal solution. You can even end up with conflicting min_dist / newmembership values.

The alternative way is to create thread private local_min_dist / local_newmembership arrays, and merge them at the end of the execution:

#pragma omp parallel
{
    // Note: implicitly private because defined inside the parallel region
    int local_newmembership[N];
    int local_min_dist[N];

    #pragma omp for private(dist,i,j)
    for(k=0;k<K;k++)
    {
        //some code 
        for(i=0;i<N;i++)
        {
            // NOTE: No critical region necessary
            // as we operate on private variables
            if(local_min_dist[i]>dist[i])//The point i belongs to the cluster k
            {
                local_newmembership[i]=k;
                local_min_dist[i]=dist[i];
            }
            dist[i]=0;
        }
    }

    for (i = 0; i < N; i++)
    {
        // Here we have a critical region,
        // but it is outside of the k-loop
        #pragma omp critical
        if (min_dist[i] > local_min_dist[i])
        {
            newmembership[i] = local_newmembership[i];
            local_min_dist[i] = local_min_dist[i];
        }
    }
}