Por que todo desenvolvedor deveria conhecer SIMD

 (mitchellh.com)
1 pontos por GN⁺ 2 시간 전 | 1 comentários | Compartilhar no WhatsApp
  • SIMD não é uma técnica complexa reservada apenas a software de desempenho máximo, mas um meio cotidiano de otimização que acelera laços comuns ao processar dados sequenciais em vários valores por vez
  • Um código SIMD típico segue uma estrutura de 5 etapas: broadcast de constantes, iteração por unidade vetorial, operação em paralelo, redução/armazenamento do resultado e tratamento da cauda escalar
  • O loop de busca de codepoints do Ghostty compara 4, 8 ou 16 u32 de uma vez e, em teoria, pode aumentar a taxa de processamento em até 4x no ARM NEON, 8x no AVX2 e 16x no AVX-512
  • Em um desktop Intel com AVX2, a vazão total do terminal ficou cerca de 5x mais rápida, e quando não há largura vetorial compatível ou sobra entrada, o loop escalar existente processa toda a entrada ou o restante
  • A vetorização automática do compilador pode perder oportunidades mesmo em laços simples, então vale verificar primeiro a saída otimizada, mas loops quentes importantes podem manter comportamento e desempenho previsíveis com SIMD explícito

O que o SIMD faz

  • SIMD permite que a CPU processe vários valores em paralelo com uma única instrução
    • Em vez de comparar bytes um a um, é possível comparar 4, 8 ou mais de uma vez
    • Há oportunidade de transformar laços como for (byte in bytes), for (character in string), for (value in array) em processamento por largura vetorial
  • Se os dados tiverem centenas, milhares ou milhões de bytes, é possível obter aceleração local de 4x, 8x ou mais, dependendo da largura paralela
  • Se os dados tiverem apenas alguns ou algumas dezenas de valores, não vale a pena aplicar SIMD
  • simdutf e simdjson usam técnicas SIMD complexas, mas o SIMD do dia a dia não precisa ser tão complexo assim
  • Os exemplos usam Zig, mas a estrutura de 5 etapas também se aplica a outras linguagens, e cada linguagem difere na forma de suportar instruções SIMD

A estrutura recorrente de 5 etapas

  1. Fazer broadcast das constantes necessárias para todas as lanes e, se preciso, inicializar acumuladores vetoriais
  2. Percorrer a entrada em blocos do tamanho da largura vetorial por vez
  3. Executar comparações ou operações aritméticas em paralelo em todas as lanes
  4. Reduzir ou armazenar o resultado vetorial de acordo com o algoritmo
  5. Tratar o restante que não cabe em um vetor completo com o scalar tail existente
  • Ao se acostumar com essa estrutura, fica possível decompor um laço comum nas mesmas 5 etapas, tornando escrever SIMD tão simples quanto escrever um loop escalar
  • Se algo não puder ser expresso facilmente nessa estrutura, o mais apropriado é pular o uso de SIMD por enquanto

O loop de busca real do Ghostty

  • O Ghostty consome dados de um array de codepoints decodificados até encontrar um valor menor ou igual a 0xF
    • A maior parte dos dados de terminal são caracteres comuns a serem exibidos, então eles são processados em lote
    • O loop encontra o fim do próximo trecho imprimível o mais rápido possível
  • A implementação escalar original verifica os codepoints um por um
while (end < cps.len and cps[end] > 0xF) end += 1;
  • A implementação vetorial usa vetores genéricos sem funções intrínsecas específicas de CPU, e adiciona 12 linhas de código em relação à implementação escalar
  • O ganho esperado de vazão corresponde ao número de lanes do vetor
    • ARM NEON e Apple Silicon: até 4x
    • AVX2, suportado pela maioria das CPUs x86 modernas: até 8x
    • AVX-512, suportado por algumas CPUs Intel e AMD Zen 4 ou superiores: até 16x
  • Em um desktop Intel com AVX2, a vazão total medida desde a entrada do programa de terminal até o estado final do terminal ficou cerca de 5x mais rápida
    • Não é possível obter toda a aceleração teórica por causa do trabalho ao redor do SIMD
  • Caracteres de controle C0 também existem após 0xF, mas 0xF é o critério usado neste caminho de código do Ghostty
    • ESC e outras sequências de controle são tratadas em outro caminho

