Su atención es invitada a una pequeña descripción de las capacidades de vectorización de algoritmos en .NET Framework y .NETCORE. El propósito del artículo es presentar estas técnicas a aquellos que no las conocían en absoluto y mostrar que .NET no va muy por detrás de los lenguajes "reales, compilados" para los nativos.
desarrollo
Estoy empezando a aprender técnicas de vectorización, por lo que si alguien de la comunidad me señala un canto explícito o sugiere versiones mejoradas de los algoritmos que se describen a continuación, estaré muy feliz.
Un poco de historia
En .NET, SIMD apareció por primera vez en 2015 con el lanzamiento de .NET Framework 4.6. Luego se agregaron los tipos Matrix3x2, Matrix4x4, Plane, Quaternion, Vector2, Vector3 y Vector4, lo que permitió la construcción de cálculos vectorizados. Más tarde, se agregó el tipo Vector <T>, que proporcionó más oportunidades para vectorizar algoritmos. Pero muchos programadores todavía estaban descontentos porque los tipos anteriores limitaron el flujo de pensamientos del programador y no permitieron el uso completo de las instrucciones SIMD de los procesadores modernos. Ya en nuestro tiempo, en .NET Core 3.0 Preview, ha aparecido el espacio de nombres System.Runtime.Intrinsics, que proporciona mucha más libertad para elegir instrucciones. Para obtener los mejores resultados en velocidad, debe usar RyuJit y construir en x64 o desactivar Prefer 32-bit y construir en AnyCPU. Todos los puntos de referencia que ejecuté en una computadora con un procesador Intel Core i7-6700 3.40GHz (Skylake).
Resumir los elementos de la matriz.
Decidí comenzar con el problema clásico, que a menudo se escribe primero cuando se trata de vectorización. Esta es la tarea de encontrar la suma de los elementos de la matriz. Escribiremos cuatro implementaciones de esta tarea, resumiremos los elementos de la matriz Array:
Más obvio
public int Naive() { int result = 0; foreach (int i in Array) { result += i; } return result; }
Usando LINQ
public long LINQ() => Array.Aggregate<int, long>(0, (current, i) => current + i);
Usando vectores de 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; }
Usando código del espacio System.Runtime.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; }
Lancé un punto de referencia sobre estos 4 métodos en mi computadora y obtuve este resultado:
Se puede ver que las soluciones con vectores e intrínsecos son mucho más rápidas que la solución obvia y con LINQ. Ahora tenemos que descubrir qué sucede en estos dos métodos.
Considere el método de Vectores con más detalle:
Vectores 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; - esta es la cantidad de números de 4 bytes que podemos poner en un vector. Si se usa la aceleración de hardware, este valor muestra cuántos números de 4 bytes se pueden colocar en un registro SIMD. De hecho, muestra cuántos elementos de este tipo puede realizar operaciones en paralelo;
- accVector: un vector en el que se acumulará el resultado de la función;
var v = nuevo Vector <int> (matriz, i); - los datos se cargan en un nuevo vector v, desde la matriz, comenzando desde el índice i. Se cargarán exactamente los datos de vectorSize. - accVector = Vector.Add (accVector, v); - Se añaden dos vectores.
Por ejemplo, en la matriz se almacenan 8 números: {0, 1, 2, 3, 4, 5, 6, 7} y vectorSize == 4, luego:
En la primera iteración del bucle accVector = {0, 0, 0, 0}, v = {0, 1, 2, 3}, después de la adición en accVector será: {0, 0, 0, 0} + {0, 1, 2 , 3} = {0, 1, 2, 3}.
En la segunda iteración, v = {4, 5, 6, 7} y después de la suma accVector = {0, 1, 2, 3} + {4, 5, 6, 7} = {4, 6, 8, 10}. - Solo queda obtener de alguna manera la suma de todos los elementos del vector, para esto podemos aplicar la multiplicación escalar por un vector lleno de unidades: int result = Vector.Dot (accVector, Vector <int> .One);
Entonces resulta: {4, 6, 8, 10} {1, 1, 1, 1} = 4 1 + 6 1 + 8 1 + 10 * 1 = 28. - Al final, si es necesario, se suman los números que no caben en el último vector.
Si nos fijamos en el código del método intrínseco:
Intrínseca 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; }
Puede ver que es muy similar a Vectores con algunas excepciones:
Compara dos matrices
Es necesario comparar dos matrices de bytes. En realidad, este es el problema por el cual comencé a aprender SIMD en .NET. Nuevamente, escribiremos varios métodos para el punto de referencia, compararemos dos matrices: ArrayA y ArrayB:
La solución más obvia:
public bool Naive() { for (int i = 0; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; }
Solución a través de LINQ:
public bool LINQ() => ArrayA.SequenceEqual(ArrayB);
Solución a través de la función MemCmp:
[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;
Usando vectores de 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; }
Usando intrínsecos:
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; } }
El resultado del benchmark en mi computadora:
Creo que todo el código para estos métodos es comprensible, con la excepción de dos líneas en intrínsecos:
var areEqual = Avx2.CompareEqual(va, vb); if (Avx2.MoveMask(areEqual) != equalsMask) { return false; }
En el primero, se comparan dos vectores para igualdad y el resultado se almacena en el vector areEqual, en el que todos los bits se establecen en 1 en un elemento en una posición específica si los elementos correspondientes en va y vb son iguales. Resulta que si los vectores de los bytes va y vb son completamente iguales, entonces en areEquals todos los elementos deberían ser iguales a 255 (11111111b). Porque Avx2.CompareEqual es un contenedor sobre _mm256_cmpeq_epi8, luego en el sitio de Intel puede ver el pseudocódigo de esta operación:
El método MoveMask de un vector crea un número de 32 bits. Los valores de bits son los bits altos de cada uno de los 32 elementos de un solo byte del vector. El pseudocódigo se puede encontrar aquí .
Por lo tanto, si algunos bytes en va y vb no coinciden, en areEqual los bytes correspondientes serán 0, por lo tanto, los bits más significativos de estos bytes también serán 0, lo que significa que los bits correspondientes en la respuesta Avx2.MoveMask también serán 0 y la comparación con equalsMask no funcionará.
Analicemos un pequeño ejemplo, suponiendo que la longitud del vector es de 8 bytes (para escribirlo fue menor):
- Sea va = {100, 10, 20, 30, 100, 40, 50, 100}, y vb = {100, 20, 10, 30, 100, 40, 80, 90};
- Entonces areEqual será igual a {255, 0, 0, 255, 255, 255, 0, 0};
- El método MoveMask devolverá 10011100b, que deberá compararse con la máscara 11111111b, porque Como estas máscaras son desiguales, resulta que los vectores va y vb no son iguales.
Cuente cuántas veces ocurre un elemento en la colección
A veces es necesario calcular cuántas veces se encuentra un elemento en particular en una colección, por ejemplo, ints, este algoritmo también se puede acelerar. Escribamos algunos métodos para comparar, buscaremos el elemento Item en la matriz de Array.
Lo más obvio:
public int Naive() { int result = 0; foreach (int i in Array) { if (i == Item) { result++; } } return result; }
usando LINQ:
public int LINQ() => Array.Count(i => i == Item);
utilizando vectores de 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; }
Usando intrínsecos:
public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4;
El resultado del benchmark en mi computadora:
Los métodos de Vectores e Intrínsecos son completamente idénticos en lógica, las diferencias están solo en la implementación de operaciones específicas. La idea en su conjunto es:
- se crea un vector de máscara en el que se almacena el número requerido en cada elemento;
- La parte de la matriz se carga en el vector v y se compara con la máscara, luego todos los bits se establecerán en elementos iguales en areEqual, porque areEqual es un vector de ints, entonces si configura todos los bits de un elemento, obtenemos -1 en este elemento ((int) (1111_1111_1111_1111_1111_1111_1111_1111b) == -1);
- el vector areEqual se resta de accVector y luego accVector será la suma de cuántas veces se produjo el elemento elemento en todos los vectores v para cada posición (menos min da un plus).
Todo el código del artículo se puede encontrar en GitHub
Conclusión
Examiné solo una parte muy pequeña de las posibilidades que ofrece .NET para los cálculos de vectorización. Para obtener una lista completa y actualizada de intrínsecos disponibles en .NETCORE bajo x86, puede consultar el código fuente . Es conveniente que en los archivos C # en el resumen de cada intrínseco haya su propio nombre del mundo de C, lo que simplifica la comprensión del propósito de este intrínseco y la traducción de los algoritmos C ++ / C existentes a .NET. La documentación de System.Numerics.Vector está disponible en msdn .
En mi opinión, .NET tiene una gran ventaja sobre C ++, porque La compilación JIT ya tiene lugar en la máquina del cliente, el compilador puede optimizar el código para un procesador de cliente específico, proporcionando el máximo rendimiento. Al mismo tiempo, un programador para escribir código rápido puede permanecer dentro del marco de un lenguaje y tecnología.
UPD (15/09/2019):
Había una jamba en los puntos de referenciaEn los puntos de referencia, usé IterationSetup, que, como resultó, puede afectar en gran medida el rendimiento de los puntos de referencia que funcionan en menos de 100 ms. Si lo rehace en GlobalSetup, los resultados serán así.
Suma de elementos de matriz:
Comparando dos matrices:
El número de ocurrencias de un elemento en una matriz: