schnelle einfache Präzision Matrix Zeiten Vektor Produkt

Question

Betrachten Sie eine Matrix A der Schwimmer der Größe 48x16 und ein Vektor der Schwimmer b der Größe 1x48.

vorschlagen Bitte einen Weg b × A so schnell wie möglich auf gemeinsame Desktop-Prozessoren der Berechnung (i5/i7).

Hintergrund. Das oben genannte Produkt befindet sich in einer engen Schleife, daher ist eine schnelle Berechnung unerlässlich. Im Moment arbeite ich mit dem folgenden naiven Algorithmus:

inline void Critical(const float A[48][16], const float b[48], float x[16]) const { 
    for (int u = 0; u < 48; ++u) { 
     for (int i = 0; i < 16; ++i) { 
      x[i] += A[u][i] * b[u]; 
     } 
    } 
} 

Ich habe versucht, die Vermehrung zu MKL des SGEMV und später SGEMM aber ohne Erfolg abzuladen. Die naive Implementierung funktioniert immer noch schneller auf einem i7 4800MQ.

EDIT1.

Eigen mit statischer Zuordnung ist ungefähr so ​​schnell wie der naive Algorithmus.

Ich habe versucht, GCC5, ICC und VC2015U3 mit Optimierungen eingeschaltet (/ O3, schnelle Mathematik, mtune = native, etc). ICC scheint unter Linux und Windows den schnellsten Code zu produzieren.

EDIT2.

Die Elemente A sind klein, max (| A _ui |) = 256. Ähnlich max (| b _u |) = 1,0. Vernünftig approximative Lösungen sind ebenfalls akzeptabel, solange der Algorithmus schneller ist als der naive.

Answer 1

MKL hat normalerweise einen großen Overhead, daher ist die Leistung für kleine Matrix schlecht. Eigen auf der anderen Seite haben Matrix-Optimierung mit fester Größe, die auf kleiner Matrix gut funktioniert. Sie benötigen auch korrekte Übersetzungsoptionen, um die maximale Leistung mit Eigen zu erhalten.

#include <iostream> 
#include <Eigen/Eigen> 
#include <omp.h> 

inline void Critical(const float A[48][16], const float b[48], float x[16]) { 
    for (int i = 0; i < 16; ++i) { 
    x[i] = 0; 
    } 
    for (int u = 0; u < 48; ++u) { 
    for (int i = 0; i < 16; ++i) { 
     x[i] += A[u][i] * b[u]; 
    } 
    } 
} 

int main() { 
    float a[48][16] = { 0 }; 
    float b[48] = { 0 }; 
    float x[16] = { 0 }; 
    Eigen::Matrix<float, 48, 16> ma; 
    Eigen::Matrix<float, 1, 48> mb; 
    Eigen::Matrix<float, 1, 16> mx; 

    ma.setRandom(); 
    mb.setRandom(); 
    for (int i = 0; i < 48; ++i) { 
    for (int j = 0; j < 16; ++j) { 
     a[i][j] = ma(i, j); 
    } 
    b[i] = mb(i); 
    } 

    double t; 
    int n = 10000000; 

    t = omp_get_wtime(); 
    for (int i = 0; i < n; ++i) { 
    Critical(a, b, x); 
    } 
    t = omp_get_wtime() - t; 
    std::cout << "for-loop time: " << t << std::endl; 

    t = omp_get_wtime(); 
    for (int i = 0; i < n; ++i) { 
    mx = mb * ma; 
    } 
    t = omp_get_wtime() - t; 
    std::cout << "eigen time: " << t << std::endl; 

    Eigen::Map < Eigen::Matrix<float, 1, 16> > native_x(x); 
    std::cout << "error: " << (mx - native_x).norm() << std::endl; 

    return 0; 
} 

Wenn mit g ++ 5.2.1

$ g++ -fopenmp -O3 -DNDEBUG -I~/program/include/eigen3 -o test/gemv test/gemv.cpp && test/gemv 
for-loop time: 2.53004 
eigen time: 1.17458 
error: 1.49636e-06 

Kompilieren Wenn mit icpc 16.0.2

$ icpc -fopenmp -fast -DNDEBUG -I~/program/include/eigen3 -o test/gemv test/gemv.cpp && test/gemv 
for-loop time: 1.03432 
eigen time: 1.01054 
error: 1.40769e-06 

icpc verwendet Auto-Vektorisierung zum Kompilieren FOP-Schleifen somit die Leistung ist mit gleicher Eigen.