От серийного к omp: нет ускорения

Question

Я новичок в 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

Что я делаю не так?

EDIT

Процессор: Intel (R) Core (TM) i5-4590 Процессор (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

Answer 1

Ваша основная проблема заключается в том, что вы случайно используете вложенный параллелизм:

#pragma omp parallel
{
    size_t i, j;

    #pragma omp parallel for

Поскольку вы уже находитесь в параллельном регионе, ваша вторая строка должна быть

    #pragma omp for

В противном случае, так какomp parallel for равно omp parallel и omp for, у вас есть две вложенные параллельные области, что, как правило, плохо.Исправление этой незначительной вещи ускоряется примерно в 2 раза на аналогичном процессоре.

Существует несколько ограничений, почему вы вряд ли получите полное ускорение в 4 раза, например, но не ограничиваясь:

• Пропускная способность памяти в качестве узкого места
• Относительные издержки из-за небольшого объема работы, выполняемой в параллельном цикле
• Меньшие тактовые частоты с несколькими потоками в турбо-режиме

Изменить: Кстати, гораздо более идиоматический способ написания вашего кода заключается в следующем:

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

Если вы объявляете переменные как можно более локально, OpenMP почти всегда будет делать правильные вещи.Что в данном случае означает, что i и j являются частными.В общем, гораздо проще рассуждать о коде таким образом.

Answer 2

Для этого может быть много причин, наиболее очевидным из которых является то, что рабочая нагрузка слишком мала, чтобы заметить ускорение.Начальная рабочая нагрузка составляет 300 мс.Я бы предложил заключить это в последовательную внешнюю петлю, которая повторяет эту работу не менее 20 раз, а затем вы начинаете с последовательного времени (300 мс * 20) 6 секунд для тестирования.

Другим фактором являетсяналичие параллельных ядер на машине, на которой вы работаете.Если ваш процессор имеет одно ядро, многопоточность приведет к замедлению из-за стоимости переключения потоков.2 логических ядра должны показывать некоторое ускорение, 2 физических ядра могут показывать близкое к линейному ускорение.

Использование только прагматических директив также не гарантирует использование openMP.Вы должны скомпилировать, используя аргумент командной строки -fopenmp, чтобы гарантировать, что библиотека openmp связана с вашим объектным кодом.

Редактировать

Глядя на ваш код сейчас,фактор, который контролирует объем работы, кажется, N, а не внешний цикл.Идея внешнего цикла состояла в том, чтобы искусственно увеличить объем работы за тот же период времени, но это невозможно сделать здесь, когда вы пытаетесь решить конкретную проблему.Вы также можете попробовать распараллелить вложенный цикл, но я думаю, что N = 800 слишком мало, чтобы распараллеливание имело значение.

#pragma omp parallel for private(j) collapse(2)

j должен быть закрытым для каждой итерации внешнего цикла, следовательно, закрытым (j) в противном случае j распределяется между всеми потоками, что приводит к неточному результату.

Ваш цикл выполняется 640 000 раз, что не так много для современных процессоров с тактовой частотой 3GHZ +, попробуйте что-то около N = 5000, что составляет 25M итераций.