Почему матрица VC++ умножает вектор быстрее с openMP, чем с асинхронным?

Я закодировал умножение вектора на матрицу двумя способами: один с помощью openMP, другой с помощью std::async. Я ожидал, что производительность будет практически одинаковой. OpenMP работает медленно при первом вызове, вероятно, потому, что откладывает создание пула потоков. После этого асинхронная версия стабильно работает на 40% медленнее. (У меня Intel Core i5, 4 ядра.)

В чем дело? Разве VC++ не использует пул потоков для асинхронности? Я делаю что-то глупое? (Скорее всего.) Я думаю, что доступ к выходному вектору достаточно разнесен, чтобы избежать ложного совместного использования.

#include "stdafx.h"
# include <iostream>
# include <vector>
# include <omp.h>
# include <ctime>
#include <numeric>
#include <thread>
#include <chrono>
#include <future>

// Matrix multiplication of vector using omp
template<class Mat, class Vec>
void mult_mat_vec_omp
(const Mat &mat, const Vec &inp, Vec &out) {
    const int steps = static_cast<int>(std::size(mat));
    using std::begin; using std::end;
    auto N = std::thread::hardware_concurrency();
    omp_set_num_threads(N); 
#pragma omp parallel for 
    for (int i=0; i < steps; ++i) {
        out[i] = std::inner_product(begin(mat[i]), end(mat[i]), begin(inp), 0.0);
    }
}


// Matrix multiplication of vector using async
template<class Mat, class Vec>
void mult_mat_vec_async
(const Mat &mat, const Vec &inp, Vec &out) {
    using std::begin; using std::end;
    auto N = std::thread::hardware_concurrency();
    typedef decltype(N) usigned;
    const unsigned steps = static_cast<unsigned>(std::size(mat));
    auto f = [&](unsigned id) {
    for (unsigned i=id; i < steps; i+= N) {
            out[i] = std::inner_product(begin(mat[i]), end(mat[i]), begin(inp), 0.0);
        }
    };
    std::vector<std::future<void>> threads;
    for (unsigned i = 1; i<N; ++i) {
        threads.push_back(std::async(std::launch::async, f, i));
    }
    f(0);
    for (auto &x: threads) {
        x.get();
    }
}


double test() {
    using std::vector;
    using clock=std::chrono::high_resolution_clock;
    vector<double> a;
    vector<double> b;
    vector<double> c;
    vector<vector<double>> mat;
    vector<double> v;
    int rows = 350;
    int cols = 350;
    for (int i = 0; i< cols; ++i) {
        a.push_back(i/10.0);
        b.push_back(-999);
        c.push_back(8888);
    }
    for (int i=0; i<rows; ++i) {

        v.clear();
        for (int j=0; j<cols; ++j) {
            v.push_back (((i+.5)*j)/100.0);
        }
        mat.push_back(v);
    }
    clock::time_point start = clock::now();
    int N = 10000;
    for (int i=0; i< N/10; ++i) { 
    mult_mat_vec_omp(mat, a, b) ;
    mult_mat_vec_omp(mat, a, b);
    mult_mat_vec_omp(mat, a, b);
    mult_mat_vec_omp(mat, a, b);
    mult_mat_vec_omp(mat, a, b);
    mult_mat_vec_omp(mat, a, b);
    mult_mat_vec_omp(mat, a, b);
    mult_mat_vec_omp(mat, a, b);
    mult_mat_vec_omp(mat, a, b);
    mult_mat_vec_omp(mat, a, b);

    };
    long long duration =  
std::chrono::duration_cast<std::chrono::milliseconds>(clock::now()-start).count();
    start = clock::now();
    size_t cutoff = 0; // 2*rows*cols;
    for (int i=0; i< N/10; ++i) { 
    mult_mat_vec_async(mat, a, c);
    mult_mat_vec_async(mat, a, c);
    mult_mat_vec_async(mat, a, c);
    mult_mat_vec_async(mat, a, c);
    mult_mat_vec_async(mat, a, c);
    mult_mat_vec_async(mat, a, c);
    mult_mat_vec_async(mat, a, c);
    mult_mat_vec_async(mat, a, c);
    mult_mat_vec_async(mat, a, c);
    mult_mat_vec_async(mat, a, c);

    };
 long long duration2 = std::chrono::duration_cast<std::chrono::milliseconds>(clock::now()-start).count();
    //cout << mat[0][5] << " " << b[0] << " " << c[0] << endl;
    bool good = (b==c);
    std::cout << duration*(1.0/N) << ' ' << duration2*(1.0/N) << " " << good << std::endl;
    return 0;
}

