NumPy-Matrixmultiplikation mit 150 Zeilen C-Code übertreffen

Zusammenfassung

Einführung

• Matrixmultiplikation ist ein wesentlicher Bestandteil moderner neuronaler Netze
• NumPy erreicht hohe Leistung durch die Nutzung externer BLAS-Bibliotheken
• Dieser Artikel erklärt, wie sich eine einfache, portable und skalierbare Hochleistungs-Matrixmultiplikation implementieren lässt

NumPy-Leistung

• NumPy verwendet auf AMD-CPUs OpenBLAS
• Die Leistungsmessung erfolgt in FLOP/s
• Auf einer Ryzen 7 7700 CPU wird die Single-Thread- und Multi-Thread-Leistung von NumPy gemessen

Theoretische Grenzen

• Die Speicherhierarchie der CPU und SIMD-Erweiterungen werden erläutert
• Theoretisch sind 163 GFLOPS mit einem einzelnen Thread und 1203 GFLOPS mit mehreren Threads erreichbar

Einfache Implementierung

• Der grundlegende Algorithmus der Matrixmultiplikation wird erklärt und die Leistung einer einfachen Implementierung gemessen
• Die einfache Implementierung erreicht 2,7 GFLOPS

Kernel

• Es wird erklärt, wie sich Matrixmultiplikation durch Zerlegung in kleine Teilprobleme lösen lässt
• Der Kernel wird mit SIMD-Instruktionen optimiert
• Mit einem 16x6-Kernel werden 147 GFLOPS erreicht

Masking und Packing

• Es wird erklärt, wie Randfälle behandelt werden, um Matrizen beliebiger Größe zu verarbeiten
• Mit Masking und Packing wird die Leistung optimiert
• Die neue Implementierung erreicht 56 GFLOPS

Caching

• Das Speichersystem des CPU-Caches wird erläutert
• Durch Nutzung des Caches werden Datenwiederverwendung und Cache-Verwaltung optimiert

Meinung von GN⁺

• Dieser Artikel ist sehr lehrreich, weil er Schritt für Schritt erklärt, wie sich eine Hochleistungs-Matrixmultiplikation implementieren lässt
• Man kann lernen, wie Optimierungen mit SIMD-Instruktionen und CPU-Caches funktionieren
• Er hilft dabei, die interne Arbeitsweise von Bibliotheken wie NumPy zu verstehen
• Andere Projekte mit ähnlicher Funktionalität sind unter anderem Intel MKL und OpenBLAS
• Bei der Einführung neuer Technologien oder von Open Source sollte man Leistung und Portabilität berücksichtigen

[GN⁺]

Hacker-News-Kommentare

• Die meiste Software ist nicht optimiert, daher gibt es viel Spielraum für Leistungsverbesserungen

  • Die Wahl des Algorithmus ist am wichtigsten
  • Es sollte geprüft werden, ob sich schwere Operationen wie Kernel-Aufrufe reduzieren lassen
  • Durch Vektorisierung lässt sich die Leistung verbessern
  • Es sollte geprüft werden, ob sich die Cache-Effizienz optimieren lässt
  • Es sollte geprüft werden, ob hardwarespezifische Optimierungen möglich sind

• Die im BLIS-Repository referenzierten Papers sind maßgebliche Quellen, um dieses Thema zu verstehen

  • Es ist unklar, warum man denkt, dass optimiertes BLAS keine gute Leistung liefert
  • Statt numpy sollte AMDs BLAS verwendet werden
  • BLIS ist besser parallelisiert als OpenBLAS

• SIMD-Instruktionen sind für die Vektorisierung des Mikrokernels nicht erforderlich

  • Mit geeigneten Blockgrößen erreicht der reine C-Mikrokernel von BLIS mehr als 80 % der Leistung handoptimierter Implementierungen

• Die meisten Coding-Patterns sind nicht vollständig auf die Hardware zugeschnitten und verschenken daher viel Leistung

  • Es lohnt sich, den klassischen CS-Aufsatz "There's plenty of room at the top" zu lesen

• Es ist lobenswert, dass sich die Benchmarks leicht reproduzieren lassen

  • Auf einer 16-Core-Xeon-CPU benötigt matmul.c, mit gcc -O3 kompiliert, 1,41 Sekunden, mit clang -O2 kompiliert 1,47 Sekunden, NumPy benötigt 1,07 Sekunden
  • Es wird angenommen, dass ein avx512-Kernel schneller wäre
  • Wenn man statt omp pthreads verwendet und den Thread-Pool explizit verwaltet, lässt sich der Overhead reduzieren

• Es wird bezweifelt, dass die Implementierung von numpy tatsächlich Multithreading verwendet

• Es stellt sich die Frage, warum die Leistung besser ist als bei OpenBLAS

  • Details wie Caching werden behandelt
  • Es ist fraglich, ob dies für einen bestimmten Prozessor stärker optimiert ist

• Ein Vergleich, bei dem die eine Seite Python und die andere C ist, ist nicht fair

  • Besser wäre ein Vergleich, bei dem beide in C geschrieben sind

• Die Ineffizienz bei der Maskenerzeugung fällt auf

  • Es gibt effizientere Methoden, etwa ein globales konstantes Array zu erzeugen oder mit einem konstanten Vektor zu vergleichen
  • Das ist jedoch ein nebensächliches Problem und dürfte in der Praxis keinen großen Unterschied machen

• Der praktische Nutzen, die Matrixmultiplikation selbst zu multithreaden, wird infrage gestellt

  • Multithreading wäre eher für Algorithmen nützlich, die Matrixmultiplikation verwenden

• Erwähnung von jarts tinyBLAS

  • Ein relevanter Link wird bereitgestellt