🕒 🌊 🦌 Ein kleiner Überblick über SIMD in .NET / C # 🤟🏻 🕺 😔

Hier ein kurzer Überblick über die Vektorisierungsfunktionen von Algorithmen in .NET Framework und .NET Core. Dieser Artikel richtet sich an diejenigen, die nichts über diese Techniken wissen. Ich werde auch zeigen, dass .NET für die native Entwicklung nicht hinter "echt kompilierten" Sprachen zurückbleibt.

Ich fange gerade an, Vektorisierungstechniken zu lernen. Ich würde mich freuen, wenn Community-Mitglieder eindeutige Fehler finden oder Verbesserungen der beschriebenen Algorithmen vorschlagen.

Etwas Geschichte

SIMD wurde 2015 in .NET Framework 4.6 veröffentlicht. Dann wurden die Typen Matrix3x2, Matrix4x4, Plane, Quaternion, Vector2, Vector3 und Vector4 hinzugefügt. Sie erlaubten vektorisierte Berechnungen. Als nächstes kam der Typ Vector <T>, der mehr Möglichkeiten zur Vektorisierung von Algorithmen bot. Viele Programmierer waren jedoch immer noch unzufrieden, da diese Typen die Ideenströme der Codierer einschränkten und nicht die volle Kapazität von SIMD-Anweisungen in modernen Prozessoren nutzen ließen. In der Vorschau von .NET Core 3.0 haben wir jetzt den System.Runtime.Intrinsics-Namespace, der viel Freiheit bei der Auswahl von Anweisungen bietet. Um die höchste Geschwindigkeit zu erzielen, müssen Sie RyuJit verwenden und entweder auf die x64-Assembly zurückgreifen oder ausschalten. Bevorzugen Sie 32-Bit und wählen Sie AnyCPU-Assembly. Ich habe alle Benchmarks auf einem Intel Core i7-6700 3,40 GHz (Skylake) CPU-Computer ausgeführt.

Array-Elemente summieren

Ich habe mich entschlossen, mit einer klassischen Aufgabe zu beginnen, die normalerweise an erster Stelle steht, wenn es um Vektorisierung geht. Es geht darum, die Summe der Array-Elemente zu finden. Schreiben wir vier Implementierungen dieser Aufgabe, um die Elemente von Array zu summieren.

Die naheliegendste Implementierung:

public int Naive() { int result = 0; foreach (int i in Array) { result += i; } return result; }

LINQ-basierte Implementierung:

 public long LINQ() => Array.Aggregate<int, long>(0, (current, i) => current + i);

Die Implementierung basiert auf Vektoren von 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; }

Die Implementierung basiert auf Code aus dem System.Runtime.Intrinsics-Namespace:

 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 diese 4 Methoden auf meinem Computer verglichen und die folgenden Ergebnisse erzielt:

Methode	ItemsCount	Mittelwert	Fehler	Stddev	Verhältnis
Naiv	10	3,531 ns	0,0336 ns	0,0314 ns	1,00
LINQ	10	76,925 ns	0,4166 ns	0,3897 ns	21.79
Vektoren	10	2,750 ns	0,0210 ns	0,0196 ns	0,78
Intrinsics	10	6,513 ns	0,0623 ns	0,0582 ns	1,84

Naiv	100	47,982 ns	0,3975 ns	0,3524 ns	1,00
LINQ	100	590,414 ns	3,8808 ns	3,4402 ns	12.31
Vektoren	100	10,122 ns	0,0747 ns	0,0699 ns	0,21
Intrinsics	100	14.277 ns	0,0566 ns	0,0529 ns	0,30

Naiv	1000	569.910 ns	2,8297 ns	2,6469 ns	1,00
LINQ	1000	5.658,570 ns	31,7465 ns	29.6957 ns	9.93
Vektoren	1000	79,598 ns	0,3498 ns	0,3272 ns	0,14
Intrinsics	1000	66,970 ns	0,3937 ns	0,3682 ns	0,12

Naiv	10.000	5.637,571 ns	37,5050 ns	29,2814 ns	1,00
LINQ	10.000	56.498.987 ns	294.8776 ns	275,8287 ns	10.02
Vektoren	10.000	772.900 ns	2,6802 ns	2,5070 ns	0,14
Intrinsics	10.000	579,152 ns	2,8371 ns	2,6538 ns	0,10

Naiv	100.000	56.352,865 ns	230,7916 ns	215,8826 ns	1,00
LINQ	100.000	562,610,571 ns	3,775.7631 ns	3,152.9332 ns	9.98
Vektoren	100.000	8,389.647 ns	165,9590 ns	227,1666 ns	0,15
Intrinsics	100.000	7,261.334 ns	89,6468 ns	69.9903 ns	0,13

