Я новичок в openMP. Я работаю над алгоритмом кратчайшего пути для всех пар, и вот последовательная процедура C++, которую мне нужно распараллелить (полный код в конце поста):

void mini(vector<vector<double>> &M, size_t n, vector<double> &rowk, vector<double> &colk)
{
    size_t i, j;

    for ( i=0; i<n; i++)
        for ( j=0; j<n; j++)
            M[i][j]=min(rowk[j]+colk[i], M[i][j]);

}

При выполнении получаю следующее:

$ time ./floyd 

real    0m0,349s
user    0m0,349s
sys     0m0,000s

Теперь я пытаюсь вставить некоторые директивы:

void mini(vector<vector<double>> &M, size_t n, vector<double> &rowk, vector<double> &colk)
{

    #pragma omp parallel
    {
        size_t i, j;

        #pragma omp parallel for
        for ( i=0; i<n; i++)
            for ( j=0; j<n; j++)
                M[i][j]=min(rowk[j]+colk[i], M[i][j]);
    }

}

К сожалению, ускорения нет:

$ grep -c ^processor /proc/cpuinfo                                    
4
$ time ./floyd 

real    0m0,547s
user    0m2,073s
sys     0m0,004s

Что я делаю неправильно?

РЕДАКТИРОВАТЬ

Процессор: Intel(R) Core(TM) i5-4590 CPU (4 аппаратных ядра)

Полный код:

#include <cstdio>
#include <vector>
#include <limits>
#include <ctime>
#include <random>
#include <set>
#include <omp.h>

using namespace std;

typedef struct Wedge
{
    int a, b;
    double w;
} Wedge;


typedef pair<int, int> edge;

int randrange(int end, int start=0)
{
    random_device rd;
    mt19937 gen(rd());
    uniform_int_distribution<> dis(start, end-1);

    return dis(gen);
}

void relax_omp(vector<vector<double>> &M, size_t n, vector<double> &rowk, vector<double> &colk)
{
    #pragma omp parallel
    {
        size_t i, j;

        #pragma omp parallel for
        for (i=0; i<n; i++)
            for ( j=0; j<n; j++)
                M[i][j]=min(rowk[j]+colk[i], M[i][j]);

    }
}


void relax_serial(vector<vector<double>> &M, size_t n, vector<double> &rowk, vector<double> &colk)
{
    size_t i, j;


    for (i=0; i<n; i++)
        for ( j=0; j<n; j++)
            M[i][j]=min(rowk[j]+colk[i], M[i][j]);
}


void floyd(vector<vector<double>> &dist, bool serial)
{
    size_t i, k;

    size_t n {dist.size()};

    for (k=0; k<n; k++)
    {
        vector<double> rowk =dist[k];
        vector<double> colk(n);

        for (i=0; i<n; i++)
            colk[i]=dist[i][k];
        if (serial)
            relax_serial(dist, n, rowk, colk);
        else
            relax_omp(dist, n, rowk, colk);
    }

    for (i=0; i<n; i++)
        dist[i][i]=0;
}


vector<Wedge> random_edges(int n, double density, double max_weight)
{
    int M{n*(n-1)/2};
    double m{density*M};
    set<edge> edges;
    vector<Wedge> wedges;

    while (edges.size()<m)
    {
        pair<int,int> L;
        L.first=randrange(n);
        L.second=randrange(n);

        if (L.first!=L.second && edges.find(L) == edges.end())
        {
            double w=randrange(max_weight);
            Wedge wedge{L.first, L.second, w};
            wedges.push_back(wedge);
            edges.insert(L);
        }
    }
    return wedges;
}


vector<vector<double>> fill_distances(vector<Wedge> wedges, int n)
{
    double INF = std::numeric_limits<double>::infinity();
    size_t i, m=wedges.size();
    vector<vector<double>> dist(n, vector<double>(n, INF));
    int a, b;
    double w;
    for (i=0; i<m; i++)
    {   a=wedges[i].a;
        b=wedges[i].b;
        w=wedges[i].w;
        dist[a][b]=w;
    }
    return dist;
}


int main (void)
{
    double density{0.33};
    double max_weight{200};
    int n{800};
    bool serial;

    int ntest=10;
    double avge_serial=0, avge_omp=0;

    for (int i=0; i<ntest; i++)
    {
        vector<Wedge> wedges=random_edges(n, density, max_weight);
        vector<vector<double>> dist=fill_distances(wedges, n);
        double dtime;

        dtime = omp_get_wtime();
        serial=true;
        floyd(dist, serial);
        dtime = omp_get_wtime() - dtime;
        avge_serial+=dtime;


        dtime = omp_get_wtime();
        serial=false;
        floyd(dist, serial);
        dtime = omp_get_wtime() - dtime;
        avge_omp+=dtime;
    }
    printf("%d tests, n=%d\n", ntest, n);
    printf("Average serial : %.2lf\n", avge_serial/ntest);
    printf("Average openMP : %.2lf\n", avge_omp/ntest);
    return 0;
}

выход :

20 tests, n=800
Average serial : 0.31
Average openMP : 0.61

командная строка:

g++ -std=c++11 -Wall -O2 -Wno-unused-result -Wno-unused-variable -Wno-unused-but-set-variable -Wno-unused-parameter floyd.cpp -o floyd -lm -fopenmp