Faster Positional-Population Counts for AVX2, AVX-512, and ASIMD

Este artigo apresenta um algoritmo otimizado para o cálculo de contagens populacionais posicionais (pospopcnt) utilizando instruções SIMD (AVX2, AVX-512 e ASIMD), alcançando velocidades próximas ao limite de transferência de memória mesmo para pequenos conjuntos de dados e oferecendo melhorias na estrutura do algoritmo, no tratamento de arrays desalinhados ou curtos e na acumulação de resultados intermediários.

O essencial

Imagine que você tem uma pilha gigante de cartões de identificação. Cada cartão tem uma pequena janela com 32 ou 64 luzinhas (bits). Em alguns cartões, a luzinha número 5 está acesa; em outros, a número 12; e em alguns, várias luzes estão acesas ao mesmo tempo.

O problema que este artigo resolve é: como contar, super rápido, quantas vezes cada número de luzinha (de 1 a 64) foi aceso em toda a pilha de cartões?

Se você fizesse isso manualmente, pegando um cartão de cada vez e olhando cada luzinha, levaria uma eternidade. O artigo apresenta uma nova "máquina" (um algoritmo) que usa a força bruta dos processadores modernos para fazer essa contagem em frações de segundo, mesmo para pilhas pequenas ou gigantes.

Aqui está a explicação simplificada, usando analogias do dia a dia:

1. O Problema: A Pilha de Cartões Desorganizada

Normalmente, os computadores contam quantas luzes estão acesas em um cartão (isso é chamado de "popcount"). Mas aqui, queremos saber onde elas estão acesas. Queremos saber: "Quantas vezes a luz 1 acendeu? E a luz 2? E a luz 3?"

Antes deste trabalho, existia um método antigo (feito por Klarqvist e colegas) que era como usar um caminhão de mudanças para levar apenas uma caixa de cada vez. Funcionava muito bem se você tivesse uma cidade inteira de caixas (milhares de dados), mas era lento e ineficiente se você tivesse apenas uma caixa (poucos dados).

2. A Solução: O "Truque" dos Engenheiros

Os autores (Robert, Daniel e Florian) criaram uma nova abordagem que funciona como uma linha de montagem de alta velocidade. Eles usaram três ideias principais:

A. O "Carregador de Caixas" (CSA - Carry-Save Adder)

Imagine que você tem 15 pessoas (vetores de dados) tentando carregar caixas para um caminhão.

• O jeito antigo: Cada pessoa colocava uma caixa no caminhão, e o motorista esperava, anotava o número e chamava a próxima.
• O jeito novo (CSA): As 15 pessoas jogam as caixas em uma esteira. Em vez de contar uma por uma, elas usam um sistema de "empilhamento inteligente". Elas juntam 3 caixas e as transformam em 2 caixas maiores (uma leve e uma pesada). Fazem isso várias vezes em paralelo.
• Resultado: Em vez de contar 15 caixas separadamente, eles reduzem tudo para apenas 4 ou 5 pilhas grandes muito rapidamente. É como transformar 15 caixas de areia em 4 sacos de cimento compactados.

B. A "Torre de Transposição" (Bit-Parallel Transposition)

Depois de compactar as caixas, elas ainda estão bagunçadas. A luz 1 de um cartão pode estar misturada com a luz 2 de outro.

• A analogia: Imagine que você tem 4 baralhos de cartas embaralhados. Você precisa separar todas as cartas de "Ás" em uma pilha, todas as "Reis" em outra, etc.
• O truque: O algoritmo faz uma "dança" com os dados. Ele pega as cartas e as rearranja em um instante, usando instruções especiais do processador, para que todas as "luzes 1" fiquem juntas, todas as "luzes 2" fiquem juntas, e assim por diante. Isso é feito de forma que o processador faz tudo ao mesmo tempo, não uma carta por vez.

C. O "Pulo do Gato" para Pilhas Pequenas

O método antigo era lento para pilhas pequenas (menos de 4 mil cartões). O novo método tem um "modo turbo" para isso.

• A analogia: Se você tem apenas 3 cartas para contar, não precisa montar uma linha de montagem gigante. O novo algoritmo usa um "caminhão de entrega expresso" que entra, pega os dados, faz a contagem e sai antes que você perceba. Isso permite que a velocidade seja alta desde o primeiro byte de dados.

3. Os Processadores (AVX2, AVX-512 e ASIMD)

O artigo foi testado em três tipos de "fábricas" (processadores):

