Uma pequena visão geral do SIMD no .NET / C #

Sua atenção é convidada a uma pequena visão geral dos recursos de vetorização de algoritmos no .NET Framework e no .NETCORE. O objetivo do artigo é apresentar essas técnicas para quem não as conhece e mostrar que o .NET não fica muito atrás dos idiomas "reais e compilados" para os nativos
desenvolvimento.

Estou apenas começando a aprender técnicas de vetorização. Portanto, se alguém da comunidade me indicar um cant explícito ou oferecer versões aprimoradas dos algoritmos descritos abaixo, ficarei muito feliz.

Um pouco de história

No .NET, o SIMD apareceu pela primeira vez em 2015 com o lançamento do .NET Framework 4.6. Em seguida, foram adicionados os tipos Matrix3x2, Matrix4x4, Plane, Quaternion, Vector2, Vector3 e Vector4, o que permitiu a construção de cálculos vetorizados. Posteriormente, foi adicionado o tipo Vector <T>, o que proporcionava mais oportunidades para algoritmos de vetorização. Mas muitos programadores ainda estavam infelizes porque os tipos acima limitavam o fluxo de pensamentos do programador e não permitiam o uso total das instruções SIMD dos processadores modernos. Atualmente, na visualização do .NET Core 3.0, o espaço para nome System.Runtime.Intrinsics apareceu, o que oferece muito mais liberdade na escolha das instruções. Para obter os melhores resultados em velocidade, você precisa usar o RyuJit e construir no x64 ou desabilitar o Prefer 32 bits e construir no AnyCPU. Todos os benchmarks que eu executei em um computador com um processador Intel Core i7-6700 de 3.40GHz (Skylake).

Resuma os elementos da matriz

Decidi começar com o problema clássico, que geralmente é escrito primeiro quando se trata de vetorização. Essa é a tarefa de encontrar a soma dos elementos da matriz. Escreveremos quatro implementações desta tarefa, resumiremos os elementos da matriz Array:

Mais óbvio

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 vetores do 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 o código do espaço 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; } 

Lancei uma referência nesses quatro métodos no meu computador e obtive este resultado:

Pode-se observar que as soluções com Vectors e Intrinsics são muito mais rápidas que a solução óbvia e com LINQ. Agora precisamos descobrir o que acontece nesses dois métodos.

Considere o método Vectors em mais detalhes:

 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 = Vetor <int> .Count; - é quantos números de 4 bytes podemos colocar em um vetor. Se a aceleração de hardware for usada, esse valor mostra quantos números de 4 bytes podem ser colocados em um registro SIMD. De fato, mostra quantos elementos desse tipo você pode realizar operações em paralelo;
• accVector - um vetor no qual o resultado da função se acumulará;
  var v = novo vetor <int> (matriz, i); - os dados são carregados em um novo vetor v, da matriz, iniciando no índice i. Os dados exatamente vectorSize serão carregados.
• accVector = Vector.Add (accVector, v); - dois vetores são adicionados.
  Por exemplo, 8 números são armazenados na matriz: {0, 1, 2, 3, 4, 5, 6, 7} e vectorSize == 4 e, em seguida:
  Na primeira iteração do loop accVector = {0, 0, 0, 0}, v = {0, 1, 2, 3}, após a adição no accVector será: {0, 0, 0, 0} + {0, 1, 2 , 3} = {0, 1, 2, 3}.
  Na segunda iteração, v = {4, 5, 6, 7} e após a adição accVector = {0, 1, 2, 3} + {4, 5, 6, 7} = {4, 6, 8, 10}.
• Resta apenas obter de algum modo a soma de todos os elementos do vetor; para isso, podemos aplicar a multiplicação escalar por um vetor preenchido com unidades: int result = Vector.Dot (accVector, Vector <int> .One);
  Acontece: {4, 6, 8, 10} {1, 1, 1, 1} = 4 1 + 6 1 + 8 1 + 10 * 1 = 28.
• No final, se necessário, são adicionados números que não se encaixam no último vetor.

Se você olhar para o código do método 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; } 

Você pode ver que é muito semelhante ao Vectors, com algumas exceções:

• vectorSize é dado por constante. Isso ocorre porque as instruções Avx2 que operam em registros de 256 bits são explicitamente usadas nesse método. Em um aplicativo real, deve-se verificar se o processador Avx2 atual suporta instruções e, se não, chamar outro código. Parece algo como isto:
  

   if (Avx2.IsSupported) { DoThingsForAvx2(); } else if (Avx.IsSupported) { DoThingsForAvx(); } ... else if (Sse2.IsSupported) { DoThingsForSse2(); } ... 