Es ist klar, dass Lösungen mit Vektoren und Intrinsics viel schneller sind als die offensichtlichen und LINQ-basierten Lösungen. Jetzt müssen wir herausfinden, was in diesen beiden Methoden vor sich geht.

Betrachten wir die Vektorenmethode 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; - Die Anzahl der 4-Byte-Zahlen, die wir in einen Vektor einfügen können. Wenn die Hardwarebeschleunigung verwendet wird, zeigt dieser Wert an, wie viele 4-Byte-Nummern in ein SIMD-Register eingefügt werden können. Tatsächlich wird angezeigt, wie viele Elemente dieses Typs gleichzeitig verarbeitet werden können.
accVector ist ein Vektor, der das Ergebnis der Funktion akkumuliert.
var v = neuer Vektor <int> (Array, i); - Die Daten aus dem Array werden beginnend mit dem i-Index in einen neuen v-Vektor geladen. Die Vektorgröße der Daten wird genau geladen.
accVector = Vector.Add (accVector, v); - Zwei Vektoren werden summiert.
Zum Beispiel enthält Array 8 Zahlen: {0, 1, 2, 3, 4, 5, 6, 7} und vectorSize == 4.
Während des ersten Zyklus iteriert accVector = {0, 0, 0, 0}, v = {0, 1, 2, 3} und nach der Addition hält accVector: {0, 0, 0, 0} + {0, 1 , 2, 3} = {0, 1, 2, 3}.
Während 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}.
Jetzt müssen wir nur noch die Summe aller Vektorelemente erhalten. Dazu können wir die Skalarmultiplikation mit einem mit Einsen gefüllten Vektor verwenden: int result = Vector.Dot (accVector, Vector <int> .One);
Dann erhalten wir: {4, 6, 8, 10} * {1, 1, 1, 1} = 4 * 1 + 6 * 1 + 8 * 1 + 10 * 1 = 28.
Falls erforderlich, werden die Zahlen, die nicht zum letzten Vektor passen, am Ende summiert.

Schauen wir uns den Intrinsics-Code an:

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; }

Wir können sehen, dass es mit einer Ausnahme wie Vektoren ist:

vectorSize wird durch eine Konstante angegeben. Dies liegt daran, dass diese Methode explizit Avx2-Anweisungen verwendet, die mit 256-Bit-Registern arbeiten. Eine echte Anwendung sollte eine Überprüfung enthalten, ob ein aktueller Prozessor Avx2 unterstützt. Wenn nicht, sollte ein anderer Code aufgerufen werden. Es sieht so aus:
```
 if (Avx2.IsSupported) { DoThingsForAvx2(); } else if (Avx.IsSupported) { DoThingsForAvx(); } ... else if (Sse2.IsSupported) { DoThingsForSse2(); } ... 
```
var accVector = Vector256 <int> .Zero; accVector wird als 256-Bit-Vektor deklariert, der mit Nullen gefüllt ist.
fest (int * ptr = Array) - Der Zeiger auf das Array wird in ptr platziert.
Als nächstes folgen die gleichen Operationen wie in Vektoren: Laden von Daten in einen Vektor und Hinzufügen von zwei Vektoren.
Die Summierung von Vektorelementen erfolgt nach folgender Methode:
- Erstellen Sie ein Array auf dem Stapel: var temp = stackalloc int [vectorSize];
- Laden Sie einen Vektor in dieses Array: Avx2.Store (temp, accVector);
- Summenarray-Elemente während des Zyklus.
Als nächstes werden die Elemente zusammengefasst, die nicht zum letzten Vektor passen.

Zwei Arrays vergleichen

Wir müssen zwei Arrays von Bytes vergleichen. Genau diese Aufgabe hat mich dazu gebracht, SIMD in .NET zu studieren. Lassen Sie uns noch einmal verschiedene Methoden für das Benchmarking schreiben und 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; }

LINQ-basierte Lösung:

 public bool LINQ() => ArrayA.SequenceEqual(ArrayB);

Die Lösung basierend auf der 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;

Die Lösung basiert auf Vektoren von 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; }

Intrinsics-basierte Lösung:

 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; } }

Die Ergebnisse der Ausführung des Benchmarks auf meinem Computer:

Methode	ItemsCount	Mittelwert	Fehler	Stddev	Verhältnis
Naiv	10.000	7.033,8 ns	50,636 ns	47,365 ns	1,00
LINQ	10.000	64.841,4 ns	289,157 ns	270,478 ns	9.22
Vektoren	10.000	504,0 ns	2,406 ns	2,251 ns	0,07
Memcmp	10.000	368,1 ns	2,637 ns	2,466 ns	0,05
Intrinsics	10.000	283,6 ns	1,135 ns	1,061 ns	0,04

