SIMD-Algorithmen von Grund auf entwerfen

Entwurf von SIMD-Algorithmen

• Erklärung zur SIMD-Optimierung: SIMD steht für Single Instruction, Multiple Data, und man muss dabei wie ein Schaltungsdesigner denken.
• SIMD wird häufig im Zusammenhang mit Performance und HPC (High Performance Computing) erwähnt, ist für Einsteiger aber kein vertrautes Thema.
• In den meisten Programmiersprachen sind SIMD-Programmier-APIs schwer zu benutzen.
• SIMD-Algorithmen lassen sich mit einer prozeduralen Programmierweise nur schwer verstehen; funktionale Programmierung kann dabei helfen.
• Der Text handelt von vb64, einer Implementierung eines Base64-Codecs mit Rusts Bibliothek std::simd.

Physikalische Grenzen

• Computer existieren in der realen Welt und sind an die Gesetze der Physik gebunden.
• In der frühen Ära des Computings ließ sich die Leistung durch den Kauf eines neuen Computers steigern.
• Der Effekt des Dennard-Scalings ist zusammengebrochen, sodass kleinere Transistoren einen höheren Stromverbrauch bedeuten.
• Mehr Kerne wurden zum neuen Trend. Über Multithreading lässt sich die CPU-Leistung steigern, allerdings entsteht dabei Synchronisations-Overhead.

Warum prozeduraler Code langsam ist

• Moderne CPU-Kerne führen Code nicht zeilenweise aus.
• Durch Instruction-Level Parallelism können mehrere Operationen gleichzeitig ausgeführt werden, wenn keine Datenabhängigkeiten bestehen.
• Die Parallelität steigt, wenn der Compiler Datengefahren auflösen kann.
• Verzweigungen und Speicheroperationen verursachen Stalls, was Code langsamer macht.

SIMD und Lanes

• SIMD und Vektor werden oft synonym verwendet.
• SIMD-Instruktionen verwenden Vektoren als Grundeinheit, also Arrays von Zahlen fester Größe.
• Jedes Element eines Vektors wird als Lane bezeichnet, und SIMD-Vektoren sind normalerweise eher klein.

Operationen auf echten Vektoren

• SIMD-Vektoren bieten komplexere Operationen als gewöhnliche Register.
• Vektorregister unterstützen viele verschiedene Operationen, darunter Bit-Operationen, arithmetische Operationen pro Lane, Vergleiche pro Lane und Shuffles.
• Shuffles sind in der SIMD-Programmierung wichtig, um Daten an die richtigen Positionen zu verschieben.

Intrinsics und Instruction Selection

• Welche Operationen beim Schreiben von SIMD-Code verfügbar sind, hängt von der Architektur ab.
• Der Compiler löst dabei das Problem der Instruction Selection und entscheidet, mit welchen Instruktionen eine vom Nutzer angeforderte Operation umgesetzt wird.
• Portablen SIMD-Code zu schreiben ist komplex, aber mit Laufzeit-Erkennung von Features lässt sich auf verschiedenen Prozessoren optimaler Code erzeugen.

Parsing mit SIMD

• Text lässt sich mit SIMD parsen, und das kann sehr schnell sein.
• Ein Beispiel dafür ist die Implementierung von Base64-Decoding mit SIMD.
• Der entscheidende Schritt beim Erstellen einer SIMD-Version ist, alle Verzweigungen zu entfernen.

Meinung von GN⁺

Das Wichtigste an diesem Artikel ist, dass SIMD-Programmierung im Unterschied zur herkömmlichen prozeduralen Programmierung Daten parallel verarbeitet und so die Leistung verbessern kann. SIMD ist im Bereich High Performance Computing von großer Bedeutung, und besonders in modernen Programmiersprachen wie Rust zu verstehen, wie sich SIMD effektiv einsetzen lässt, kann für Softwareingenieure ein äußerst interessantes Thema sein. Denn mit SIMD kann man lernen, komplexe Algorithmen zu optimieren und die Grenzen realer Hardware zu überwinden.

[GN⁺]

Hacker-News-Kommentare

• Ein großartiger Artikel, der einen Anwendungsfall für portables SIMD zeigt. Ich habe die Benchmarks auf einem Zen-3-System reproduziert und denselben Geschwindigkeitsgewinn bestätigt. Auf einem M1 mbp steigt der Leistungsgewinn bei einer Eingabelänge von 110 Byte allmählich auf bis zu das Doppelte. Der Gewinn ist geringer als auf x86_64, aber das Ziel scheint erreicht worden zu sein. Allerdings zeigt sich auch, dass Rust bei SIMD- und Pointer-bezogenen Arbeiten sowie beim Performance Engineering insgesamt etwas umständlich ist.
• Es ist manchmal erstaunlich, dass selbst wenn man in C++ sein Bestes gibt, eine Version mit SIMD mehr als die 10-fache Geschwindigkeit zeigen kann. Die Portabilität des Codes leidet zwar darunter, aber man wünscht sich, dass Compiler automatische Vektorisierung besser beherrschen würden. Es wäre schön, wenn Sprachen Unterstützung dafür bekämen, die Reihenfolge bestimmter Operationen per Annotation umordnen zu können.
• Es wird darauf hingewiesen, dass der Compiler eine bestimmte popcount-Implementierung nicht zu einer einzelnen Instruktion optimieren konnte, dies aber bei einer anderen Implementierung unter Umständen möglich ist.
• _mm256_cvtps_epu32 ist keine AVX2-Instruktion, sondern eine AVX-512-Instruktion; bei AVX1 liegen Ganzzahlen in vorzeichenbehafteter Form vor, und die entsprechende Instruktion ist _mm256_cvtps_epi32.
• Die kleine Minimap auf der rechten Seite gefällt mir sehr.
• ISPC wird als besser bewertet, als SIMD zu C++ oder Rust hinzuzufügen. Außerdem unterstützt es dynamisches Dispatching, was direkt selbst zu implementieren schwierig ist.
• Es wird gefragt, wie es im Vergleich zu fastbase64 aussieht, und zugleich die Meinung geäußert, dass man die optimistische Haltung des Autors gegenüber portablen SIMD-Bibliotheken teilen möchte.
• Ein großartiger Artikel, der den Eindruck hinterlässt, dass man selbst wohl nie so klug werden könnte.
• Obwohl erwähnt wurde, dass das erste Beispiel einer nicht vektorisierten popcnt-Implementierung „ehrlich gesagt lächerlichen Code“ erzeugt, scheint die Funktion bei Kompilierung im Release-Modus für die native Ziel-CPU doch recht ordentlich vektorisiert zu werden.
• Ein ziemlich guter Versuch zu Rust Simd. Es wird die Frage gestellt, was beim Untersuchen des generierten Codes die überraschendste Auffälligkeit war.