Algoritmos SIMD projetados do zero

Projeto de algoritmos SIMD

• Explicação sobre otimização com SIMD: SIMD significa instrução única, múltiplos dados, e é necessário pensar como um projetista de circuitos.
• SIMD é frequentemente mencionado em desempenho e HPC (computação de alto desempenho), mas não é um tema familiar para iniciantes.
• Na maioria das linguagens de programação, as APIs de programação SIMD são difíceis de usar.
• Algoritmos SIMD são difíceis de entender com uma mentalidade de programação procedural, e a programação funcional ajuda.
• O texto trata do vb64, que implementa um codec base64 usando a biblioteca std::simd do Rust.

Limites físicos

• Computadores existem no mundo real e são restringidos pelas leis da física.
• Na era inicial da computação, era possível melhorar o desempenho comprando um computador novo.
• O efeito do escalonamento de Dennard entrou em colapso, então transistores menores passaram a significar maior consumo de energia.
• Aumentar o número de núcleos tornou-se a nova tendência. É possível melhorar o desempenho da CPU com multithreading, mas isso gera sobrecarga de sincronização.

A lentidão do código procedural

• Núcleos de computadores modernos não executam código linha por linha.
• Por meio do paralelismo em nível de instrução, várias operações podem ser realizadas ao mesmo tempo quando não há dependência de dados.
• O paralelismo aumenta quando o compilador consegue resolver riscos de dados.
• Desvios e operações de memória causam stalls, o que torna o código mais lento.

SIMD e lanes

• SIMD e vetores são frequentemente usados como sinônimos.
• Instruções SIMD usam como unidade básica vetores, que são arrays de tamanho fixo de números.
• Cada elemento do vetor é chamado de lane, e vetores SIMD geralmente têm tamanho pequeno.

Operações sobre vetores reais

• Vetores SIMD oferecem operações mais complexas do que registradores comuns.
• Registradores vetoriais suportam várias operações, como operações de bits, aritmética por lane, comparação por lane e shuffle.
• O shuffle é importante na programação SIMD para mover os dados para as posições adequadas.

Intrínsecos e seleção de instruções

• Ao escrever código SIMD, as operações disponíveis variam conforme a arquitetura.
• O compilador resolve o problema de seleção de instruções, decidindo quais instruções usar para as operações solicitadas pelo programador.
• Escrever código SIMD portátil é complexo, mas, com detecção de recursos em tempo de execução, é possível gerar o código ideal para diferentes processadores.

Parsing com SIMD

• É possível fazer parsing de texto com SIMD, e isso pode ser muito rápido.
• A implementação da decodificação de base64 com SIMD pode ser usada como exemplo.
• Remover todos os desvios é a chave no processo de criar uma versão SIMD.

Opinião do GN⁺

O ponto mais importante deste texto é que a programação SIMD, diferentemente da programação procedural tradicional, pode melhorar o desempenho ao processar dados em paralelo. SIMD é muito importante na área de computação de alto desempenho e, especialmente em linguagens modernas como Rust, entender como usar SIMD de forma eficaz pode ser um tema muito interessante para engenheiros de software. Isso porque, com SIMD, é possível aprender a otimizar algoritmos complexos e a superar os limites do hardware real.

[GN⁺]

Comentários do Hacker News

• Ótimo artigo para ver casos de uso de SIMD portável. Ao reproduzir os benchmarks em um sistema Zen 3, confirmei o mesmo ganho de velocidade. Em um M1 mbp, o ganho de desempenho aumenta gradualmente até chegar a 2x com comprimento de entrada de 110 bytes. O ganho é menor do que em x86_64, mas dá para dizer que o objetivo foi alcançado. No entanto, também ficou claro que Rust é um tanto incômodo para trabalhos com SIMD e ponteiros, além de engenharia de desempenho em geral.
• Às vezes, é surpreendente que, mesmo tentando programar da melhor forma possível em C++, a versão usando SIMD mostre desempenho mais de 10 vezes mais rápido. A portabilidade do código piora, mas seria ótimo se o compilador fizesse uma autovetorização melhor. Seria bom que a linguagem adicionasse suporte, via anotações, para permitir reordenar a sequência de certas operações.
• Aponta que o compilador não conseguiu otimizar uma determinada implementação de popcount para uma única instrução, mas que isso é possível em outros casos.
• _mm256_cvtps_epu32 não é uma instrução de AVX2, e sim de AVX-512; em AVX1, os inteiros existem em forma com sinal e a instrução correspondente é _mm256_cvtps_epi32.
• Gostei muito do pequeno minimapa à direita.
• Avalia que o ISPC é melhor do que adicionar SIMD a C++ ou Rust. Além disso, ele oferece suporte a despacho dinâmico, algo complicado de implementar manualmente.
• Levanta a pergunta de como isso se compara ao fastbase64 e diz que gostaria de compartilhar a atitude otimista do autor em relação às bibliotecas SIMD portáveis.
• Um excelente texto, que deixa a impressão de que eu jamais conseguiria ficar tão inteligente assim.
• Embora tenha sido mencionado que o primeiro exemplo da implementação de popcnt não vetorizada gera um "código francamente ridículo", ao compilar em modo release para a CPU nativa, a função aparentemente é vetorizada de forma bastante razoável.
• Considera que é uma tentativa bastante boa com Rust Simd. Também pergunta qual foi a peculiaridade mais surpreendente ao inspecionar o código gerado.