Warum ist die Matrixmultiplikation langsamer als meine?

Question

Ich habe eine Matrix-Multiplikation mit boost::numeric::ublas::matrix implementiert

Result result = read(); 

boost::numeric::ublas::matrix<int> C; 
C = boost::numeric::ublas::prod(result.A, result.B); 

und ein anderer mit dem Standard-Algorithmus (my full, working boost code sehen) (siehe full standard code):

vector< vector<int> > ijkalgorithm(vector< vector<int> > A, 
            vector< vector<int> > B) { 
    int n = A.size(); 

    // initialise C with 0s 
    vector<int> tmp(n, 0); 
    vector< vector<int> > C(n, tmp); 

    for (int i = 0; i < n; i++) { 
     for (int k = 0; k < n; k++) { 
      for (int j = 0; j < n; j++) { 
       C[i][j] += A[i][k] * B[k][j]; 
      } 
     } 
    } 
    return C; 
} 

Dies ist, wie ich die Geschwindigkeit testen:

time boostImplementation.out > boostResult.txt 
diff boostResult.txt correctResult.txt 

time simpleImplementation.out > simpleResult.txt 
diff simpleResult.txt correctResult.txt 

Beide Programme lesen eine hartcodierte Textdatei, die zwei 2000 x 2000 matri enthält ces. Beide Programme wurden mit diesen Flags zusammengestellt:

g++ -std=c++98 -Wall -O3 -g $(PROBLEM).cpp -o $(PROBLEM).out -pedantic 

Ich habe 15 Sekunden für meine Implementierung und über 4 Minuten für die Boost-Implementierung! Ich habe 28,19 Sekunden für den ikj-Algorithmus und 60,99 Sekunden für Boost-Nachdem es mit

g++ -std=c++98 -Wall -pedantic -O3 -D NDEBUG -DBOOST_UBLAS_NDEBUG library-boost.cpp -o library-boost.out 

Kompilieren:

bearbeiten. Boost ist also immer noch deutlich langsamer.

Warum ist Boost so viel langsamer als meine Implementierung?

Answer 1

Langsamere Leistung der uBLAS-Version kann teilweise durch Debugging-Funktionen der letzteren erklärt werden, wie TJD darauf hingewiesen hat.

Hier ist die von der uBLAS Version mit Debugging-Zeit genommen auf:

real 0m19.966s 
user 0m19.809s 
sys  0m0.112s 

die Zeit von der uBLAS Version genommen Hier ist mit Debug-off (-DNDEBUG -DBOOST_UBLAS_NDEBUG Compiler-Flags hinzugefügt):

real 0m7.061s 
user 0m6.936s 
sys  0m0.096s 

So mit Debugging aus, uBLAS Version ist fast 3 mal schneller.

Restleistungsunterschied kann durch Angabe des folgenden Abschnitts uBLAS FAQ erläutert: „Warum ist uBLAS so viel langsamer als (Atlas-) BLAS“:

Ein wichtiges Designziel von ublas ist so allgemein zu sein, wie möglich.

Diese Allgemeingültigkeit kommt fast immer mit Kosten. Insbesondere kann die Funktionsschablone prod verschiedene Arten von Matrizen behandeln, wie zum Beispiel spärliche oder dreieckige Matrizen. Glücklicherweise bietet uBLAS Alternativen, die für eine dichte Matrixmultiplikation optimiert sind, insbesondere axpy_prod und block_prod. Hier sind die Ergebnisse der verschiedenen Methoden zu vergleichen:

ijkalgorithm prod axpy_prod block_prod 
    1.335  7.061 1.330  1.278 

Wie Sie sehen können beide axpy_prod und block_prod sind etwas schneller als Ihre Implementierung.Das Messen nur der Rechenzeit ohne I/O, Entfernen von unnötigem Kopieren und sorgfältige Wahl der Blockgröße für block_prod (ich benutzte 64) kann den Unterschied tiefer machen.

Siehe auch uBLAS FAQ und Effective uBlas and general code optimization.

Answer 2

Ich glaube, Ihr Compiler optimiert nicht genug. Der uBLAS-Code verwendet häufig Vorlagen und Vorlagen erfordern eine starke Nutzung von Optimierungen. Ich lief den Code durch MS VC 7.1 Compiler im Release-Modus für 1000x1000 Matrizen, es gibt mir

10.064 s für uBLAS

7.851 s für Vektor

Der Unterschied ist immer noch da, aber keineswegs überwältigend . Das Kernkonzept von uBLAS ist eine faule Auswertung, so wertet prod(A, B) Ergebnisse nur bei Bedarf aus, z. prod(A, B)(10,100) wird in kürzester Zeit ausgeführt, da nur dieses eine Element tatsächlich berechnet wird. Als solche gibt es eigentlich keinen dedizierten Algorithmus für die ganze Matrix-Multiplikation, die optimiert werden könnte (siehe unten). Aber man konnte die Bibliothek ein wenig helfen, erklärte

matrix<int, column_major> B; 

wird Laufzeit zu 4.426 s reduzieren, die Ihre Funktion gebunden mit einer Hand schlägt. Diese Deklaration macht den Zugriff auf den Speicher sequenzieller, wenn Matrizen multipliziert werden, wodurch die Cache-Nutzung optimiert wird.

P.S. Nach dem Lesen von uBLAS Dokumentation bis zum Ende;), sollten Sie herausgefunden haben, dass es tatsächlich eine dedizierte Funktion gibt, um ganze Matrizen gleichzeitig zu multiplizieren. 2 Funktionen - axpy_prod und opb_prod. So

opb_prod(A, B, C, true); 

auch auf nicht optimierten row_major B Matrix führt in 8.091 sec und ist auf einer Stufe mit dem Vektor-Algorithmus

P.P.S. Es gibt noch mehr Optimierungen:

C = block_prod<matrix<int>, 1024>(A, B); 

führt in 4.4 s, egal ob B column_ oder row_ Dur. Betrachten Sie die Beschreibung: "Der Funktionsblock_prod ist für große, dichte Matrizen ausgelegt." Wählen Sie spezifische Tools für bestimmte Aufgaben!

Answer 3

Ich habe eine kleine Website Matrix-Matrix Product Experiments with uBLAS erstellt. Es geht darum, eine neue Implementierung für das Matrix-Matrix-Produkt in uBLAS zu integrieren. Wenn Sie bereits die Boost-Bibliothek haben, besteht sie nur aus zusätzlichen 4 Dateien. Es ist also ziemlich eigenständig.

Ich wäre interessiert, wenn andere die einfachen Benchmarks auf verschiedenen Rechnern ausführen könnten.