int main ()
{
    for(int i=0; i<15; ++i) test();
    return 0;
}

person Jive Dadson    schedule 24.10.2017    source источник
comment
Как долго длится бенчмарк? Секунды? Миллисекунды?   -  person Mysticial    schedule 24.10.2017
comment
Секунды на итерацию (режим выпуска). Должно быть очевидно, как уменьшить это, если вам нужно сесть на автобус. Сократите N=10000.   -  person Jive Dadson    schedule 24.10.2017
comment
Во-первых, модель доступа к памяти в версии std::async довольно ужасна. Каждая нить шагает на N. В версии OpenMP вы позволяете OpenMP управлять распределением работы. И, вероятно, он использует блочное распределение вместо пошагового распределения.   -  person Mysticial    schedule 24.10.2017
comment
Ужасно из-за промахов кеша? Н всего 4.   -  person Jive Dadson    schedule 24.10.2017
comment
Я не уверен, имеет ли это значение здесь, но это означает, что каждый поток касается в 4 раза больше кэш-линий, чем нужно. Другая возможность заключается в том, что вы получаете ложное совместное использование при записи в out[i]. Они чередуются между потоками, поэтому существует реальная возможность конфликта.   -  person Mysticial    schedule 24.10.2017
comment
Я думаю, что вы можете быть правы, касаясь большего количества строк. Я сомневаюсь, что это ложный обмен. Кажется, я помню, что строки кэша короткие. Я буду работать над этим. БРБ   -  person Jive Dadson    schedule 24.10.2017
comment
Я попытался использовать блочное распределение. Нет радости. Программное обеспечение stackoverflow недовольно продолжительным обсуждением. Потом...   -  person Jive Dadson    schedule 24.10.2017
comment
похоже, что openmp ничего не делает, и макросы openmp не влияют. он работает синхронно, поэтому версия потока работает быстрее.   -  person David Haim    schedule 24.10.2017
comment
Не могли бы вы опубликовать конкретную модель процессора и цифры производительности. Это облегчает воспроизведение и дает конкретный ответ.   -  person Zulan    schedule 24.10.2017
comment
@Zulan - Intel Core i5-2400 (в) 3,10 ГГц 3,10 ГГц   -  person Jive Dadson    schedule 24.10.2017


Ответы (1)


На Intel Core i7-2600, отключенном HT, с gcc 7.2/Linux цифры несколько другие, асинхронная версия примерно на 10% медленнее.

Теперь обсуждение эффективности кэширования и ложного совместного использования находится на правильном пути. Вы должны попытаться получить доступ к последовательным элементам одним и тем же потоком, по крайней мере, до размера строки кэша (например, 64 байта). Для чтения вы просто экономите на доступе к памяти, используя кэш / локальность данных более эффективно — для записи это еще хуже, потому что ложное совместное использование будет отскакивать от строки кеша между ядрами. Однако важно понимать, что речь идет не о фактическом доступе к данным — это происходит внутри std::inner_product и одинаково для обеих версий. Если бы фактический доступ к данным осуществлялся по такому шаблону с чередованием потоков, производительность была бы намного хуже, чем на 40%.

Теперь его легко избежать и проверить, помогает ли это:

const unsigned steps = static_cast<unsigned>(std::size(mat));
auto f = [&](unsigned id) {
    const auto chunk_size = 1 + ((steps - 1) / N);
    const auto max = std::min(chunk_size * (id + 1), steps);
    for (unsigned i = chunk_size * id; i < max; i++)
    {
        out[i] = std::inner_product(begin(mat[i]), end(mat[i]), begin(inp), 0.0);
    }
};

В моей конфигурации это устраняет все различия в производительности между версиями.

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

Обратите внимание, что std::vector<std::vector<>> не является хорошей структурой данных для высокопроизводительного доступа к данным/умножения матриц. Вы не приблизитесь к производительности высокооптимизированной библиотеки, использующей непрерывную память для матрицы.

person Zulan    schedule 24.10.2017
comment
Большое спасибо. На моей машине переход от шагания к чанкингу дал улучшение на 10%. Асинхронная версия по-прежнему на 30% медленнее, чем omp. Очень странный. Какую магию творит под капотом версия omp? - person Jive Dadson; 25.10.2017
comment
Я изменил мат в тестовой процедуре с ‹vector‹vector‹double›› на double mat[rows][cols].. Меня порадовало, что шаблоны работают без изменений, но я не увидел увеличения скорости. - person Jive Dadson; 25.10.2017