Naiv	100.000	85.214,4 ns	903,868 ns	845,478 ns	1,00
LINQ	100.000	702.279,4 ns	2,846.609 ns	2,662.720 ns	8.24
Vektoren	100.000	5,179,2 ns	45,337 ns	42,409 ns	0,06
Memcmp	100.000	4,510,5 ns	24,292 ns	22.723 ns	0,05
Intrinsics	100.000	2.957,0 ns	11.452 ns	10,712 ns	0,03

Naiv	1.000.000	844.006,1 ns	3,552.478 ns	3,322.990 ns	1,00
LINQ	1.000.000	6.483.079,3 ns	42.641,040 ns	39.886,455 ns	7.68
Vektoren	1.000.000	54.180,1 ns	357,258 ns	334.180 ns	0,06
Memcmp	1.000.000	49.480,1 ns	515,675 ns	457,133 ns	0,06
Intrinsics	1.000.000	36.633,9 ns	680,525 ns	636,564 ns	0,04

Ich denke, der Code dieser Methoden ist klar, mit Ausnahme von zwei Zeilen in Intrinsics:

 var areEqual = Avx2.CompareEqual(va, vb); if (Avx2.MoveMask(areEqual) != equalsMask) { return false; }

In der ersten Zeile werden zwei Vektoren auf Gleichheit verglichen und das Ergebnis in einem gleichen Vektor gespeichert, in dem alle Bits im Element an einer bestimmten Position auf 1 gesetzt werden, wenn die entsprechenden Elemente in va und vb gleich sind. Es stellt sich also heraus, dass, wenn die Bytevektoren va und vb gleich sind, alle Elemente in areEquals gleich 255 (11111111b) sein sollten. Da Avx2.CompareEqual ein Wrapper über _mm256_cmpeq_epi8 ist, können wir auf der Intel-Website den Pseudocode dieser Operation anzeigen:
Die MoveMask-Methode erstellt aus einem Vektor eine 32-Bit-Zahl. Die oberen Bits von jeweils 32 Ein-Byte-Elementen in einem Vektor sind die Werte der Bits im MoveMask-Ergebnis. Der Pseudocode ist hier verfügbar.

Wenn also einige Bytes in va und vb nicht übereinstimmen, sind die entsprechenden Bytes in areEqual 0. Daher sind auch die oberen Bits dieser Bytes 0. Dies bedeutet, dass die entsprechenden Bits in der Avx2.MoveMask-Antwort ebenfalls 0 sind und areEqual nicht gleich equalsMask ist.

Schauen wir uns ein Beispiel an, bei dem angenommen wird, dass die Vektorlänge 8 Bytes beträgt (um weniger zu schreiben):

Sei va = {100, 10, 20, 30, 100, 40, 50, 100} und vb = {100, 20, 10, 30, 100, 40, 80, 90}.
Dann sind areEquals {255, 0, 0, 255, 255, 255, 0, 0}.
Die MoveMask-Methode gibt 10011100b zurück, die mit der 11111111b-Maske verglichen werden soll. Da diese Masken nicht gleich sind, sind auch die Vektoren va und vb nicht gleich.

Zählen der Häufigkeit, mit der ein Element in einer Sammlung vorkommt.

Manchmal müssen Sie die Vorkommen eines bestimmten Elements, z. B. Ganzzahlen, in einer Sammlung zählen. Wir können diesen Algorithmus auch beschleunigen. Zum Vergleich schreiben wir verschiedene Methoden, um das Element Item in Array zu durchsuchen.

Das offensichtlichste:

 public int Naive() { int result = 0; foreach (int i in Array) { if (i == Item) { result++; } } return result; }

Verwenden von 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; var temp = stackalloc int[vectorSize]; for (int j = 0; j < vectorSize; j++) { temp[j] = Item; } var mask = Avx2.LoadVector256(temp); 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); var areEqual = Avx2.CompareEqual(v, mask); accVector = Avx2.Subtract(accVector, areEqual); } } int result = 0; Avx2.Store(temp, accVector); for(int j = 0; j < vectorSize; j++) { result += temp[j]; } for(; i < array.Length; i++) { if (array[i] == Item) { result++; } } return result; }

Die Ergebnisse der Ausführung des Benchmarks auf meinem Computer:

