параллельный K ближайшего соседа с использованием openmp и ошибки сегментации

Question

Я пытаюсь сделать k ближайшего соседа (KNN) точек данных в «dat», поэтому мой первый шаг - построить матрицу расстояний между каждой точкой и всеми остальными точками, затем для каждой точки найти 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-средних вместораспараллеливание.Вы можете просто скачать библиотеку FLANN http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN.

Answer 2

Так что я согласен с @izomorphius, что распараллеливание этого алгоритма (где вычисляются все расстояния), вероятно, не будет ускорением по сравнению с использованием более быстрого алгоритма на основе дерева, особенно для очень большого количества точек.1002 * Тем не менее, вы можете сделать это довольно легко.Проблема в том, что вы не можете иметь несколько потоков, выполняющих такие вещи, как 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;
}