Esta é a pseudo-decodificação da minha apresentação no !! Con 2019 .A maioria das arquiteturas de processadores em uso atualmente possui instruções chamadas
popcount , abreviação de '
popcount count'. Ela faz o seguinte: conta o número de bits definidos em uma palavra de máquina. Por exemplo (vamos
popcount(00100110) palavras de 8 bits por simplicidade),
popcount(00100110) é 3 e
popcount(01100000) é 2.
Pode surpreendê-lo bastante, assim como eu, mas é tudo o que ela faz! Parece não ser muito útil, certo?
Eu pensei que isso fosse uma adição recente a alguns casos de uso hiperespecializados, mas na verdade está presente nas arquiteturas de processadores desde pelo menos 1961:
Então o que está acontecendo?
Instrução NSA
popcount também
popcount conhecido como "instrução NSA", e um
tópico muito interessante no comp.arch discute seu uso em criptografia. Há rumores de que ele foi originalmente adicionado ao conjunto de instruções da CPU a pedido da NSA. Conforme declarado
neste segmento de correio arquivado :
Era quase uma tradição enviar um de cada lote de carros CDC mais rápidos para um "bom cliente" - um caminhão desconhecido chegou e nunca mais foi ouvido.
Uma grande lenda, mas por que eles a usaram?
Uma medida do conteúdo é
o peso de Hamming , que é o número de caracteres diferentes de zero em uma string. Para uma string binária, isso é
popcount !
Conforme
explicado aqui , a NSA precisava criptografar as mensagens interceptadas e, como o CDC 6000 trabalhava com palavras de 60 bits, uma palavra era suficiente para armazenar a maioria dos alfabetos que os interessavam. Eles foram capazes de:
- Dividir a mensagem em linhas
- Defina um pouco para cada caractere único em uma string
- Use
popcount para contar o número de caracteres diferentes
- Use o contador como um hash para mais análises criptográficas
Curiosamente, a
popcount parece ter desaparecido dos conjuntos de instruções entre meados da década de 1970 e meados da década de 2000; portanto, o retorno deve ser explicado por algo diferente de aplicações criptográficas. Para que mais pode ser usado?
Bug fix
O conceito de peso de Hamming está relacionado à
distância de Hamming , que é o número de posições diferentes entre duas linhas do mesmo comprimento. Para duas cadeias binárias
x e
y , isso é apenas um
popcount após o XOR. Por exemplo:
00100110
01100000 ^
--------
01000110
popcount (01000110) = 3
Em aplicações de telecomunicações, isso ajuda a calcular a distância do sinal, onde uma palavra conhecida é transmitida ao longo do fio e o número de bits alterados é contado para estimar o erro de transmissão.
Em seguida, podemos projetar o
código de correção de erros apropriado. Por exemplo, se uma transmissão precisar suportar até dois bits modificados, as palavras de código deverão diferir em pelo menos 5 na distância de Hamming.
Redes neurais convolucionais binárias
E agora algo completamente diferente: redes neurais convolucionais binárias! Mas primeiro, o que é isso?
- Binário significa que usamos apenas matrizes de valores +1 (codificados como 1) e -1 (codificados como 0), diferentemente dos valores de ponto flutuante de 32 bits.
- Convolução significa multiplicação de matrizes?
- Redes neurais são sistemas inspirados no cérebro de animais (aqui estou nadando um pouco).
Portanto, devemos realizar a multiplicação de matrizes binárias. Mas o que há de especial em matrizes binárias?
A multiplicação de matrizes convencional por valores de 32 bits é adequada para computadores desktop com CPUs e GPUs poderosas, mas cada vez mais queremos realizar trabalhos úteis em dispositivos pequenos e simples como smartphones, roteadores, relógios inteligentes etc. Podemos decompor esses matrizes mais complexas para camadas de matrizes binárias, e é tão mais fácil trabalhar com elas e armazená-las que nos beneficiamos, apesar do aumento no número de camadas.
É aqui
popcount entra em cena. É usado para calcular o produto escalar de duas matrizes binárias:
a = xnor (x, y)
b = número de pessoas (a)
c = len (a)
ponto (x, y) = 2 × b - c
Veja
aqui e
aqui para mais detalhes.
Programação de xadrez
Muitos programas de xadrez armazenam dados em uma representação de
bitboard , que se encaixa convenientemente em uma palavra de 64 bits. A operação
Population Count foi usada para operações significativas com essa visão, como o cálculo da
mobilidade de uma figura.
Impressão digital molecular
Isso também está relacionado à distância de Hamming: as moléculas são de alguma forma misturadas e comparadas (usando
popcount ) para determinar quão semelhantes elas são. Veja
aqui para mais detalhes.
Tentativas mapeadas de matriz de hash (HAMT)
Foi aqui que aprendi sobre o
popcount ! HAMT é uma estrutura de dados (
criada por Phil Bagwell ) que pode armazenar um número muito grande de valores (geralmente 32 ou 64) em uma matriz em cada nó de tentativa. No entanto, alocar memória para uma matriz de 32 ou 64 elementos pode ser incrivelmente inútil toda vez, especialmente se a matriz realmente contiver apenas alguns elementos. A solução é adicionar uma máscara de bits na qual o número de bits definido corresponda ao número de elementos na matriz, o que permite que a matriz cresça e contraia conforme necessário. O cálculo do índice para um determinado elemento pode ser efetivamente feito usando
popcount . No
meu post sobre a implementação de estruturas HAMT, você pode aprender mais sobre como elas funcionam.
Estruturas de dados compactadas
Esta é uma nova e empolgante área de pesquisa que se concentra em como armazenar dados em um espaço mínimo, sem desempacotá-los para realizar um trabalho útil. Um dos métodos é pensar em termos de matrizes de bits (vetores de bits) que podem ser solicitadas em duas operações:
rank(i) conta o número de bits dados até o i-ésimo índice no vetor de bits
select(i) localiza o índice no qual o i-ésimo bit está definido
Para tornar essas operações eficientes em vetores de bits grandes, é necessário criar um índice e usá-lo de maneira eficaz, nos dois casos que envolvem
popcount . Aqui está uma boa visão geral do índice RRR. E, até onde eu sei, a abordagem moderna mais avançada é descrita no artigo
Estruturas de classificação e seleção com eficiência de espaço e alto desempenho em seqüências de bits não compactadas .
Otimizações do compilador
popcount tornou-se tão difundido que o
GCC e o
Clang são capazes de detectá-lo e substituí-lo por uma instrução
popcount . Imagine esta Clippy: "Oh, vejo que você está tentando implementar o
popcount , deixe-me sair e consertá-lo para você!" O código LLVM correspondente está
aqui . Daniel Lemyr o cita como um exemplo da mente incrível dos compiladores modernos.
Conclusão
Envolta em mistério no início de sua história, a instrução
popcount ser usada em todos os lugares, embora permanecesse um pouco incomum na instrução da CPU. Gosto da maneira como ele conecta áreas tão diferentes da ciência da computação e me pergunto quantas outras instruções tão estranhas existem. Se você tem seu próprio favorito, eu gostaria de ouvir sobre ela!