Etapa 1: broadcast de constantes

if (simd.lanes(u32)) |lanes| {
    const V = @Vector(lanes, u32);
    const threshold: V = @splat(0xF);
  • simd.lanes(u32) no Ghostty retorna quantos u32 a CPU de destino consegue processar ao mesmo tempo
    • Cada valor é chamado de lane
    • ARM retorna 4, AVX2 retorna 8 e AVX-512 retorna 16
    • Se não houver um tamanho vetorial utilizável, retorna null e o código SIMD é ignorado
  • @Vector(lanes, u32) cria um tipo vetorial com aquela quantidade de lanes
    • Se lanes for 8, um V contém 8 u32 que podem ser processados em paralelo
  • Comparações vetoriais exigem vetores dos dois lados, então @splat(0xF) replica 0xF em todas as lanes
{ 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF }
  • Este algoritmo não precisa de acumulador vetorial, mas outros algoritmos podem inicializá-lo nesta etapa

Etapa 2: iterar um vetor por vez

while (end + lanes <= cps.len) : (end += lanes) {
    const values: V = cps[end..][0..lanes].*;
  • Se lanes for 8, o loop só entra quando restam pelo menos 8 valores, e carrega 8 valores em values
  • Ao fim de cada iteração, end é incrementado não em 1, mas no número de lanes
  • É preciso conseguir carregar um vetor completo; portanto, se restarem apenas 5 valores, um vetor de 8 lanes não é lido
  • Valores que não cabem no vetor são tratados pela cauda escalar da etapa 5

Etapa 3: comparação paralela em todas as lanes

const greater_than_threshold = values > threshold;
  • Como values e threshold são vetores, > compara cada lane correspondente em uma única operação vetorial
  • Em 8 lanes, isso executa em paralelo 8 comparações equivalentes a cps[end] > 0xF
values:                 { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
threshold:              {  0xF,  0xF,  0xF,  0xF,  0xF,  0xF,  0xF,  0xF }
greater_than_threshold: { true, true, true, false, true, true, true, true }
  • Não há loop interno explícito, e o resultado é um vetor com booleanos por lane
  • A mesma estrutura pode ser aplicada não só a comparações, mas também a soma, multiplicação, mínimo, máximo e outras operações suportadas pelo tipo vetorial
  • A comparação em si é uma única operação vetorial, mas carregar o vetor, reduzir o resultado e localizar a lane que falhou exigem instruções adicionais

Etapa 4: redução do resultado vetorial

if (@reduce(.And, greater_than_threshold)) continue;
  • @reduce(.And, ...) combina todos os booleanos com and e produz um único booleano
  • Se todas as lanes forem true, passa para o próximo vetor; se ao menos uma for false, encontra a posição exata da falha
const mask: std.meta.Int(.unsigned, lanes) = @bitCast(greater_than_threshold);
end += @ctz(~mask);
break;
  • @bitCast converte o vetor booleano em uma máscara inteira com 1 bit por lane
    • 1 significa que o valor é maior que 0xF
    • 0 significa que a comparação falhou
  • Ao inverter a máscara, as comparações que falharam viram 1, e @ctz conta quantos bits 0 existem antes do primeiro 1
values:                 { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
greater_than_threshold: { true, true, true, false, true, true, true, true }
mask:                   {    1,    1,    1,     0,    1,    1,    1,    1 }
~mask:                  {    0,    0,    0,     1,    0,    0,    0,    0 }
  • Neste exemplo, @ctz(~mask) retorna 3, movendo end para a lane 3, onde está o primeiro caractere de controle 0x0A
  • A redução do resultado é a parte que mais varia entre as 5 etapas, dependendo do algoritmo
    • Uma soma pode reduzir o acumulador vetorial a um único número
    • Uma transformação pode armazenar o vetor inteiro no buffer de saída
    • Esta busca gera uma máscara de bits para localizar a posição de uma lane específica

Etapa 5: tratamento da cauda escalar

while (end < cps.len and cps[end] > 0xF) end += 1;
  • Se o comprimento da entrada não for múltiplo exato da largura vetorial, o loop escalar original trata o restante
  • Depois de um loop vetorial de 8 lanes, podem sobrar de 0 a 7 valores
  • Em CPUs onde simd.lanes(u32) retorna null, a parte SIMD é ignorada e o loop escalar trata toda a entrada
  • A implementação original cuida ao mesmo tempo do tratamento do restante e do fallback de compatibilidade
  • Vetores genéricos removem a sintaxe específica de cada CPU, mas não eliminam a geração de código específica por CPU
    • O Zig converte operações vetoriais para o conjunto de instruções ativado no alvo

O que a vetorização automática deixa passar

  • Compiladores podem fazer vetorização automática em código simples, como laços aritméticos regulares sem fluxo de controle complexo
  • Antes de escrever SIMD manualmente, vale compilar a versão escalar com opções de otimização e verificar o código gerado
  • Compiladores de produção frequentemente perdem oportunidades de vetorização, e embora a vetorização automática seja pesquisada há décadas, estudos recentes ainda partem desse problema
  • Se o laço for importante o bastante para que um ganho de 5x faça diferença, pode valer a pena escrever a vetorização de forma explícita para manter o comportamento previsível
    • Isso evita situações em que mudanças irrelevantes no código ou atualizações do compilador façam um loop vetorial voltar silenciosamente a ser escalar

Até onde desenvolvedores precisam dominar SIMD

  • Ao encontrar hot loops que buscam, comparam, contam ou transformam grandes volumes de dados sequenciais, é preciso ao menos considerar processamento por largura vetorial
  • O SIMD do dia a dia segue uma forma regular: preparação de constantes, carregamento vetorial, operação paralela, redução do resultado e cauda escalar
  • Se a linguagem oferecer bom suporte a SIMD, é possível melhorar desempenho sem conhecer diretamente assembly ou detalhes específicos de CPU
  • O nível necessário para todo desenvolvedor não é dominar técnicas complexas no estilo de simdutf e simdjson, mas reconhecer oportunidades de aplicar SIMD e aproveitar sua estrutura comum

Leituras relacionadas

1 comentários

 
GN⁺ 2 시간 전
Comentários do Hacker News

  • É um bom texto, mas começar dizendo que SIMD é fácil de entender e tão fácil de escrever quanto um loop for e já no primeiro exemplo transformar uma linha de código escalar em 12 linhas não convence muito
    Seria melhor admitir com franqueza que SIMD é difícil, mas vale a pena. Se o público é iniciante, não deveria usar termos específicos de SIMD como broadcast sem explicação logo no passo 1, e o passo 5, que explicou o tratamento da cauda escalar, foi uma boa escolha

    • SIMD e o primeiro exemplo não são exatamente difíceis, mas sim um trabalho bem mais trabalhoso
      É preciso descobrir quantos itens o hardware processa de uma vez, agrupar o trabalho nesse tamanho, desempacotar o resultado depois, tratar separadamente os itens restantes e até transformar constantes em vetores replicados. Nada disso é difícil por si só, mas aumenta o trabalho e deixa tudo mais incômodo
    • Aprendi Parallel-C, criado no auge do entusiasmo com o Transputer por volta de 1990, uma linguagem que adicionava recursos de programação paralela ao C
      Meu recurso favorito era par(; ; ), em que o compilador paralelizava automaticamente loops for sob certas condições de contorno
    • Achei interessante porque estou bem perto do público-alvo, mas o nível de dificuldade sobe rápido demais e ficou parecido com o infame meme de desenhar uma coruja
    • SIMD em si é simples; o estranho é a forma de usar operações paralelas em dados dentro de uma linguagem escalar
    • Um dos maiores erros no ensino técnico é declarar que algo é simples para tirar o medo das pessoas sobre o tema. Em vez de dizer que é simples, é preciso mostrar isso na prática
      Se o tema de fato é complexo, o certo é dividi-lo em partes menores e mais simples, organizar bem a sequência para que a pessoa consiga subir a curva de aprendizado íngreme e convencê-la de que vale a pena

  • Um conselho melhor seria que todo mundo deveria conhecer programação de arrays. Em geral, a otimização com SIMD exige esse modo de pensar, e técnicas realmente específicas de SIMD empacotado são surpreendentemente raras
    Programação de arrays facilita a vetorização automática pelo compilador, então mesmo sem usar SIMD diretamente costuma produzir código com bom desempenho

    • A abordagem de programação de arrays em que você faz todas as comparações primeiro e só depois encontra a primeira falha não ajuda muito quando a duração da execução é curta. Como ela não oferece saída antecipada por conta própria, pode gastar muito tempo com comparações desnecessárias
    • Não gosto de linguagens de código fechado e o MATLAB tem muitos defeitos, mas na universidade era muito natural escrever com eficiência código vetorizado para simulações numéricas
      Não tenho tanta experiência, mas Julia parece ser a linguagem moderna e mais expressiva que chega mais perto de oferecer capacidades semelhantes de vetorização

  • Nos últimos dias otimizei operações de matriz de um projeto de bioinformática com AVX-512 e fiquei muito satisfeito
    Na maioria das aplicações, o gargalo é ler grandes conjuntos de dados da memória, então em vez de reler várias vezes para várias operações, dá para fazer tudo de uma vez com registradores AVX e kernels fundidos. Ganhos de 5x são comuns; usei intrinsics diretamente, mas com o crate wide operações comuns ficam bem simples: https://docs.rs/wide/latest/wide/

  • A esmagadora maioria dos desenvolvedores não precisa aprender SIMD de forma alguma. Fico me perguntando por que se passa a impressão de que todo desenvolvedor precisa saber disso para ser um desenvolvedor de verdade

    • Pelo menos vale a pena saber que SIMD existe e o que ele pode fazer. Se você é desenvolvedor, provavelmente já escreveu algum loop quente que soma ou compara valores simples, e saber que o compilador pode otimizar isso para a arquitetura de CPU alvo é útil em várias situações

  • O título seria melhor como “todo mundo deveria saber quando SIMD não está sendo aplicado”
    Compiladores modernos vetorizam muito bem, mas de repente voltam para código escalar por causa de uma única suposição ou de um ramo com dependência de dados. Pode ser mais valioso saber consultar o relatório de otimização do compilador do que saber escrever SIMD

    • A solução para uma vetorização automática ruim é escrever código SIMD manualmente, então fico em dúvida se saber ler relatórios de otimização é mesmo mais valioso do que isso
      Se você só consegue identificar o problema, no fim das contas acaba em um “que pena”
    • Foi exatamente isso que aconteceu na prática: https://xcancel.com/mitchellh/status/2079672171321081908#m

  • No ano passado comecei a aprender SIMD em x86 e ARM ao criar um sintetizador de áudio: https://github.com/seclorum/SIMDSynth
    A arquitetura de um sintetizador multitimbral e polifônico foi muito adequada para aprender os princípios de SIMD, porque aplica o mesmo processamento a vários fluxos de dados. Mas depurar foi bem difícil, e eu realmente senti falta de um simulador que permitisse entender o estado de cada pipeline de processamento; investigar ferramentas para SIMD parece exigir outro grande investimento

  • O texto é bom e seria ótimo se mais linguagens suportassem SIMD, mas é um pouco estranho dizer que “todo programador deveria saber disso” quando as duas linguagens mais populares não oferecem suporte nativo a SIMD

    • É difícil afirmar que as linguagens mais populares também sejam as mais usadas pelos engenheiros de software que são o público-alvo deste tipo de texto

  • Mesmo que você não vá escrever SIMD à mão ou planeje deixar isso para a IA, ainda precisa saber que tipos de trabalho podem ficar mais rápidos com SIMD em certo hardware. Só assim dá para projetar algoritmos e estruturas de código de modo que a aplicação de SIMD seja possível
    O efeito das dependências de dados, o custo de aumentar a largura dos elementos vetoriais e como evitá-lo, como transformar condições e desvios em máscaras e características como “não existe instrução de divisão” são coisas muito mais fáceis de internalizar depois de usar SIMD nem que seja um pouco

    • Quase não se fala sobre quando SIMD realmente acelera
      Funciona bem ao inspecionar ou transformar grandes blocos contíguos de dados de uma vez, mas se você precisa tomar uma decisão a cada poucos bytes de entrada, pode acabar igual ou até mais lento que a abordagem escalar. SIMD não é um botão mágico de aceleração

  • Este é um vídeo útil em que Casey Muratori explica como a equipe de desenvolvimento de The Witness resolveu um problema real de desempenho com SIMD: https://www.youtube.com/watch?v=Ge3aKEmZcqY

    • Excelente apresentação, mas é longa demais para eu recomendar a outras pessoas; seria ótimo se houvesse uma versão em texto focada nos pontos principais
      É um bom exemplo de integração vertical para desempenho: mostra por que abstrações gerais existem e por que precisam ser genéricas e, depois de entender isso, como em certos casos de uso é possível integrar verticalmente da definição do problema até o SIMD para obter grandes ganhos

  • Antes de entrar em micro-otimizações como SIMD, é preciso revisar seriamente as estruturas de dados e os padrões de acesso
    No passado, apliquei SIMD em código Zig, mas o modelo de estrutura de dados era o oposto do que a otimização exigia, como colocar pneus de corrida de alto desempenho em uma lata-velha com o motor quebrado. Era um caso típico de otimização prematura, sem nem medir o desempenho e sem considerar onde a memória era alocada
    Hoje, vejo os dados como tabelas SQL e projeto a estrutura em torno de possíveis chaves primárias e padrões de acesso. Antes, eu usava árvores apontando para outras structs no heap, acumulando ao mesmo tempo as desvantagens de listas encadeadas, a fragmentação de vários vetores no heap e o custo lento de criação e liberação. Só o Drop já consumia uma parte considerável do tempo de execução
    Como árvores sempre podem ser linearizadas, avalio os padrões de acesso e inserção, se a estrutura realmente é uma árvore ou outro grafo, e se deve ser armazenada como Vec ou como uma struct de vários Vec. Como resultado, o código ficou mais rápido e mais simples, os dados passaram a ficar reunidos em arranjos homogêneos, o que facilita para o compilador aplicar otimizações SIMD e aproveitar o cache L1, e, quando necessário, também dá para escrever diretamente código SIMD sem desvios
    Material relacionado: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

    • Para acelerar hot loops com SIMD, o essencial é layout de dados e estrutura amigável ao cache
      Em gargalos reais, é preciso evitar alocação de memória, consultas a tabelas de funções virtuais e indireções excessivas. Até o vector do C++ nem sempre é a melhor opção se puder disparar alocações inesperadas
    • Como engenheiro de performance, é um problema com que sempre me deparo. Performance começa na arquitetura, e em hot paths com layout de dados ruim há um limite para o desempenho que se consegue extrair
      Em contrapartida, código orientado a dados quase sempre dá suporte fácil a threading e SIMD
    • Mais fundamental ainda, o padrão de acesso à memória é importante
      Curiosamente, no fim as rotinas de CPU também acabam sendo escritas no estilo de GPU, e uma abordagem é usar structs de arrays no estilo Parquet em vez de array de objetos
    • Tabelas são uma forma eficiente de implementar grafos genéricos e, a menos que seja possível especializar o grafo, é a melhor representação que conheço