使用openmp和分段錯誤的並行K最近鄰居

Question

我正在嘗試做「dat」中數據點的k最近鄰居（KNN），所以我的第一步是構建每個點和所有其他點之間的距離矩陣點，然後爲每個點找到K最近的鄰居。下面的代碼在沒有openmp的情況下可以很好地工作。但是，當我使用openmp時，會出現分段錯誤。我認爲這個錯誤與我如何更新包含k個最小元素索引的最小值有關。我認爲可能是我需要使用矢量最小的「縮小」，但我不知道如何使用它，或者它是對還是錯，所以對如何克服這種分割錯誤的幫助真的很感激。

vector<vector<double> > dist(dat.size(), vector<double>(dat.size())); 
size_t p,j; 
ptrdiff_t i; 
vector<double> sumKnn; 
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 = p+1; 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][j-p-1]=j; 
      mycont++; 
     } 
     else 
     { 
      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.push_back(sum); 
} 

Answer 1

你可以用 「挑剔」 的指令：

#pragma omp critical 
{ 
smallest[p].erase(smallest[p].begin()+index); 
smallest[p].push_back(j); 
} 

和

#pragma omp critical 
sumKnn.push_back(sum); 

但我同意，更好是使用kd樹或K均值的樹istead並行化。您可以下載FLANN庫http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN。

Answer 2

所以我同意@izomorphius是並行算法（其中所有的距離計算）可能不會比使用更快的基於樹的算法，特別是對於非常大數目的點是一個加速。

不過，你可以很容易地做到這一點。問題是你不能有多個線程同時處理共享向量上的push_back（）和erase（）。無論如何坦率地說，載體看起來像是錯誤的方法來使用這些東西;既然你知道這些東西的大小，只是使用數組可能是一種方式。

無論如何，通過在最小的[] []數組中手動​​移動東西，而不是使用擦除和回推，並且只需爲sumKnn寫入靜態數組而不是使用push_back（），就可以實現上班。

#include <cmath> 
#include <cstdlib> 
#include <vector> 

using namespace std; 

int main(int argc, char **argv) { 

    const int size = 25; // number of pts 
    const int k = 2;  // number of neighbours 
    const int c = 2;  // number of dimensions 

    vector<vector<double> > dat(size, vector<double>(c)); 
    for (int i=0; i<size; i++) { 
     vector<double> pt(c); 
     for (int d=0; d<c; d++) { 
      pt.push_back(rand()*1./RAND_MAX); 
     } 
     dat.push_back(pt); 
    } 

    vector<vector<double> > dist(size, vector<double>(size)); 
    double sumKnn[size]; 

    vector<vector<int > > smallest(size, vector<int>(k)); 
#pragma omp parallel for default(none) shared(dat, dist, smallest, sumKnn) 
    for(size_t p=0;p<size;++p) 
    { 
     int mycont=0; 
     for (size_t j = p+1; j < size; ++j) 
     { 
      double ecl = 0.0; 
      for (ptrdiff_t 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][j-p-1]=j; 
       mycont++; 
      } 
      else 
      { 
       double max=0.0; 
       int index=0; 
       for(int i=0;i<k;i++) 
       { 
        if(max < dist[p][smallest[p][i]]) 
        { 
         index=i; 
         max=dist[p][smallest[p][i]]; 
        } 
       } 
       if(max>dist[p][j]) 
       { 
        for (int ii=index; ii<k-1; ii++) 
         smallest[p][ii] = smallest[p][ii+1]; 
        smallest[p][k-1] = j; 
       } 
      } 
     } 
     double sum=0.0; 
     for(int r=0;r<k;r++) 
      sum+= dist[p][smallest[p][r]]; 
     sumKnn[p] = sum; 
    } 


    return 0; 
}