1. AVX2 (Intel): Como um caminhão de 256 bits. Rápido, mas tem um limite de largura.
2. AVX-512 (Intel): Como um caminhão de 512 bits (o dobro de largo!). Ele carrega o dobro de dados de uma vez. O algoritmo brilha aqui, atingindo velocidades absurdas (91 Gigabytes por segundo!). É como se o caminhão fosse tão largo que ele carrega a cidade inteira de uma vez.
3. ASIMD (ARM): Usado em celulares e servidores modernos (como os da AWS). É como um caminhão menor (128 bits), mas muito ágil. O algoritmo foi adaptado para ser eficiente mesmo nesse tamanho menor.

4. Por que isso importa?

Imagine que você é um biólogo tentando encontrar padrões no DNA de milhões de pessoas, ou um banco tentando analisar milhões de transações em segundos.

• Antes: Você esperava horas para processar os dados.
• Agora: Com este algoritmo, o computador processa os dados na velocidade da memória (o limite físico de quão rápido os dados podem viajar do disco para a memória).

Resumo da Ópera

Este artigo é sobre como organizar uma bagunça de dados de forma tão eficiente que o computador não perde tempo nem com um único segundo.

Eles pegaram uma técnica antiga de "empilhar caixas" (Harley-Seal), melhoraram a forma como as caixas são organizadas (transposição bit a bit) e criaram um sistema que funciona tão bem que, para dados grandes, a velocidade é limitada apenas pela velocidade do cabo de internet que conecta a memória ao processador, e não pela inteligência do código.

Em suma: Eles transformaram um trabalho de "contagem manual" em uma "dança sincronizada de robôs", tornando tudo muito mais rápido, desde uma única caixa até uma cidade inteira de dados.

Resumo técnico

Resumo Técnico: Contagens Populacionais Posicionais Mais Rápidas para AVX2, AVX-512 e ASIMD

1. O Problema

O problema central abordado é o cálculo eficiente da contagem populacional posicional (positional population count ou pospopcnt). Diferente da contagem populacional tradicional (que soma todos os bits definidos em um número), a versão posicional conta quantas vezes cada posição de bit específica foi definida em uma sequência de palavras de $w$ bits.

• Aplicações: Esta operação é fundamental em bioinformática (emparelhamento aproximado de sequências de DNA), engenharia de bancos de dados (agrupamento de variáveis categóricas de baixa cardinalidade codificadas em one-hot) e processamento digital.
• Desafio: Implementações anteriores, como a de Klarqvist et al., utilizavam técnicas SIMD (Single Instruction Multiple Data) baseadas no esquema de Harley-Seal. No entanto, essas implementações sofriam de:
  • Alto custo de inicialização, exigindo arrays grandes (vários KiB) para superar o desempenho de código escalar.
  • Ineficiência no processamento de dados desalinhados e arrays muito curtos.
  • Acumulação de resultados intermediários que não era totalmente paralela, criando gargalos.

2. Metodologia

Os autores propõem um algoritmo refinado que otimiza o esquema de Harley-Seal utilizando redes de Somador de Guarda de Transporte (CSA - Carry-Save Adder) e lógica de transposição de bits em paralelo.

Principais componentes da metodologia:

• Redes CSA Otimizadas:

  • O algoritmo utiliza redes CSA para comprimir vetores de bits de entrada em acumuladores.
  • Diferente do trabalho anterior, eles introduzem uma iteração inicial separada usando uma rede CSA15 (processando 15 vetores de entrada) para gerar acumuladores iniciais, em vez de inicializar acumuladores com zeros e entrar diretamente no loop principal. Isso reduz o número de operações de adição necessárias no início.
  • O loop principal utiliza uma rede CSA16+4, processando 16 vetores de entrada e somando aos 4 acumuladores existentes, gerando um novo vetor de "carry" ($a_{16}$) que é processado imediatamente, enquanto os outros 4 acumuladores são mantidos para a próxima iteração.

• Acumulação Paralela de Bits (Bit-Parallel Accumulation):

  • Uma inovação chave é a forma como os bits do vetor de carry ($a_{16}$) são somados aos contadores. Em vez de iterar sobre cada bit (abordagem escalar), o algoritmo realiza uma transposição e redução vetorial completa.
  • Os bits são divididos em pares (pares/ímpares), somados e reduzidos recursivamente (de bits para nibbles, bytes, e palavras de 16 bits) usando instruções de shuffle e adição vetorial. Isso reduz a complexidade de $O(w)$ para $O(\log w)$.

