Warum wird meine Matrix-Vektor-Multiplikationsskalierung nicht durchgeführt?

15

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=VERBOSEAusgabe 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.075Sekunden 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:Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben

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.

Anfrage
quelle

Antworten:

20

Ihre Matrix hat eine Größe von 15.000 x 15.000, sodass Sie 225 Millionen Elemente in der Matrix haben. Dies ergibt ungefähr 2 GB Speicher. Dies ist viel mehr als die Cachegröße Ihres Prozessors. Sie muss daher bei jeder Matrixmultiplikation vollständig aus dem Hauptspeicher geladen werden, sodass ca. 100 GB Datenübertragung sowie die für die Quell- und Zielvektoren erforderlichen Daten anfallen.

Die maximale Speicherbandbreite des i3 beträgt ungefähr 21 GB / s, basierend auf den Intel-Spezifikationen. Wenn Sie sich jedoch im Internet umschauen, werden Sie feststellen, dass höchstens die Hälfte davon in der Realität verfügbar ist. Zumindest würden Sie also erwarten, dass Ihr Benchmark 10 Sekunden hält, und Ihr tatsächlicher Messwert von 45 Sekunden ist nicht so weit von dieser Marke entfernt.

Gleichzeitig führen Sie ungefähr 10 Milliarden Gleitkommamultiplikationen und -additionen durch. Wenn Sie beispielsweise 10 Taktzyklen für die Kombination und eine Taktrate von 3 GHz berücksichtigen, werden Sie bei ~ 30 Sekunden herauskommen. Natürlich können sie gleichzeitig mit spekulativen Speicherladevorgängen ausgeführt werden, wenn der Cache clever ist.

Alles in allem würde ich sagen, dass Sie nicht zu weit vom Ziel entfernt sind. Was hättest du erwartet?

Wolfgang Bangerth
quelle
Gibt es nicht eine Möglichkeit, mindestens 2-3 zu beschleunigen?
Anfrage
@Nunoxic - Möglicherweise möchten Sie die Speicherleistung Ihres Systems mit einem Tool wie SiSoftware Sandra messen. Die Wolfgangs-Analyse ist genau das Richtige für mich. Wenn Ihre Anwendung an die Speicherbandbreite gebunden ist, hilft Parallelisierung nicht oder nur wenig. Sehen Sie sich auch die Energiesparoptionen an, die möglicherweise die Speicherleistung drosseln. Erwägen Sie außerdem, Ihren Speicher durch einen Speicher mit höherer Qualität zu ersetzen. Eine geringere CAS-Latenz kann beispielsweise einen großen Unterschied für Ihre Wandzeit bedeuten.
Mark Booth
4

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?

Pedro
quelle
Ich habe ATLAs, GoTo und Netlib BLAS ausprobiert. Alle sind schwächer als MKL in der Leistung. Wird das erwartet oder mache ich etwas falsch? Ich habe ATLAS wie im Handbuch beschrieben zusammengestellt. Außerdem habe ich meinen (exakt) Code eingefügt hier . Es heißt MKL's BLAS.
Anfrage
Okay, und für die Skalierung, sind Sie sicher, dass der Code in Ihrem Baseline-Fall nur auf einer einzelnen CPU ausgeführt wird? ZB wenn Sie es vergleichen, zeigt das CPU-Verwendungshistogramm nur einen einzelnen Kern an?
Pedro
Ja. Das CPU-Histogramm zeigt 1 Kern.
Anfrage
Was bekommen Sie aus Neugier für zwei oder drei Kerne? Verfügt Ihr Computer tatsächlich über vier physische Kerne oder nur über zwei Kerne mit Hyperthreading ?
Pedro
Wie finde ich das heraus? Ich habe meine KMP_AFFINITY in die Hauptliste aufgenommen.
Anfrage
0

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.

b

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.)

Thomas Klimpel
quelle