• var accVector = Vector256 <int> .Zero; accVector é declarado como um vetor de 256 bits preenchido com zeros.
• fixo (int * ptr = matriz) - um ponteiro para uma matriz é inserido em ptr.
• Em seguida, as mesmas operações que em Vetores: carregando dados em um vetor e adicionando dois vetores.
• Para resumir os elementos do vetor, foi aplicado o seguinte método:
  
  • uma matriz é criada na pilha: var temp = stackalloc int [vectorSize];
  • o vetor é carregado nessa matriz: Avx2.Store (temp, accVector);
  • em um loop, os elementos da matriz são somados.
• os elementos da matriz que não são colocados no último vetor são somados

Compare duas matrizes

É necessário comparar duas matrizes de bytes. Na verdade, esse é o problema pelo qual comecei a aprender o SIMD no .NET. Novamente, escreveremos vários métodos para o benchmark, compararemos duas matrizes: ArrayA e ArrayB:

A solução mais óbvia:

 public bool Naive() { for (int i = 0; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; } 

Solução via LINQ:

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

Solução via função 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 vetores do 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 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; } } 

O resultado da referência no meu computador:

Todo o código desses métodos, eu acho, é compreensível, com exceção de duas linhas no Intrinsics:

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

No primeiro, dois vetores são comparados quanto à igualdade e o resultado é armazenado no vetor areEqual, no qual todos os bits são definidos como 1 em um elemento em uma posição específica se os elementos correspondentes em va e vb forem iguais. Acontece que se os vetores dos bytes va e vb forem completamente iguais, em areEquals todos os elementos deverão ser 255 (11111111b). Porque O Avx2.CompareEqual é um invólucro sobre _mm256_cmpeq_epi8; no site da Intel, você pode ver o pseudo-código desta operação:
O método MoveMask de um vetor cria um número de 32 bits. Os valores de bits são os bits altos de cada um dos 32 elementos de byte único do vetor. O pseudocódigo pode ser encontrado aqui .

Portanto, se alguns bytes em va e vb não coincidirem, em areEqual os bytes correspondentes serão 0, portanto os bits mais significativos desses bytes também serão 0, o que significa que os bits correspondentes na resposta Avx2.MoveMask também serão 0 e a comparação com equalsMask não funcionará.

Vamos analisar um pequeno exemplo, assumindo que o comprimento do vetor seja 8 bytes (para escrever era menor):

• Seja va = {100, 10, 20, 30, 100, 40, 50, 100} e vb = {100, 20, 10, 30, 100, 40, 80, 90};
• Então areEqual será igual a {255, 0, 0, 255, 255, 255, 0, 0};
• O método MoveMask retornará 10011100b, que precisará ser comparado com a máscara 11111111b, porque Como essas máscaras são desiguais, os vetores va e vb não são iguais.

Contar quantas vezes um elemento ocorre na coleção

Às vezes é necessário calcular quantas vezes um elemento específico é encontrado em uma coleção, por exemplo, ints, esse algoritmo também pode ser acelerado. Vamos escrever alguns métodos para comparação, procuraremos o elemento Item na matriz Array.

O mais óbvio:

 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 vetores 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 Intrinsics:

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

O resultado da referência no meu computador:

Os métodos Vectors e Intrinsics são completamente idênticos na lógica, as diferenças estão apenas na implementação de operações específicas. A ideia como um todo é:

• um vetor de máscara é criado no qual o número necessário é armazenado em cada elemento;
• A parte da matriz é carregada no vetor ve comparada com a máscara; todos os bits serão definidos em elementos iguais em areEqual, porque areEqual é um vetor de ints; se você definir todos os bits de um elemento, obteremos -1 nesse elemento ((int) (1111_1111_1111_1111_1111_1111_1111_1111b) == -1);
• o vetor areEqual é subtraído de accVector e, em seguida, o accVector será a soma de quantas vezes o elemento do item ocorreu em todos os v vetores de cada posição (menos min dá um sinal de mais).

Todo o código do artigo pode ser encontrado no GitHub

Conclusão

Examinei apenas uma parte muito pequena das possibilidades que o .NET oferece para a vetorização de cálculos. Para obter uma lista completa e atualizada de intrínsecas disponíveis no .NETCORE em x86, você pode consultar o código-fonte . É conveniente que nos arquivos C # no resumo de cada intrínseca exista seu próprio nome no mundo C, o que simplifica o entendimento do objetivo desse intrínseco e a tradução dos algoritmos C ++ / C existentes para o .NET. A documentação do System.Numerics.Vector está disponível em msdn .

Na minha opinião, o .NET tem uma grande vantagem sobre o C ++, porque A compilação JIT já ocorre na máquina do cliente, o compilador pode otimizar o código para um processador de cliente específico, fornecendo desempenho máximo. Ao mesmo tempo, um programador para escrever código rápido pode permanecer na estrutura de um idioma e tecnologia.

UPD (15/09/2019):