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

    Wir bieten Ihnen einen kleinen Überblick über die Möglichkeiten der Vektorisierung von Algorithmen in .NET Framework und .NETCORE. Der Artikel soll diejenigen Techniken vorstellen, die diese überhaupt nicht kannten, und zeigen, dass .NET nicht weit von den "echten" kompilierten Sprachen für die native
    Entwicklung entfernt ist.


    Я только начинаю изучать приёмы векторизации, так что если кто из сообщества укажет мне на явные косяк, или предложит улучшенные версии описанных ниже алгоритмов, то буду дико рад.


    Немного истории


    В .NET SIMD впервые появился в 2015 году с выходом .NET Framework 4.6. Тогда были добавлены типы Matrix3x2, Matrix4x4, Plane, Quaternion, Vector2, Vector3 и Vector4, которые позволили прозводить векторизированные вычисления. Позже был добавлен тип Vector<T>, который предоставил больше возможностей для векторизации алгоритмов. Но многие программисты всё равно были недовольны, т.к. вышеописанные типы ограничивали поток мыслей программиста и не давали возможности использовать полную мощь SIMD-инструкций современных процессоров. Уже в наше время, в .NET Core 3.0 Preview появилось пространство имён System.Runtime.Intrinsics, которое предоставляет гораздо большую свободу в выборе инструкций. Чтобы получить наилучшие результаты в скорости надо использовать RyuJit и нужно либо собирать под x64, либо отключить Prefer 32-bit и собирать под AnyCPU. Все бенчмарки я запускал на компьютере с процессором Intel Core i7-6700 CPU 3.40GHz (Skylake).


    Summieren Sie die Array-Elemente


    Ich habe mich dazu 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 finden. Schreiben wir vier Implementierungen dieser Aufgabe und fassen die Elemente des Array-Arrays zusammen:


    Am offensichtlichsten


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

    LINQ verwenden


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

    Verwenden von Vektoren aus System.Numerics:


    publicintVectors() {
        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:


    publicunsafeintIntrinsics() {
        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 = stackallocint[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 das folgende Ergebnis erhalten:


    MethodeAnzahl der ArtikelMedian
    Naiv1075,12 ns
    LINQ101 186,85 ns
    Vektoren1060,09 ns
    Intrinsics10255,40 ns
    Naiv100360,56 ns
    LINQ1002 719,24 ns
    Vektoren10060,09 ns
    Intrinsics100345,54 ns
    Naiv10001,847.88 ns
    LINQ100012 033,78 ns
    Vektoren1000240,38 ns
    Intrinsics1000630,98 ns
    Naiv10.00018 403,72 ns
    LINQ10.000102 489,96 ns
    Vektoren10.0007 316,42 ns
    Intrinsics10.0003 365,25 ns
    Naiv100.000176 630,67 ns
    LINQ100.000975 998,24 ns
    Vektoren100.00078 828,03 ns
    Intrinsics100.00041 269,41 ns

    Es ist ersichtlich, dass Lösungen mit Vectors und Intrinsics gegenüber der offensichtlichen Lösung und mit LINQ erheblich schneller sind. Jetzt müssen wir verstehen, was bei diesen beiden Methoden passiert.


    Betrachten wir die Vectors-Methode genauer:


    Vektoren
    publicintVectors() {
        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 den Vektor eingeben. Bei Verwendung der Hardwarebeschleunigung gibt dieser Wert an, wie viele 4-Byte-Nummern in einem SIMD-Register gespeichert werden können. Tatsächlich zeigt es, wie viele Elemente dieses Typs parallel ausgeführt werden können.
    • accVector - ein Vektor, in dem sich das Ergebnis der Funktion ansammelt;
      var v = neuer Vektor <int> (Array, i); - Die Daten werden aus dem Array beginnend mit Index i in den neuen Vektor v geladen. Es werden exakt vectorSize-Daten geladen.
    • accVector = Vector.Add (accVector, v); - Zwei Vektoren werden hinzugefügt.
      Zum Beispiel speichert Array 8 Zahlen: {0, 1, 2, 3, 4, 5, 6, 7} und vectorSize == 4, dann:
      In der ersten Iteration des Zyklus accVector = {0, 0, 0, 0}, v = {0, 1, 2, 3} lautet nach dem Hinzufügen 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 der 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, hierfür können Sie eine Skalarmultiplikation mit einem mit Einheiten gefüllten Vektor anwenden: 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.
    • Bei Bedarf werden am Ende die Zahlen addiert, die nicht in den letzten Vektor passen.

    Wenn Sie sich den Code für die Intrinsics-Methode ansehen:


    Intrinsics
    publicunsafeintIntrinsics() {
        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 = stackallocint[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 einigen Ausnahmen sehr ähnlich ist:


    • vectorSize ist eine Konstante. Dies liegt daran, dass Avx2-Befehle, die mit 256-Bit-Registern arbeiten, in dieser Methode explizit verwendet werden. In einer realen Anwendung muss überprüft werden, ob der aktuelle Avx2-Prozessor die Anweisungen unterstützt, und, falls nicht unterstützt, einen anderen Code aufrufen. Es sieht so aus:
      if (Avx2.IsSupported) {
      DoThingsForAvx2();
      }
      elseif (Avx.IsSupported) {
      DoThingsForAvx();
      }
      ...
      elseif (Sse2.IsSupported) {
      DoThingsForSse2();
      }
      ...
    • var accVector = Vector256 <int> .Zero; accVector wird als ein mit Nullen gefüllter 256-Bit-Vektor deklariert.
    • fixed (int * ptr = Array) - Der Zeiger auf das Array wird in ptr eingegeben.
    • Weitere Operationen sind die gleichen wie in Vektoren: Laden von Daten in einen Vektor und Hinzufügen von zwei Vektoren.
    • Zum Aufsummieren der Elemente des Vektors wurde die folgende Methode verwendet:
      • Auf dem Stapel wird ein Array erstellt: var temp = stackalloc int [vectorSize];
      • Der Vektor wird in dieses Array geladen: Avx2.Store (temp, accVector);
      • Die Schleife fasst die Elemente des Arrays zusammen.
    • dann werden die Array-Elemente erreicht, die nicht in den letzten Vektor passen.

    Vergleichen Sie zwei Arrays


    Es ist notwendig, zwei Bytearrays zu vergleichen. Eigentlich ist dies die Aufgabe, wegen der ich angefangen habe, SIMD in .NET zu studieren. Lassen Sie uns noch einmal mehrere Methoden für den Benchmark schreiben, wir werden zwei Arrays vergleichen: ArrayA und ArrayB:


    Die naheliegendste Lösung:


    publicboolNaive() {
        for (int i = 0; i < ArrayA.Length; i++) {
            if (ArrayA[i] != ArrayB[i]) returnfalse;
        }
        returntrue;
    }

    Lösung über LINQ:


    publicboolLINQ() => ArrayA.SequenceEqual(ArrayB);

    Lösung über MemCmp-Funktion:


    [DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl)]
    staticexternintmemcmp(byte[] b1, byte[] b2, long count);
    publicboolMemCmp() => memcmp(ArrayA, ArrayB, ArrayA.Length) == 0;

    Verwenden von Vektoren aus System.Numerics:


    publicboolVectors() {
        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)) {
                returnfalse;
            }
        }
        for (; i < ArrayA.Length; i++) {
            if (ArrayA[i] != ArrayB[i])
                returnfalse;
        }
        returntrue;
    }

    Verwenden von Intrinsics:


    publicunsafeboolIntrinsics() {
        int vectorSize = 256 / 8;
        int i = 0;
        constint 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) {
                    returnfalse;
                }
            }
            for (; i < ArrayA.Length; i++) {
                if (ArrayA[i] != ArrayB[i])
                    returnfalse;
            }
            returntrue;
        }
    }

    Das Ergebnis des Benchmarks auf meinem Computer:


    MethodeAnzahl der ArtikelMedian
    Naiv10.00066 719,1 ns
    LINQ10.00071 211,1 ns
    Vektoren10.0003,695,8 ns
    Memcmp10.000600,9 ns
    Intrinsics10.0001.607,5 ns
    Naiv100.000588 633,7 ns
    LINQ100.000651 191,3 ns
    Vektoren100.00034 659,1 ns
    Memcmp100.0005 513,6 ns
    Intrinsics100.00012.078,9 ns
    Naiv1.000.0005.637.293,1 ns
    LINQ1.000.0006.622.666,0 ns
    Vektoren1.000.000777 974,2 ns
    Memcmp1.000.000361 704,5 ns
    Intrinsics1.000.000434 252,7 ns

    Ich denke, der gesamte Code dieser Methoden ist verständlich, mit Ausnahme von zwei Zeilen in Intrinsics:


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

    In den ersten beiden werden Vektoren auf Gleichheit verglichen und das Ergebnis im areEqual-Vektor gespeichert, in dem die Bits im 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 sein müssen (11111111b). Weil Avx2.CompareEqual ist ein Wrapper für _mm256_cmpeq_epi8. Auf der Intel-Website können Sie den Pseudocode dieser Operation sehen:
    Die MoveMask-Methode aus dem Vektor erstellt eine 32-Bit-Zahl. Die Bitwerte sind die hohen Bits jedes der 32 Einzelbyteelemente des Vektors. Pseudocode kann hier eingesehen werden .


    Stimmen also einige Bytes in va und vb nicht überein, so sind die entsprechenden Bytes in areEqual gleich 0, daher sind auch die High-Bits dieser Bytes gleich 0. MovoveMask ist auch gleich 0 und der Vergleich mit equalsMask wird nicht funktionieren.


    Analysieren wir ein kleines Beispiel unter der Annahme, dass die Vektorlänge 8 Byte beträgt (so dass weniger geschrieben wurde):


    • Sei va = {100, 10, 20, 30, 100, 40, 50, 100} und vb = {100, 20, 10, 30, 100, 40, 80, 90};
    • Dann ist gleich gleich gleich {255, 0, 0, 255, 255, 255, 0, 0};
    • Die MoveMask-Methode gibt 10011100b zurück, die mit der Maske 11111111b verglichen werden muss, da Da diese Masken ungleich sind, stellt sich heraus, dass beide Vektoren va und vb ungleich sind.

    Zählen, wie oft ein Objekt in einer Sammlung gefunden wurde.


    Manchmal muss gezählt werden, wie oft ein bestimmtes Element in einer Sammlung gefunden wurde, z. B. ints. Dieser Algorithmus kann auch beschleunigt werden. Schreiben wir zum Vergleich mehrere Methoden, und suchen wir das Item-Element im Array-Array.


    Das offensichtlichste:


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

    mit LINQ:


    publicintLINQ() => Array.Count(i => i == Item);

    mit Vektoren von System.Numerics.Vectors:


    publicintVectors() {
        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:


    publicunsafeintIntrinsics() {
        int vectorSize = 256 / 8 / 4;
        //var mask = Avx2.SetAllVector256(Item);//var mask = Avx2.SetVector256(Item, Item, Item, Item, Item, Item, Item, Item);var temp = stackallocint[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;
    }

    Das Ergebnis des Benchmarks auf meinem Computer:


    MethodeAnzahl der ArtikelMedian
    Naiv10002 824,41 ns
    LINQ100012 138,95 ns
    Vektoren1000961,50 ns
    Intrinsics1000691.08 ns
    Naiv10.00027 072,25 ns
    LINQ10.000113 967,87 ns
    Vektoren10.0007 571,82 ns
    Intrinsics10.0004,296,71 ns
    Naiv100.000361 028,46 ns
    LINQ100.0001.091.994,28 ns
    Vektoren100.00082 839,29 ns
    Intrinsics100.00040 307,91 ns
    Naiv1.000.0001,634 175,46 ns
    LINQ1.000.0006 194 257,38 ns
    Vektoren1.000.000583 901,29 ns
    Intrinsics1.000.000413 520,38 ns

    Methoden Vektoren und Intrinsics stimmen in der Logik vollständig überein, die Unterschiede bestehen nur in der Implementierung spezifischer Operationen. Die ganze Idee ist:


    • erstellt eine Vektormaske, in der die gewünschte Nummer in jedem Element gespeichert ist;
    • Ein Teil des Arrays wird in den Vektor v geladen und mit der Maske verglichen, dann werden alle Bits in gleichen Elementen in gleichen Elementen gesetzt, da 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. In accVector wird dann die Summe der Häufigkeit angegeben, mit der das Element item in allen Vektoren v für jede Position angetroffen wird (Minus gibt Ihnen ein Plus für Minuten).

    Den gesamten Code aus dem Artikel finden Sie auf GitHub


    Fazit


    Ich habe nur einen kleinen Teil der Möglichkeiten betrachtet, die .NET für die Vektorisierung von Berechnungen bietet. Eine vollständige und aktuelle Liste der in .NETCORE unter x86 verfügbaren intrinsik finden Sie im Quellcode . Praktischerweise gibt es in C # -Dateien in der Zusammenfassung jedes intrinsischen Elements einen eigenen Namen aus der Welt von C, was sowohl das Verständnis des Zwecks dieses intrinsischen Elements als auch die Übersetzung bereits vorhandener C ++ / C-Algorithmen nach .NET vereinfacht. Die Dokumentation zu System.Numerics.Vector ist auf msdn verfügbar .


    .NET hat meiner Meinung nach einen großen Vorteil gegenüber C ++, da Die JIT-Kompilierung findet bereits auf dem Clientcomputer statt. Der Compiler kann den Code für einen bestimmten Clientprozessor optimieren und so die maximale Leistung erzielen. Gleichzeitig kann ein Programmierer zum Schreiben von schnellem Code im Rahmen einer Sprache und Technologie bleiben.


    Jetzt auch beliebt: