Параллельный алгоритм для поиска ближайших точек K

Question

Я применил следующий код, который использует точки данных в «dat» для вычисления матрицы расстояния между каждой точкой и всеми остальными точками «dist». Затем я использую эту матрицу расстояний, чтобы найти К ближайших точек к каждой точке данных «наименьшая», а затем использовать ее, чтобы найти сумму ближайшего соседа К.

Следующий алгоритм - это параллельный алгоритм с использованием OpenMP, и он работает очень хорошо. Мне просто нужны предложения, чтобы он работал быстрее. Любое предложение высоко ценится.

vector<vector<double> > dist(dat.size(), vector<double>(dat.size())); 
size_t p,j; 
ptrdiff_t i; 
double* sumKnn = new double[dat.size()]; 
vector<vector<int > > smallest(dat.size(), vector<int>(k)); 
#pragma omp parallel for private(p,j,i) default(shared) 
for(p=0;p<dat.size();++p) 
{ 
    int mycont=0; 
    for (j = 0; j < dat.size(); ++j) 
    { 
     double ecl = 0.0; 
     for (i = 0; i < c; ++i) 
     { 
      ecl += (dat[p][i] - dat[j][i]) * (dat[p][i] - dat[j][i]); 
     } 
     ecl = sqrt(ecl); 
     dist[p][j] = ecl; 
     //dist[j][p] = ecl; 
     int index=0; 
     if(mycont<k && j!=p) 
     { 
      smallest[p][mycont]=j; 
      mycont++; 
     } 
     else if(j!=p) 
     { 
      double max=0.0; 
      int index=0; 
      for(int i=0;i<smallest[p].size();i++) 
      { 
       if(max < dist[p][smallest[p][i]]) 
       { 
        index=i; 
        max=dist[p][smallest[p][i]]; 
       } 
      } 
      if(max>dist[p][j]) 
      { 
       smallest[p].erase(smallest[p].begin()+index); 
       smallest[p].push_back(j); 
      } 
     }   
    } 
    double sum=0.0; 
    for(int r=0;r<k;r++) 
     sum+= dist[p][smallest[p][r]]; 
    sumKnn[p]=sum; 
} 

Answer 1

Это больше комментариев, чем ответ, но комментарий коробка слишком мала, ...

Одним из полезных аспектов OpenMP является то, что вы можете parallelise последовательной программы пошагово. Итак, ваш первый шаг должен состоять в том, чтобы написать серийный код, который решает вашу проблему. Когда вы это сделаете, вы можете отправить сообщение снова и попросить о помощи по его параллелизации.

Чтобы распараллелить вашу программу, найдите самый внешний оператор цикла и подумайте, как распределение итераций цикла по потокам повлияет на вычисления. Я подозреваю, что вы захотите создать общий вектор близких точек, когда петли пройдут, а затем отсортируйте их в конце только на одном потоке. Или, возможно, нет.