Критическая секция внутри для цикла в OpenMP

Question

У меня есть следующий код:

#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; 
    } 
} 

расстояния является частным переменным, тогда как newmemebership и Min_Dist является общей variable.For моего теста кода все еще работает, если мы запустим код без добавления конструкции критического сечения. Насколько я понимаю, это не должно быть, поскольку два потока могут выполняться с одинаковым значением i и могут изменять min_dist [i] и newmembership [i], приводящие к конфликту.

Пожалуйста, объясните, нужно ли добавить конструкцию критического сечения, а также есть ли лучший способ реализовать выше, т.е. использовать блокировки или семафоры?

Answer 1

Удаление раздела critical будет представлять собой гонку данных. Рассмотрим следующее выполнение:

(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 

Таким образом, вы получите неминутное решение. Вы даже можете столкнуться с противоречивыми значениями min_dist/newmembership.

Альтернативный способ заключается в создании нитке privatelocal_min_dist/local_newmembership массивов, и объединить их в конце исполнения:

#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]; 
     } 
    } 
}