Aquí hay un vistazo rápido a las capacidades de vectorización de algoritmos en .NET Framework y .NET Core. Este artículo es para aquellos que no saben nada sobre estas técnicas. También mostraré que .NET no se queda atrás de los lenguajes "compilados reales" para el desarrollo nativo.
Estoy empezando a aprender técnicas de vectorización. Por lo tanto, agradeceré si los miembros de la comunidad encuentran errores claros o sugieren mejoras en los algoritmos descritos.
Algo de historia
SIMD apareció en .NET Framework 4.6 en 2015. Fue entonces cuando se agregaron los tipos Matrix3x2, Matrix4x4, Plane, Quaternion, Vector2, Vector3 y Vector4. Permitieron cálculos vectorizados. El siguiente fue el tipo Vector <T> que dio más oportunidades para vectorizar algoritmos. Sin embargo, muchos programadores todavía estaban insatisfechos ya que estos tipos restringían los flujos de ideas de los codificadores y no permitían usar toda la capacidad de las instrucciones SIMD en los procesadores modernos. Ahora en .NET Core 3.0 Preview, tenemos el espacio de nombres System.Runtime.Intrinsics que da mucha libertad en la elección de instrucciones. Para obtener la máxima velocidad, debe usar RyuJit y recurrir al ensamblaje x64 o desactivar Prefer 32-bit y elegir el ensamblaje AnyCPU. Ejecuté todos los puntos de referencia en la computadora con CPU Intel Core i7-6700 3.40 GHz (Skylake).
Suma de elementos de matriz
Decidí comenzar con una tarea clásica que generalmente viene primero si hay una vectorización involucrada. Se trata de encontrar la suma de los elementos de la matriz. Escribamos cuatro implementaciones de esta tarea para sumar los elementos de Array.
La implementación más obvia:
public int Naive() { int result = 0; foreach (int i in Array) { result += i; } return result; }
Implementación basada en LINQ:
public long LINQ() => Array.Aggregate<int, long>(0, (current, i) => current + i);
La implementación basada en 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; }
La implementación basada en el código del espacio de nombres 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; }
Comparé esos 4 métodos en mi computadora y obtuve los siguientes resultados:
Está claro que las soluciones con vectores e intrínsecos son mucho más rápidas que las soluciones obvias y basadas en LINQ. Ahora tenemos que descubrir qué sucede en estos dos métodos.
Consideremos el método de vectores más de cerca:
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; - la cantidad de números de 4 bytes que podemos colocar en un vector. Si se usa la aceleración de hardware, este valor muestra cuántos números de 4 bytes podemos poner en un registro SIMD. De hecho, muestra cuántos elementos de este tipo se pueden manejar simultáneamente;
- accVector es un vector que acumula el resultado de la función;
- var v = nuevo Vector <int> (matriz, i); - los datos de la matriz se cargan en un nuevo vector v, comenzando desde el índice i. El vectorSize de datos se cargará exactamente;
- accVector = Vector.Add (accVector, v); - se suman dos vectores.
Por ejemplo, hay 8 números en la matriz: {0, 1, 2, 3, 4, 5, 6, 7} y vectorSize == 4.
Luego, durante la iteración del primer ciclo accVector = {0, 0, 0, 0}, v = {0, 1, 2, 3} y después de la adición accVector mantendrá: {0, 0, 0, 0} + {0, 1 , 2, 3} = {0, 1, 2, 3}.
Durante la segunda iteración v = {4, 5, 6, 7} y después de la adición accVector = {0, 1, 2, 3} + {4, 5, 6, 7} = {4, 6, 8, 10}. - Ahora solo necesitamos obtener la suma de todos los elementos vectoriales. Para hacer esto, podemos usar la multiplicación escalar por un vector lleno de unos: int result = Vector.Dot (accVector, Vector <int> .One);
Luego obtenemos: {4, 6, 8, 10} * {1, 1, 1, 1} = 4 * 1 + 6 * 1 + 8 * 1 + 10 * 1 = 28. - Si es necesario, los números que no se ajustan al último vector se sumarán al final.
Veamos el código 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; }
Podemos ver que es como Vectores con una excepción:
Comparar dos matrices
Necesitamos comparar dos matrices de bytes. Es exactamente esta tarea la que me hizo estudiar SIMD en .NET. Nuevamente, escribamos varios métodos para la evaluación comparativa y comparemos 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 basada en LINQ:
public bool LINQ() => ArrayA.SequenceEqual(ArrayB);
La solución basada en 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;
La solución basada en 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; }
Solución basada en intrínseca:
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; } }
Los resultados de ejecutar el benchmark en mi computadora:
Supongo que el código de estos métodos es claro, excepto por dos líneas en Intrinsics:
var areEqual = Avx2.CompareEqual(va, vb); if (Avx2.MoveMask(areEqual) != equalsMask) { return false; }
En la primera línea, se comparan dos vectores para la igualdad y el resultado se guarda en un vector areEqual en el que todos los bits del elemento en una posición particular se establecen en 1 si los elementos correspondientes en va y vb son iguales. Entonces, resulta que si los vectores de bytes va y vb son iguales, todos los elementos en areEquals deberían ser iguales a 255 (11111111b). Como Avx2.CompareEqual es un contenedor sobre _mm256_cmpeq_epi8, podemos ir al sitio web de Intel y ver el pseudocódigo de esta operación:
El método MoveMask crea un número de 32 bits a partir de un vector. Los bits superiores de cada 32 elementos de un byte en un vector son los valores de bits en el resultado de MoveMask. El pseudocódigo está disponible aquí .
Por lo tanto, si algunos bytes en va y vb no coinciden, los bytes correspondientes en areEqual serán 0. Por lo tanto, los bits superiores de estos bytes también serán 0. Esto significa que los bits correspondientes en la respuesta Avx2.MoveMask también serán 0 y areEqual no será igual a equalsMask.
Veamos un ejemplo suponiendo que la longitud del vector es de 8 bytes (para escribir menos):
- Deje va = {100, 10, 20, 30, 100, 40, 50, 100} y vb = {100, 20, 10, 30, 100, 40, 80, 90}.
- Entonces areEquals será {255, 0, 0, 255, 255, 255, 0, 0}.
- El método MoveMask devolverá 10011100b que se debe comparar con la máscara 11111111b. Como estas máscaras no son iguales, los vectores va y vb tampoco lo son.
Contando las veces que ocurre un elemento en una colección.
Algunas veces necesita contar las ocurrencias de un elemento en particular, por ejemplo, enteros, en una colección. También podemos acelerar este algoritmo. Para comparar, escribamos varios métodos para buscar el elemento Item en Array.
El 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);
Usando 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; 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; }
Los resultados de ejecutar el benchmark en mi computadora:
Los vectores y los métodos intrínsecos coinciden completamente en lógica pero difieren en la implementación de operaciones particulares. La idea es la siguiente:
- crear un vector de máscara en el que se almacena un número requerido en cada elemento;
- cargar la parte de una matriz en v vector y comparar esta parte con una máscara. Como resultado, todos los bits se establecerán en elementos iguales de areEqual. Como areEqual es una matriz de enteros, si establecemos todos los bits de un elemento, obtendremos -1 en este elemento ((int) (1111_1111_1111_1111_1111_1111_1111_1111b) == -1);
- reste el vector areEqual del accVector. Luego, accVector mantendrá el recuento de cuántas veces se produjo el elemento elemento en todos los vectores v para cada posición (menos por menos es un más).
Todo el código del artículo está en GitHub .
Conclusión
Describí solo una pequeña parte de las capacidades de .NET para la vectorización de cómputo. Para ver la lista actualizada completa de todos los intrínsecos disponibles en .NET Core en x86, consulte el código fuente . Es conveniente que el resumen de cada intrínseco en archivos C # contenga su nombre en C world. Esto ayuda a comprender el propósito de este intrínseco y la transferencia de algoritmos C ++ / C existentes a .NET. La documentación de System.Numerics.Vector está disponible en msdn .
Creo que .NET tiene una gran ventaja sobre C ++. Como la compilación JIT ya se produce en una máquina cliente, un compilador puede optimizar el código para un procesador de cliente en particular, dando el máximo rendimiento. Al mismo tiempo, un programador puede permanecer dentro de un idioma y las mismas tecnologías para escribir código rápido.