OMP параллельный для сокращения
Я пытаюсь написать класс кластеризации k-средних. Я хочу сделать свою функцию параллельной.
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,
Возможно, лучшей стратегией было бы иметь каждый поток своей собственной переменной перемещения, и в конце они бы повысили его.
Решение
Вы используете closest переменная внутри параллельного цикла, и запись в него, и использование его в качестве проверки перед увеличением moves переменная. Но он объявлен вне цикла, поэтому все итерации используют одну и ту же переменную! Поскольку все итерации выполняются (теоретически) параллельно, вы не можете ожидать, что любая итерация увидит то, что написала любая другая итерация closest в отраслевом состоянии if (assignment[i] != closest), Эта переменная случайно обновляется путем параллельных потоков. Поэтому ваш moves оценивает в мусорное значение.
Перемещение декларации closest внутри внешнего цикла или объявив его как private(closest) в прагме OpenMP может решить вашу проблему.
Кстати, closest может быть неинициализированным, и должен быть лучше того же типа, что и kт.е. int,
Другие решения
detector