SIMD – Vektorisierung in .NET via C#

SIMD in .Net 7

Seit .NET 7 unterstützt C# das Emittieren von SIMD-Anweisungen (https://en.wikipedia.org/wiki/Single_instruction,_multiple_data) für verschiedene Architekturen. Seitdem wurden viele Verbesserungen an der Base Class Library (BCL) vorgenommen, um Vektorisierung zu nutzen, wenn dies anwendbar ist. Heute werden wir die Implementierung bestehender SIMD-optimierter Algorithmen mit C# erkunden. Notwendige Werkzeuge umfassen Visual Studio, BenchmarkDotNet sowie GodBolt / Compiler Explorer oder andere Mittel zur Untersuchung des generierten Assembly-Codes.

 

Die Theorie

Es gibt zwei mögliche Ansätze, um zu dem gewünschten SIMD-Code zu gelangen. Entweder können wir die Abstraktionen verwenden, die von der System.Runtime.Intrinsics.Vector256 (https://learn.microsoft.com/en-us/dotnet/api/system.runtime.intrinsics.vector256?view=net-9.0) Klasse bereitgestellt werden, oder wir können das target Instruction Set Architecture (ISA), die wir direkt anvisieren möchten, über System.Runtime.Intrinsics.ARM/WASM/x86 verwenden.
Die Vector-Klasse übernimmt einen Großteil der Arbeit, daher sollte sie bevorzugt werden, es sei denn, es ist absolut notwendig, spezifische Anweisungen zu verwenden. Ein kleiner Vorteil ist, dass die spezifischen ISA-Klassen eine bessere Dokumentation haben als die Vector-Klasse wenn es um die Assemblyoperationen geht, da die Vektorabstraktion offensichtlich Komplexität verbirgt.

 

Der Algorithmus – Zähle Elemente größer als X

Angenommen, man möchte die Anzahl der Elemente in einem Vektor zählen, die kleiner / größer als ein Wert X sind. Der einfache Algorithmus würde über den Vektor iterieren, eine JL/JG-Anweisung pro Element haben und bedingt einen Zählerwert inkrementieren. Ein naiver Algorithmus würde so aussehen:

Godbolt link: https://godbolt.org/z/K57cdWbx7

 

Auf zur Erstellung einer SIMD-Version dieses Algorithmus. In der ersten Iteration nehmen wir an, dass die Array-Länge ein Vielfaches von 8 ist und die zugrunde liegende Hardware unsere gewünschte Befehlssatzarchitektur unterstützt. Zunächst müssen wir einen Vektor erstellen, der das Grenzelement in jeder Position des Vektors enthält. Dafür können wir Vector.Create() verwenden. Zweitens benötigen wir ein leeres Register, um die Anzahl der gesetzten Werte zu zählen. Dies können wir über Vector256.Zero erhalten. Als nächstes iterieren wir über den Inhalt des übergebenen Spans in Vektoren der Größe 256. Dies kann durch die Verwendung der MemoryMarshal-Klasse erreicht werden, indem der ReadOnlySpan in einen ReadOnlySpan<Vector256> umgewandelt wird. Für jede Iteration verwenden wir die vpcmpgtd-Anweisung, um eine Vektormaske zu erstellen, die entweder -1 oder 0 enthält, je nachdem, ob das Element größer als unsere Grenze war. Wir subtrahieren diesen Vektor von unserem Zählvektor, wodurch wir den Zähler effektiv um eins für jedes erkannte Element inkrementieren können. Schließlich summieren wir nach dem Durchlaufen unserer Sammlung die Elemente im Zählvektor mit Vector.Sum

Annahmen vereinfachen

Ein aufmerksamer Leser könnte nun fragen: Wie beheben wir die zuvor auferlegten Einschränkungen? Der erste Schritt besteht darin zu überprüfen, ob unsere Hardware tatsächlich Beschleunigung für die von uns angeforderten Vektorgrößen unterstützt. Dies lässt sich leicht überprüfen, indem man eine if-Abfrage für Vector256.IsHardwareAccelerated hinzufügt. Die Property gibt an, dass die Vektoroperationen optimisiert sind, sofern die zugrundeliegende Hardware es unterstützt. Checks zu den individuellen ISA-Verfügbarkeiten kann man über die jeweilige ISA-Klasse bzw deren Vectorextension überprüfen (Avx2.IsSupported). Zweitens haben wir angenommen, dass die Länge des Spans ein Vielfaches von 8 ist. Dies kann behoben werden, indem überprüft wird, ob die Größe des Spans größer oder gleich Vector256.Count ist. Darüber hinaus können wir auch 4 Ganzzahlen gleichzeitig mit Vector128 verarbeiten, was bedeutet, dass wir unsere Akkumulationslogik für die letzten vollen 4 Elemente im Wesentlichen duplizieren können. Als letzten Schritt müssen wir den Code für alle Elemente einfügen, die Nachzügler sind, was bedeutet, dass Span.Length % 4 != 0, die wir manuell zählen müssen.

Benchmarks & Ergebnisse

Schließlich sind wir an dem Punkt angelangt, an dem wir unsere verschiedenen Implementierungen testen. Dafür werden wir BenchmarkDotNET verwenden, einen Industriestandard.

Wir können deutlich sehen, dass die vektorisierte Version erheblich schneller ist als der naive Ansatz. Das Testen verschiedener N-Werte für die Länge der Daten sollte Informationen über die spezifischen Cache-Größen der Hardware liefern können. Dies bleibt dem Leser als Übung überlassen.

 

Und jetzt? Können wir mehr rausholen?

Nun kommen wir zu den detaillierten Einzelheiten von SIMD, Hardwareunterstützung und Optimierung. Anfangs war ich mit dem bereitgestellten Code recht zufrieden. Ein besonderer Dank geht an Tanner Gooding (https://github.com/tannergooding), der an der Entwicklung von Hardware-Intrinsics und Numerics .NET bei Microsoft beteiligt ist, dafür, dass er den Code überprüft und einige weitere Optimierungen erwähnt hat. Es gibt immer noch einige Probleme, wie den Aufruf von MemoryMarshal.Cast, der Elemente fallen lässt, die nicht in den letzten Vektor passen, und theoretisch mehr Sprünge verursacht als eine einfache inkrementelle while-Schleife für jede Teilmengenlänge. Darüber hinaus könnten wir eine Variante von Duff’s Device verwenden, um eine Sprungtabelle nicht nur für die letzten Eingaben zu erstellen, sondern auch um unser Durchfallen im Fall kleiner Vektorgrößen zu beschleunigen, wie in den TensorPrimitives-Implementierungen zu sehen ist. (https://source.dot.net/#System.Numerics.Tensors/System/Numerics/Tensors/netcore/Common/TensorPrimitives.IAggregationOperator.cs,690) Dies würde insbesondere bei kleinen Eingabegrößen helfen. Wir könnten die Schleife entrollen, um die Anzahl der benötigten Sprünge bei größeren Eingabegrößen zu reduzieren. Eine weitere Optimierung, die wir „erzwingen“ könnten, wäre, dass der Span immer im Speicher ausgerichtet ist (NativeMemory.AlignedAlloc https://learn.microsoft.com/en-us/dotnet/api/system.runtime.interopservices.nativememory.alignedalloc?view=net-9.0). Zuletzt zerstören wir derzeit unseren Cache. Abhängig von der CPU haben Aufrufe auf den einzelnen Kernen nur eine bestimmte Menge an L1/L2/L3-Cache, bevor wir den RAM erreichen. Da wir nur an einem einzelnen int als Ausgabe interessiert sind, sollten wir die Werte aus dem Span nicht-temporal lesen (http://www.nic.uoregon.edu/~khuck/ts/acumem-report/manual_html/ch05s03.html). Dies ermöglicht es uns, den Cache frei zu halten. Wir könnten auch, abhängig von unserem Wissen über die Zielarchitektur, basierend auf unserem Wissen über die CPU, auf der wir laufen, optimieren. Wir könnten (und ich werde es nicht tun!) die maximal theoretischen GFLOPS berechnen, die wir auf unserer CPU erreichen können, wenn wir dies ohne den C#-Compiler implementieren, um einen minimalen ASM-Algorithmus zu erstellen, um zu sehen, was tatsächlich benötigt wird. Zuletzt müsste man Gleitkommazahlen berücksichtigen, wenn man diesen Algorithmus typunabhängig machen möchte. Da Floats und Doubles im Gegensatz zu anderen primitiven Zahlentypen nicht wohlgeordnet sind, müssen wir NaN für diese Typen berücksichtigen. Weitere Optimierungen bleiben dem Leser als Übung überlassen.

 

Weiterführende Informationen

Dieser Beitrag stammt von Niklas Schilli aus Berlin. Der Quellcode dazu ist hier zu finden: https://github.com/niklas-schilli-qbq/QUIBIQ.QUITEQ.SIMD

Das Buch https://en.algorithmica.org/hpc/ war hilfreich, um einige fortgeschrittene Konzepte im Umgang mit High-Performance Computing zu verstehen.

Der Intel Guide https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html# ist ebenfalls eine großartige Ressource, um spezifische SIMD-Anweisungen zu lernen.

GodBolt https://godbolt.org/ war auch von unschätzbarem Wert für die schnelle Inspektion von Assembly-Code. Source.NET hat es mir ermöglicht, den .NET-Quellcode zu inspizieren und mich von fortgeschrittenen Optimierungsmustern inspirieren zu lassen. https://source.dot.net/#