• Gerenciamento de Bordas (Head e Tail):

  • Cabeçalho (Head): Para lidar com endereços de memória não alinhados, o algoritmo carrega um vetor inicial, limpa os bytes antes do início dos dados válidos e processa o restante com a rede CSA15, evitando penalidades de desalinhamento ou processamento escalar lento.
  • Cauda (Tail) e Arrays Curtos: Para entradas menores que o tamanho do bloco principal, um algoritmo especializado processa os bits restantes bit a bit (ou byte a byte) usando máscaras de predicado (em AVX-512) ou replicação de bytes e operações de comparação (em AVX2/ASIMD), garantindo bom desempenho mesmo para arrays de apenas alguns bytes.

• Suporte Multi-Arquitetura:

  • O algoritmo foi implementado para AVX2 (Intel, 256 bits), AVX-512 (Intel, 512 bits) e ASIMD (ARM AArch64, 128 bits).
  • Adaptações específicas foram feitas para explorar instruções nativas de cada arquitetura, como vpternlogd no AVX-512 (que executa lógica ternária em uma única instrução) e instruções bsl/bit no ASIMD.

3. Contribuições Chave

1. Melhoria do Esquema Harley-Seal: Refinamento da estrutura do algoritmo com uma rede CSA inicial dedicada e uma rede de loop principal otimizada, reduzindo a latência de inicialização.
2. Acumulação Totalmente Vetorial: Substituição da acumulação escalar de bits por uma transposição e redução vetorial completa, permitindo que os resultados intermediários sejam somados aos contadores finais de forma massivamente paralela.
3. Desempenho em Dados Pequenos e Desalinhados: Tratamento eficiente de arrays desalinhados e muito curtos (a partir de 1 byte), eliminando a necessidade de grandes volumes de dados para atingir o peak performance.
4. Implementações Portáveis: Fornecimento de código de assembly otimizado para as principais extensões SIMD modernas (AVX2, AVX-512, ASIMD), demonstrando que o algoritmo é limitado pela largura de banda da memória (memory-bound) mesmo em arrays de apenas 4 KiB.

4. Resultados

Os benchmarks foram realizados em processadores Intel Xeon W-2133 (Skylake) e AWS Graviton 3 (Neoverse V1).

• AVX-512: O algoritmo atingiu um pico de 91,0 GB/s para entradas de 512 KiB. Isso representa uma melhoria de 53% em relação à melhor implementação anterior de Klarqvist et al. (59,4 GB/s). O novo algoritmo utiliza apenas 0,09 instruções por byte, contra 0,13 do anterior.
• AVX2: Alcançou 34,8 GB/s. Embora seja menos da metade da velocidade do AVX-512 (devido ao comprimento do vetor), o desempenho é robusto e supera significativamente o código escalar.
• ASIMD (ARM): Alcançou 16 GB/s, atingindo cerca de 83% do limite teórico (roofline) para a arquitetura testada.
• Arrays Curtos: Diferente do trabalho anterior, que sofria degradação severa em arrays pequenos, a nova implementação mantém desempenho próximo ao máximo desde o primeiro byte, superando implementações escalares mesmo para tamanhos de dados de poucos bytes.
• Eficiência: O algoritmo atingiu o estado de memory-bound (limitado pela largura de banda da memória) para arrays tão pequenos quanto 4 KiB, indicando que a computação é extremamente eficiente e não é o gargalo.

5. Significado e Impacto

Este trabalho representa um avanço significativo no processamento de dados binários de alta performance.

• Eficiência Operacional: Ao reduzir o número de instruções necessárias e otimizar o uso de registros e unidades de execução, o algoritmo libera recursos da CPU para outras tarefas.
• Versatilidade: A capacidade de lidar eficientemente com dados de qualquer tamanho (de bytes a gigabytes) e alinhamento torna a solução ideal para aplicações em tempo real e processamento de streams de dados, onde os tamanhos de dados variam imprevisivelmente.
• Adoção Prática: O artigo menciona que versões iniciais do algoritmo já estão sendo utilizadas em ferramentas de bioinformática (como o KMCP), validando sua utilidade prática imediata.
• Base para Futuro: A estrutura proposta serve como base para futuras otimizações em arquiteturas emergentes, como extensões de vetores de comprimento variável (SVE, RVV), embora desafios de implementação ainda existam nessas plataformas devido à falta de certas instruções de transposição.

Em resumo, os autores demonstraram que, através de uma reengenharia cuidadosa das redes de somadores e da lógica de transposição, é possível extrair o máximo desempenho das arquiteturas SIMD modernas para contagens populacionais posicionais, superando os limites anteriores de escalabilidade e eficiência.