Kann die Berechnung von Matrixeinträgen durch die For-Schleife vermieden werden?

Question

Ich muss eine geschachtelte for-Schleife verwenden, um die Einträge einer Eigen :: MatrixXd-Typ-Matrix-Ausgabe spaltenweise zu berechnen. Hier werden Eingabe [0], Eingabe [1] und Eingabe [2] als Eigen :: ArrayXXd definiert, um die elementweisen Operationen zu verwenden. Dieser Teil scheint der Engpass für meinen Code zu sein. Kann mir jemand helfen, diese Schleife zu beschleunigen? Vielen Dank!

for (int i = 0; i < r; i++) { 
    for (int j = 0; j < r; j++) { 
     for (int k = 0; k < r; k++) { 
     output.col(i * (r * r) + j * r + k) = 
      input[0].col(i) * input[1].col(j) * input[2].col(k); 
     } 
    } 
    } 

Answer 1

Wenn man über Code einer for-Schleife Optimierung denken, hilft es, zu denken: „Gibt es redundante Berechnungen, die ich beseitigen kann?“

Beachten Sie, wie in der innersten Schleife nur k ändert. Sie sollten alle möglichen Berechnungen bewegen, dass tun nicht k aus dieser Schleife beinhalten:

for (int i = 0; i < r; i++) { 
    int temp1 = i * (r * r); 
    for (int j = 0; j < r; j++) { 
    int temp2 = j * r; 
    for (int k = 0; k < r; k++) { 
     output.col(temp1 + temp2 + k) = 
      input[0].col(i) * input[1].col(j) * input[2].col(k); 
    } 
    } 
} 

Beachten Sie, wie i * (r * r) über werden berechnet und über, aber die Antwort ist immer die gleiche! Sie müssen dies nur neu berechnen, wenn Sie i Inkremente eingeben. Das gleiche gilt für j * r.

Hoffentlich hilft das!

Answer 2

Um die Anzahl der Flops zu reduzieren, sollten Sie das Ergebnis input[0]*input[1] Cache:

ArrayXd tmp(input[0].rows()); 
for (int i = 0; i < r; i++) { 
for (int j = 0; j < r; j++) { 
    tmp = input[0].col(i) * input[1].col(j); 
    for (int k = 0; k < r; k++) { 
    output.col(i * (r * r) + j * r + k) = tmp * input[2].col(k); 
    } 
} 
} 

, dann vollständig Ihre CPU zu verwenden, AVX/FMA mit -march=native und natürlich Compiler-Optimierungen (-O3) ermöglichen.

Um eine Vorstellung davon zu bekommen, was Sie mehr gewinnen können, messen Sie genau die Zeit, die dieser Teil benötigt, zählen Sie die Anzahl der Multiplikationen (r^2 * (n + r * n)) und berechnen Sie die Zahl Fließkommaoperationen pro Sekunde erreichen Sie. Dann vergleichen Sie es mit der Kapazität Ihrer CPU. Wenn Sie gut sind, dann ist die einzige Option, Multithread-For-Schleife mit z. B. OpenMP. Die Wahl der for-Schleife hängt von der Größe Ihrer Eingaben ab, aber Sie können mit der äußeren versuchen und sicherstellen, dass jeder Thread sein eigenes tmp Array hat.