Warum multipliziert die VC++ - Matrix den Vektor schneller mit openMP als asynchron?

Question

Ich codierte die Multiplikation eines Vektors mit einer Matrix auf zwei Arten, eine mit openMP, die andere mit std :: async. Ich habe erwartet, dass die Leistung praktisch identisch ist. OpenMP ist beim ersten Aufruf langsam, wahrscheinlich weil es das Erstellen eines Thread-Pools verzögert. Danach ist die Async-Version konsistent um 40% langsamer. (Ich habe Intel Core i5, die 4 Kerne ist.)

Was ist das Geschäft? Verwendet VC++ keinen Thread-Pool für Async? Mache ich etwas Dummes? (Am wahrscheinlichsten.) Ich denke, der Zugriff auf den Ausgabevektor ist ausreichend weit beabstandet, um falsches Teilen zu vermeiden.

#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; 
} 

Answer 1

Auf einem Intel Core i7-2600, deaktiviert HT, mit gcc 7.2/Linux sind die Zahlen etwas anders, die Asynchron-Version etwa 10% langsamer ist.

Jetzt ist die Diskussion auf dem richtigen Weg in Bezug auf Cache-Effizienz und falsche Freigabe. Sie sollten versuchen, auf konsekutive Elemente mit demselben Thread zuzugreifen, mindestens bis zur Größe einer Cache-Zeile (z. B. 64 Byte). Zum Lesen sparen Sie einfach Speicherzugriffe, indem Sie die Cache/Datenlokalität effizienter nutzen - zum Schreiben ist es sogar noch schlimmer, weil falsches Teilen um die Cache-Zeile zwischen den Kernen springt. Es ist jedoch wichtig zu erkennen, dass es sich nicht um den eigentlichen Datenzugriff handelt - das geschieht innerhalb von std::inner_product und ist für beide Versionen gleich. Wenn der tatsächliche Datenzugriff in einem solchen fadenverschachtelten Muster erfolgt, wäre die Leistung viel schlechter als 40%.

Nun ist es leicht zu vermeiden und zu testen, ob es hilft:

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); 
    } 
}; 

In meiner Konfiguration, die alle Performance-Unterschiede zwischen den Versionen beseitigt.

Wenn Sie immer noch einen Unterschied in der Leistung auf Ihrem System sehen, würde ich empfehlen, ein geeignetes Leistungsanalyse-Tool zu verwenden. Ich bin mit Ihrem Ökosystem nicht vertraut, kann also keine Empfehlungen geben - aber es ist wichtig, dass Sie die Leistung nicht schätzen.

Beachten Sie, dass eine std::vector<std::vector<>> keine gute Datenstruktur für Hochleistungs-Datenzugriff/Matrix-Multiplikation ist. Sie werden nicht annähernd die Leistung einer hoch optimierten Bibliothek mit zusammenhängendem Speicher für die Matrix erreichen.