Entschuldigung für den langen Beitrag, aber ich wollte alles, was ich für relevant hielt, gleich mit einbeziehen.
Was ich möchte
Ich implementiere eine parallele Version der Krylov-Subraummethoden für dichte Matrizen. Hauptsächlich GMRES, QMR und CG. Mir wurde (nach der Profilerstellung) klar, dass meine DGEMV-Routine erbärmlich war. Also beschloss ich, mich darauf zu konzentrieren, indem ich es isolierte. Ich habe versucht, es auf einem 12-Kern-Computer auszuführen, aber die folgenden Ergebnisse beziehen sich auf einen 4-Kern-Intel i3-Laptop. Es gibt keinen großen Unterschied im Trend.
Meine KMP_AFFINITY=VERBOSE
Ausgabe ist hier verfügbar .
Ich habe einen kleinen Code geschrieben:
size_N = 15000
A = randomly_generated_dense_matrix(size_N,size_N); %Condition Number is not bad
b = randomly_generated_dense_vector(size_N);
for it=1:n_times %n_times I kept at 50
x = Matrix_Vector_Multi(A,b);
end
Ich glaube, dies simuliert das Verhalten von CG für 50 Iterationen.
Was ich ausprobiert habe:
Übersetzung
Ich hatte den Code ursprünglich in Fortran geschrieben. Ich übersetzte es in C, MATLAB und Python (Numpy). Natürlich waren MATLAB und Python schrecklich. Überraschenderweise war C um ein oder zwei Sekunden besser als FORTRAN für die obigen Werte. Konsequent.
Profiling
Ich habe meinen Code für die Ausführung profiliert und er wurde für 46.075
Sekunden ausgeführt. Zu diesem Zeitpunkt wurde MKL_DYNAMIC auf gesetztFALSE
und alle Kerne wurden verwendet. Wenn ich MKL_DYNAMIC als true verwendet habe, war zu einem bestimmten Zeitpunkt nur (ca.) die Hälfte der Kerne belegt. Hier einige Details:
Address Line Assembly CPU Time
0x5cb51c mulpd %xmm9, %xmm14 36.591s
Der zeitaufwändigste Prozess scheint zu sein:
Call Stack LAX16_N4_Loop_M16gas_1
CPU Time by Utilization 157.926s
CPU Time:Total by Utilization 94.1%
Overhead Time 0us
Overhead Time:Total 0.0%
Module libmkl_mc3.so
Hier ein paar Bilder:
Schlussfolgerungen:
Ich bin ein echter Anfänger im Profilieren, aber mir ist klar, dass die Beschleunigung immer noch nicht gut ist. Der sequenzielle (1 Core) Code ist in 53 Sekunden beendet. Das ist eine Geschwindigkeit von weniger als 1,1!
Echte Frage: Was soll ich tun, um meine Geschwindigkeit zu verbessern?
Dinge, von denen ich denke, dass sie helfen könnten, aber ich kann nicht sicher sein:
- Pthreads-Implementierung
- MPI (ScaLapack) -Implementierung
- Manuelle Abstimmung (Ich weiß nicht wie. Bitte empfehlen Sie eine Ressource, wenn Sie dies vorschlagen)
Wenn jemand mehr (vor allem in Bezug auf Speicher) Details benötigt, lass es mich wissen, was ich ausführen soll und wie. Ich habe noch nie ein Erinnerungsprofil erstellt.
quelle
Wie machst du die Matrix-Vektor-Multiplikation? Eine Doppelschleife von Hand? Oder zu BLAS telefonieren? Wenn Sie MKL verwenden, würde ich dringend empfehlen, die BLAS-Routinen der Thread-Version zu verwenden.
Aus Neugier möchten Sie vielleicht auch Ihre eigene optimierte Version von ATLAS kompilieren und sehen, wie sich dies auf Ihr Problem auswirkt.
Aktualisieren
Nach der Diskussion in den Kommentaren unten stellt sich heraus, dass Ihr Intel Core i3-330M nur zwei "echte" Kerne hat. Die beiden fehlenden Kerne werden mit Hyperthreading emuliert . Da in Hyperthread-Kernen sowohl der Speicherbus als auch die Gleitkommaeinheiten gemeinsam genutzt werden, wird keine Beschleunigung erzielt, wenn einer der beiden Faktoren ein begrenzender Faktor ist. In der Tat wird die Verwendung von vier Kernen wahrscheinlich sogar die Geschwindigkeit verringern.
Welche Ergebnisse erzielen Sie mit "nur" zwei Kernen?
quelle
Ich habe den Eindruck, dass die Zeilen-Hauptreihenfolge hinsichtlich der Speicherzugriffszeiten, der Auslastung der Cache-Zeilen und der TLB-Fehler für dieses Problem optimal ist. Ich vermute, Ihre FORTRAN-Version hat stattdessen die Spalten-Hauptreihenfolge verwendet, was erklären könnte, warum sie durchweg langsamer ist als die C-Version.
Sie können die Geschwindigkeit auch testen, indem Sie anstelle der Matrixvektormultiplikation alle Elemente der Matrix in einer einzigen Schleife zusammenfassen. (Möglicherweise möchten Sie die Schleife um den Faktor 4 entrollen, da die Nichtassoziativität der Addition den Compiler daran hindern könnte, diese Optimierung für Sie durchzuführen.)
quelle