OMP 并行还原

Question

我正在尝试编写 k 均值聚类 class。我想让我的函数并行。

void kMeans::findNearestCluster()
{   
    short closest;
    int moves = 0;
    #pragma omp parallel for reduction(+:moves)
    for(int i = 0; i < n; i++)
    {      
        float min_dist=FLT_MAX;
        for(int k=0; k < clusters; k++)
        {
            float dist_sum = 0.0, dist2 = 0.0;
            for(int j = 0; j < dim; j++)
            {
                dist_sum = centroids[k*dim+j] - data[i*dim+j];
                dist2 +=  dist_sum * dist_sum;

            }
            if (dist2 < min_dist)
            {
                min_dist = dist2;
                closest = k;

            }

        }

        if (assignment[i] != closest)
        {
            assignment[i] = closest;
            moves++;
        }        

    }

    this->moves = moves;

}

它应该是这样工作的：

步骤 1：查找最近的集群
- 遍历所有数据点，比较所有质心之间的距离。
- 找到最近的质心后，将其存储在名为closest的变量中。
- 检查这个点是否分配给了新发现的最近的簇。如果没有，请将其移动到新的。（增量移动）
步骤 2：根据新分配重新计算质心。（函数未显示）
重复步骤 1 和步骤 2，直到不再发生移动。

没有#parallel moves收敛于零。如果我有 #parallel 个移动具有随机值。我认为是因为并行循环在更新 move 时存在冲突。

也许更好的策略是让每个线程都有自己的移动变量，最后它们会向上移动。

Answer 1

您在并行循环中使用了 closest 变量，在增加 moves 变量之前将其写入并用作检查。但是它是在循环外声明的，所以所有的迭代都使用同一个变量！由于所有迭代都是（理论上）并行执行的，因此您不能期望任何迭代都能看到任何其他迭代在分支条件 if (assignment[i] != closest) 中写入 closest 的内容。该变量通过竞速并行线程随机更新。因此，您的 moves 评估为垃圾值。

将 closest 的声明移到外层循环中或在 OpenMP pragma 中将其声明为 private(closest) 可能会解决您的问题。

对了，closest可能是未初始化的，最好和k是同一类型的，即int.

OMP 并行还原

OMP parallel for reduction

c++

cluster-analysis

openmp