Ihre Aufmerksamkeit wird auf einen kleinen Überblick über die Möglichkeiten der Vektorisierung von Algorithmen in .NET Framework und .NETCORE gelenkt. Der Zweck des Artikels ist es, diese Techniken denjenigen vorzustellen, die sie überhaupt nicht kannten, und zu zeigen, dass .NET nicht weit hinter den "echten, kompilierten" Sprachen für den Muttersprachler zurückbleibt
Entwicklung.
Ich fange gerade erst an, Vektorisierungstechniken zu lernen. Wenn mich also jemand aus der Community auf eine explizite Neigung hinweist oder verbesserte Versionen der unten beschriebenen Algorithmen vorschlägt, bin ich sehr glücklich.
Ein bisschen Geschichte
In .NET erschien SIMD erstmals 2015 mit der Veröffentlichung von .NET Framework 4.6. Dann wurden die Typen Matrix3x2, Matrix4x4, Ebene, Quaternion, Vektor2, Vektor3 und Vektor4 hinzugefügt, die die Erstellung vektorisierter Berechnungen ermöglichten. Später wurde der Typ Vector <T> hinzugefügt, der mehr Möglichkeiten zur Vektorisierung von Algorithmen bot. Aber viele Programmierer waren immer noch unglücklich, weil Die oben genannten Typen schränkten den Gedankenfluss des Programmierers ein und erlaubten nicht die volle Leistung der SIMD-Anweisungen moderner Prozessoren. Bereits heute wurde in der .NET Core 3.0-Vorschau der System.Runtime.Intrinsics-Namespace angezeigt, der viel mehr Freiheit bei der Auswahl von Anweisungen bietet. Um die besten Geschwindigkeitsergebnisse zu erzielen, müssen Sie RyuJit verwenden und entweder unter x64 erstellen oder Prefer 32-bit deaktivieren und unter AnyCPU erstellen. Alle Benchmarks, die ich auf einem Computer mit einem Intel Core i7-6700-Prozessor mit 3,40 GHz (Skylake) ausgeführt habe.
Fassen Sie die Elemente des Arrays zusammen
Ich habe mich entschlossen, mit dem klassischen Problem zu beginnen, das bei der Vektorisierung oft zuerst geschrieben wird. Dies ist die Aufgabe, die Summe der Elemente des Arrays zu ermitteln. Wir werden vier Implementierungen dieser Aufgabe schreiben und die Elemente des Array-Arrays zusammenfassen:
Am offensichtlichsten
public int Naive() { int result = 0; foreach (int i in Array) { result += i; } return result; }
Verwenden von LINQ
public long LINQ() => Array.Aggregate<int, long>(0, (current, i) => current + i);
Verwenden von Vektoren aus System.Numerics:
public int Vectors() { int vectorSize = Vector<int>.Count; var accVector = Vector<int>.Zero; int i; var array = Array; for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); accVector = Vector.Add(accVector, v); } int result = Vector.Dot(accVector, Vector<int>.One); for (; i < array.Length; i++) { result += array[i]; } return result; }
Verwenden von Code aus dem System.Runtime.Intrinsics-Bereich:
public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); accVector = Avx2.Add(accVector, v); } } int result = 0; var temp = stackalloc int[vectorSize]; Avx2.Store(temp, accVector); for (int j = 0; j < vectorSize; j++) { result += temp[j]; } for (; i < array.Length; i++) { result += array[i]; } return result; }
Ich habe einen Benchmark für diese 4 Methoden auf meinem Computer gestartet und folgendes Ergebnis erhalten:
Es ist ersichtlich, dass die Lösungen mit Vektoren und Intrinsics sehr viel schneller sind als die offensichtliche Lösung und mit LINQ. Jetzt müssen wir herausfinden, was bei diesen beiden Methoden passiert.
Betrachten Sie die Vektoren-Methode genauer:
Vektoren public int Vectors() { int vectorSize = Vector<int>.Count; var accVector = Vector<int>.Zero; int i; var array = Array; for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); accVector = Vector.Add(accVector, v); } int result = Vector.Dot(accVector, Vector<int>.One); for (; i < array.Length; i++) { result += array[i]; } return result; }
- int vectorSize = Vector <int> .Count; - So viele 4-Byte-Zahlen können wir in einen Vektor einfügen. Wenn die Hardwarebeschleunigung verwendet wird, zeigt dieser Wert an, wie viele 4-Byte-Nummern in einem SIMD-Register abgelegt werden können. Tatsächlich wird angezeigt, wie viele Elemente dieses Typs Sie parallel ausführen können.
- accVector - ein Vektor, in dem sich das Ergebnis der Funktion ansammelt;
var v = neuer Vektor <int> (Array, i); - Daten werden ausgehend vom Index i aus dem Array in einen neuen Vektor v geladen. Es werden genau vectorSize-Daten geladen. - accVector = Vector.Add (accVector, v); - Es werden zwei Vektoren hinzugefügt.
Zum Beispiel werden 8 Zahlen in Array gespeichert: {0, 1, 2, 3, 4, 5, 6, 7} und vectorSize == 4, dann:
In der ersten Iteration der Schleife accVector = {0, 0, 0, 0}, v = {0, 1, 2, 3} ist es nach der Addition in accVector: {0, 0, 0, 0} + {0, 1, 2 , 3} = {0, 1, 2, 3}.
In der zweiten Iteration ist v = {4, 5, 6, 7} und nach Addition accVector = {0, 1, 2, 3} + {4, 5, 6, 7} = {4, 6, 8, 10}. - Es bleibt nur irgendwie die Summe aller Elemente des Vektors zu erhalten, dafür können wir die Skalarmultiplikation mit einem mit Einheiten gefüllten Vektor anwenden: int result = Vector.Dot (accVector, Vector <int> .One);
Dann stellt sich heraus: {4, 6, 8, 10} {1, 1, 1, 1} = 4 1 + 6 1 + 8 1 + 10 * 1 = 28. - Am Ende werden bei Bedarf Zahlen addiert, die nicht in den letzten Vektor passen.
Wenn Sie sich den Intrinsics-Methodencode ansehen:
Intrinsics public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); accVector = Avx2.Add(accVector, v); } } int result = 0; var temp = stackalloc int[vectorSize]; Avx2.Store(temp, accVector); for (int j = 0; j < vectorSize; j++) { result += temp[j]; } for (; i < array.Length; i++) { result += array[i]; } return result; }
Sie können sehen, dass es Vektoren mit wenigen Ausnahmen sehr ähnlich ist:
Vergleichen Sie zwei Arrays
Es ist notwendig, zwei Arrays von Bytes zu vergleichen. Eigentlich ist dies das Problem, aufgrund dessen ich angefangen habe, SIMD in .NET zu lernen. Wieder werden wir verschiedene Methoden für den Benchmark schreiben, wir werden zwei Arrays vergleichen: ArrayA und ArrayB:
Die naheliegendste Lösung:
public bool Naive() { for (int i = 0; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; }
Lösung über LINQ:
public bool LINQ() => ArrayA.SequenceEqual(ArrayB);
Lösung über MemCmp-Funktion:
[DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl)] static extern int memcmp(byte[] b1, byte[] b2, long count); public bool MemCmp() => memcmp(ArrayA, ArrayB, ArrayA.Length) == 0;
Verwenden von Vektoren aus System.Numerics:
public bool Vectors() { int vectorSize = Vector<byte>.Count; int i = 0; for (; i < ArrayA.Length - vectorSize; i += vectorSize) { var va = new Vector<byte>(ArrayA, i); var vb = new Vector<byte>(ArrayB, i); if (!Vector.EqualsAll(va, vb)) { return false; } } for (; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; }
Verwenden von Intrinsics:
public unsafe bool Intrinsics() { int vectorSize = 256 / 8; int i = 0; const int equalsMask = unchecked((int) (0b1111_1111_1111_1111_1111_1111_1111_1111)); fixed (byte* ptrA = ArrayA) fixed (byte* ptrB = ArrayB) { for (; i < ArrayA.Length - vectorSize; i += vectorSize) { var va = Avx2.LoadVector256(ptrA + i); var vb = Avx2.LoadVector256(ptrB + i); var areEqual = Avx2.CompareEqual(va, vb); if (Avx2.MoveMask(areEqual) != equalsMask) { return false; } } for (; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; } }
Das Ergebnis des Benchmarks auf meinem Computer:
Der gesamte Code für diese Methoden ist meines Erachtens verständlich, mit Ausnahme von zwei Zeilen in Intrinsics:
var areEqual = Avx2.CompareEqual(va, vb); if (Avx2.MoveMask(areEqual) != equalsMask) { return false; }
Im ersten Schritt werden zwei Vektoren auf Gleichheit verglichen und das Ergebnis in dem Vektor areEqual gespeichert, in dem alle Bits in einem Element an einer bestimmten Position auf 1 gesetzt werden, wenn die entsprechenden Elemente in va und vb gleich sind. Es stellt sich heraus, dass, wenn die Vektoren aus den Bytes va und vb vollständig gleich sind, in areEquals alle Elemente gleich 255 (11111111b) sein sollten. Weil Avx2.CompareEqual ist ein Wrapper über _mm256_cmpeq_epi8. Auf der Intel-Website können Sie den Pseudocode dieser Operation sehen:
Die MoveMask-Methode aus einem Vektor erstellt eine 32-Bit-Zahl. Die Bitwerte sind die hohen Bits jedes der 32 Einzelbyte-Elemente des Vektors. Pseudocode finden Sie hier .
Wenn also einige Bytes in va und vb nicht übereinstimmen, sind in areEqual die entsprechenden Bytes 0, daher sind die höchstwertigen Bits dieser Bytes ebenfalls 0, was bedeutet, dass die entsprechenden Bits in der Avx2.MoveMask-Antwort ebenfalls 0 und der Vergleich sind mit equalsMask funktioniert nicht.
Analysieren wir ein kleines Beispiel unter der Annahme, dass die Länge des Vektors 8 Bytes beträgt (zum Schreiben war es weniger):
- Sei va = {100, 10, 20, 30, 100, 40, 50, 100} und vb = {100, 20, 10, 30, 100, 40, 80, 90};
- Dann ist areEqual gleich {255, 0, 0, 255, 255, 255, 0, 0};
- Die MoveMask-Methode gibt 10011100b zurück, was mit der Maske 11111111b verglichen werden muss, weil Da diese Masken ungleich sind, stellt sich heraus, dass die Vektoren va und vb nicht gleich sind.
Zählen Sie, wie oft ein Element in der Sammlung vorkommt
Manchmal muss berechnet werden, wie oft ein bestimmtes Element in einer Sammlung gefunden wird, z. B. Ints. Dieser Algorithmus kann auch beschleunigt werden. Lassen Sie uns einige Methoden zum Vergleich schreiben. Wir werden nach dem Item-Element im Array-Array suchen.
Das offensichtlichste:
public int Naive() { int result = 0; foreach (int i in Array) { if (i == Item) { result++; } } return result; }
mit LINQ:
public int LINQ() => Array.Count(i => i == Item);
Verwenden von Vektoren aus System.Numerics.Vectors:
public int Vectors() { var mask = new Vector<int>(Item); int vectorSize = Vector<int>.Count; var accResult = new Vector<int>(); int i; var array = Array; for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); var areEqual = Vector.Equals(v, mask); accResult = Vector.Subtract(accResult, areEqual); } int result = 0; for (; i < array.Length; i++) { if (array[i] == Item) { result++; } } result += Vector.Dot(accResult, Vector<int>.One); return result; }
Verwenden von Intrinsics:
public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4;
Das Ergebnis des Benchmarks auf meinem Computer:
Die Methoden Vectors und Intrinsics sind in der Logik völlig identisch, die Unterschiede bestehen nur in der Implementierung spezifischer Operationen. Die Idee als Ganzes ist:
- Es wird ein Maskenvektor erstellt, in dem die erforderliche Anzahl in jedem Element gespeichert ist.
- Der Teil des Arrays wird in den Vektor v geladen und mit der Maske verglichen, dann werden alle Bits in areEqual in gleiche Elemente gesetzt, weil areEqual ist ein Vektor aus Ints. Wenn Sie also alle Bits eines Elements setzen, erhalten wir -1 in diesem Element ((int) (1111_1111_1111_1111_1111_1111_1111_1111b) == -1);
- Der Vektor areEqual wird von accVector subtrahiert, und dann ist der accVector die Summe, wie oft das Elementelement in allen Vektoren v für jede Position aufgetreten ist (minus min ergibt ein Plus).
Der gesamte Code aus dem Artikel ist auf GitHub zu finden
Fazit
Ich habe nur einen sehr kleinen Teil der Möglichkeiten untersucht, die .NET für die Vektorisierung von Berechnungen bietet. Eine vollständige und aktuelle Liste der in .NETCORE unter x86 verfügbaren Intrinsics finden Sie im Quellcode . Es ist praktisch, dass in den C # -Dateien in der Zusammenfassung jedes Intrinsics ein eigener Name aus der Welt von C enthalten ist, was das Verständnis des Zwecks dieses Intrinsics und die Übersetzung vorhandener C ++ / C-Algorithmen in .NET vereinfacht. Die Dokumentation zu System.Numerics.Vector finden Sie unter msdn .
Meiner Meinung nach hat .NET einen großen Vorteil gegenüber C ++, weil Die JIT-Kompilierung findet bereits auf dem Client-Computer statt. Der Compiler kann den Code für einen bestimmten Client-Prozessor optimieren und bietet so maximale Leistung. Gleichzeitig kann ein Programmierer zum Schreiben von schnellem Code im Rahmen einer Sprache und Technologie bleiben.
UPD (15.09.2019):
Es gab einen Pfosten in BenchmarksIn Benchmarks habe ich IterationSetup verwendet, was, wie sich herausstellte, die Leistung von Benchmarks, die in weniger als 100 ms funktionieren, stark beeinträchtigen kann. Wenn Sie es in GlobalSetup wiederholen, sehen die Ergebnisse folgendermaßen aus.
Summe der Array-Elemente:
Vergleich zweier Arrays:
Die Anzahl der Vorkommen eines Elements in einem Array: