multithreading - Openmp中for循环内的关键部分

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

dist 是一个私有(private)变量，而 newmemebership 和 min_dist 是一个共享变量。对于我的测试用例，如果我们在不添加关键部分构造的情况下运行代码，代码仍然有效。据我所知，它不应该作为两个线程可能在相同的 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 值。

另一种方法是创建线程 private local_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];
        }
    }
}