Methode	ItemsCount	Mittelwert	Fehler	Stddev	Verhältnis
Naiv	10	8,844 ns	0,0772 ns	0,0603 ns	1,00
LINQ	10	87,456 ns	0,9496 ns	0,8883 ns	9,89
Vektoren	10	3,140 ns	0,0406 ns	0,0380 ns	0,36
Intrinsics	10	13.813 ns	0,0825 ns	0,0772 ns	1,56

Naiv	100	107,310 ns	0,6975 ns	0,6183 ns	1,00
LINQ	100	626,285 ns	5,7677 ns	5,3951 ns	5.83
Vektoren	100	11.844 ns	0,2113 ns	0,1873 ns	0,11
Intrinsics	100	19.616 ns	0,1018 ns	0,0903 ns	0,18

Naiv	1000	1.032,466 ns	6,3799 ns	5,6556 ns	1,00
LINQ	1000	6,266.605 ns	42,6585 ns	39,9028 ns	6.07
Vektoren	1000	83,417 ns	0,5393 ns	0,4780 ns	0,08
Intrinsics	1000	88,358 ns	0,4921 ns	0,4603 ns	0,09

Naiv	10.000	9.942,503 ns	47,9732 ns	40.0598 ns	1,00
LINQ	10.000	62.305.598 ns	643,8775 ns	502,6972 ns	6.27
Vektoren	10.000	914,967 ns	7,2959 ns	6,8246 ns	0,09
Intrinsics	10.000	931.698 ns	6,3444 ns	5,9346 ns	0,09

Naiv	100.000	94.834,804 ns	793,8585 ns	703,7349 ns	1,00
LINQ	100.000	626.620.968 ns	4,696.9221 ns	4.393,5038 ns	6.61
Vektoren	100.000	9.000,827 ns	179,5351 ns	192.1005 ns	0,09
Intrinsics	100.000	8,690,771 ns	101,7078 ns	95,1376 ns	0,09

Naiv	1.000.000	959,302,249 ns	4,268.2488 ns	3,783.6914 ns	1,00
LINQ	1.000.000	6,218,681.888 ns	31.321,9277 ns	29.298.5506 ns	6.48
Vektoren	1.000.000	99.778,488 ns	1,975.6001 ns	4,252.6877 ns	0,10
Intrinsics	1.000.000	96.449,350 ns	1,171.8067 ns	978,5116 ns	0,10

Vektoren und Intrinsics-Methoden stimmen in der Logik vollständig überein, unterscheiden sich jedoch in der Implementierung bestimmter Operationen. Die Idee ist die folgende:

Erstellen Sie einen Maskenvektor, in dem in jedem Element eine erforderliche Anzahl gespeichert ist.
Laden Sie den Teil eines Arrays in den Vektor v und vergleichen Sie diesen Teil mit einer Maske. Infolgedessen werden alle Bits in gleiche Elemente von areEqual gesetzt. Da areEqual ein Array von ganzen Zahlen ist, erhalten wir, wenn wir alle Bits eines Elements setzen, -1 in diesem Element ((int) (1111_1111_1111_1111_1111_1111_1111_1111b) == -1);
subtrahieren areEqual Vektor von accVector. Dann speichert accVector, wie oft das Elementelement in allen Vektoren für jede Position aufgetreten ist (Minus mal Minus ist ein Plus).

Der gesamte Code aus dem Artikel ist auf GitHub .

Fazit

Ich habe nur einen kleinen Teil der .NET-Funktionen für die Berechnungsvektorisierung beschrieben. Um die vollständige aktualisierte Liste aller in .NET Core unter x86 verfügbaren Intrinsics anzuzeigen, wenden Sie sich an den Quellcode . Es ist praktisch, dass die Zusammenfassung aller in C # -Dateien enthaltenen Elemente ihren Namen in der C-Welt enthält. Dies hilft entweder, den Zweck dieser Eigenschaft zu verstehen oder vorhandene C ++ / C-Algorithmen auf .NET zu übertragen. Die Dokumentation zu System.Numerics.Vector ist auf msdn verfügbar.

Ich denke, .NET hat einen großen Vorteil gegenüber C ++. Da die JIT-Kompilierung bereits auf einem Clientcomputer erfolgt, kann ein Compiler den Code für einen bestimmten Clientprozessor optimieren und so maximale Leistung erzielen. Gleichzeitig kann ein Programmierer in einer Sprache und denselben Technologien bleiben, um schnellen Code zu schreiben.

Ein kleiner Überblick über SIMD in .NET / C #

Etwas Geschichte

Array-Elemente summieren

Zwei Arrays vergleichen

Zählen der Häufigkeit, mit der ein Element in einer Sammlung vorkommt.

Fazit

More articles: