Dissecando a instrução ternária de lógica de bits do AVX

 (arnaud-carre.github.io)
2 pontos por GN⁺ 2024-10-07 | 1 comentários | Compartilhar no WhatsApp
  • O vpternlogd do AVX-512 é uma instrução SIMD que executa, de uma vez, qualquer lógica Booleana arbitrária bit a bit de três entradas, escolhida por um valor imediato de 8 bits
  • O ponto principal não é decorar expressões lógicas complexas, mas enxergar o #imm8 como uma tabela de consulta para os 8 casos possíveis das três entradas A/B/C
  • O blitter do Amiga, em 1985, também especificava combinações lógicas do mesmo jeito com três fontes de bitmap e um minterm de 8 bits; 0xE2 era muito usado para sprites com máscara
  • Ao ler os 8 bits da coluna de resultado de baixo para cima, obtém-se o valor imediato, então condições como “exatamente duas das três entradas são 1” também podem ser montadas diretamente como 0x68
  • O exemplo de vpternlogd na documentação da Intel e o comum 0xE2 da demoscene do Amiga se encontram nesse ponto, mostrando que instruções SIMD modernas e hardware gráfico retrô compartilham a mesma sensibilidade de projeto

vpternlogd do AVX-512

  • O vpternlogd é uma instrução ternária de lógica bit a bit que chamou atenção no material de apresentação do projeto da ISA AVX-512
  • Ela recebe três entradas A, B e C e pode expressar qualquer lógica Booleana em uma única instrução
    • Ex.: (NOT A) OR ((NOT B) XOR (C AND A))
  • As entradas podem ser registradores de 512 bits, permitindo aplicar uma lógica complexa aos 512 bits inteiros ao mesmo tempo
  • Em vez de continuar adicionando instruções dedicadas como foo_and_a_or_not_b, várias lógicas são tratadas com uma única instrução flexível e um valor imediato de 8 bits
VPTERNLOGD r0, r1, r3, #imm8
  • O #imm8 determina qual função de lógica de bits será executada
  • Muitos documentos apenas dizem que o valor imediato “define uma função binária específica”, o que dificulta entender de forma intuitiva como ele é calculado na prática

Blitter do Amiga e minterm

  • Nos computadores dos anos 1980, era comum usar chips customizados para processamento gráfico
  • O blitter do Commodore Amiga 500 aplicava operações lógicas ao mover gráficos bitmap de uma posição para outra
  • Ele lidava com até três fontes de bitmap, e a operação lógica entre elas era especificada por um valor de 8 bits chamado minterm
  • Nesse sentido, ele tem a mesma estrutura do vpternlogd: três fontes e um valor de 8 bits para escolher a combinação lógica
  • Muitos programadores de Amiga reutilizavam valores frequentes em vez de entender diretamente como calcular o minterm
    • 0x00 para limpar um buffer
    • 0xE2 para desenhar um sprite com máscara
  • O “Amiga Hardware Reference Manual”, de 1989, explicava o cálculo de minterms com uma notação confusa, o que não ajudava muito os criadores de demos da época

Calculando o valor de 8 bits como tabela de consulta

  • O #imm8 ou minterm pode ser visto não como uma combinação de operadores lógicos, mas como uma tabela de consulta com 8 entradas
  • Como as três entradas A, B e C só podem ser 0 ou 1, existem 8 combinações possíveis
  • Basta preencher diretamente a quarta coluna com o resultado desejado
A B C Resultado desejado
0 0 0 ?
0 0 1 ?
0 1 0 ?
0 1 1 ?
1 0 0 ?
1 0 1 ?
1 1 0 ?
1 1 1 ?
  • Por exemplo, se você quiser que o resultado seja 1 quando exatamente duas das três entradas forem 1, preencha a quarta coluna com os valores correspondentes a essa condição
  • Lendo os 8 bits dessa coluna de baixo para cima, obtém-se 01101000, ou seja, 0x68
  • Portanto, a função 0x68 define o resultado como 1 quando exatamente duas das três entradas são 1
  • Da mesma forma, é possível obter o valor de #imm8 necessário para qualquer função lógica arbitrária entre as três fontes

O 0xE2 do sprite com máscara

  • Um dos valores de minterm mais comuns no Amiga é 0xE2
  • Esse valor era muito usado para renderizar sprites 2D com máscara
    • A: bitmap do sprite
    • B: máscara do sprite
    • C: plano de fundo
  • A condição pode ser expressa como uma lógica de programa simples
    • se o pixel de máscara B estiver ativado, o resultado é o sprite A
    • se o pixel de máscara B não estiver ativado, o resultado é o plano de fundo C
A B C Resultado desejado
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
  • Lendo a coluna de resultado de baixo para cima, obtemos 11100010, isto é, 0xE2
  • 0xE2 é um valor de minterm extremamente comum na cultura demoscene do Amiga

Uma conexão curiosa com a documentação da Intel

Leituras relacionadas

1 comentários

 
GN⁺ 2024-10-07
Comentários no Hacker News

  • Há uma forma simples de obter o valor imediato a partir da expressão que você quer calcular. Por exemplo, se quiser calcular (NOT A) OR ((NOT B) XOR (C AND A)), basta escrever algo como ~_MM_TERNLOG_A | (~_MM_TERNLOG_B ^ (_MM_TERNLOG_C & _MM_TERNLOG_A))
    É literalmente a expressão que você quer calcular, e ela é avaliada como o valor imediato a partir das constantes _MM_TERNLOG_A/B/C definidas nos headers de intrinsics do gcc e do clang: typedef enum { _MM_TERNLOG_A = 0xF0, _MM_TERNLOG_B = 0xCC, _MM_TERNLOG_C = 0xAA } _MM_TERNLOG_ENUM;
    No MSVC, basta defini-las diretamente

    • Para não parecer mágica, escreva em binário: A = 0b11110000, B = 0b11001100, C = 0b10101010
    • O manual do Amiga recomenda normalizar para a forma normal disjuntiva

  • Pelo título, achei que queria dizer que essa instrução não funcionava direito. Na verdade, o texto só explica como ela funciona

    • Entendi “busted” aqui como no sentido de ter flagrado que o pessoal da Intel é fã do Amiga. Parece que algo se perdeu na passagem do francês, língua nativa do autor, para o inglês

  • Meu eu adolescente não escreveu “CRAP!” naquela página do manual de hardware, mas fiquei olhando para ela por muito tempo tentando entender
    No fim, como quase todo mundo, encontrei os Bobs e o BLTCON0 para cópias simples e fingi que aquela parte não existia
    Ainda assim, alguns anos depois tirei A+ em lógica computacional na universidade, então talvez aquele trauma tenha ajudado em alguma medida

  • Sobre o título: “ternary logic” normalmente significa lógica com três valores de verdade. Mas este texto trata de uma instrução de compilador que lida com qualquer porta lógica binária de três entradas

    • O nome da instrução x86 é ternlog e o intrinsic também é ternarylogic, então, embora seja meio lamentável, o título é adequado
      Além disso, bitwise já ajuda de certa forma a distinguir de “lógica de três valores”, e ternary também é usado com muita frequência para significar três entradas. a ? b : c também costuma ser chamado de operador ternário e, de fato, ternlog consegue imitar essa operação ternária; o texto trata justamente disso
    • É mais próximo de “uma instrução lógica ternária” do que de “uma instrução de lógica ternária”
    • Não sei o que seria lógica com três valores de verdade. Talvez você esteja pensando em trinary, não ternary
      Do ponto de vista de C++, JavaScript e Python, a expressão ternária no formato (a < b) ? 5 : 2 parece ser o uso mais comum. https://www.programiz.com/cpp-programming/ternary-operator
      De todo modo, qualquer suposição não importa muito. Palavras ou expressões costumam ter vários significados, e ternary significa composto por três partes, então também se aplica aqui
    • Aqui ternary não tem esse sentido
      Em C, + é um operador binário porque recebe duas entradas, e ?: é um operador ternário porque recebe três entradas. Ele só costuma ser chamado de “the ternary operator” por ser o único em C; não há nada essencialmente especial nele
      vpternlogd implementa qualquer operador ternário bit a bit com três entradas
    • Eu também fiquei confuso com essa parte. Mas um nome como “avalia uma expressão binária de três termos” seria menos conciso

  • Fiquei pensando se não é parecido com a função BitBlt do Windows. Pelo menos desde o Windows 3.1, se não me engano, ela existe, e o parâmetro op define como combinar origem, destino e máscara
    Lembro que havia nomes de códigos como BLACKNESS, que gera preto independentemente das entradas, e COPY, que copia a origem para o destino. BLACKNESS e WHITENESS tinham uma sonoridade estranhamente poética
    Pelo que lembro do Petzold, ela era implementada em software, mas na chamada o opcode era convertido em assembly sob medida dentro da função, então parecia ser um caso raro de código automodificável no sistema operacional Windows

    • Isso mesmo. BitBlt originalmente usava “operation codes” complexos de 16 bits que armazenavam operações binárias em notação polonesa reversa
      Depois foi adicionado um “operation index” que guardava a mesma informação em 1 byte, como no Amiga, mais curto e elegante. Hoje cada raster operation code contém tanto o operation index quanto o operation code, então a codificação é redundante. https://devblogs.microsoft.com/oldnewthing/20180528-00/?p=98...

  • É igual ao modo como FPGAs implementam funções lógicas arbitrárias como tabelas de consulta

    • Basicamente, CPU, GPU e FPGA estão convergindo para formas evolutivas parecidas do mesmo caranguejo computacional. Elas expõem as mesmas capacidades com áreas de otimização diferentes
    • Toda lógica pode ser implementada com memória, e toda memória pode ser implementada com lógica em alguma configuração com realimentação
      Só que, exceto para propósitos especiais como FPGAs ou a instrução deste texto, normalmente não se faz isso. Registradores rápidos e RAM estática às vezes são feitos com lógica, mas é mais comum fazê-los diretamente com transistores do que com portas
    • A maioria é assim, mas não todas. A Actel/Microsemi usa pequenas árvores de multiplexadores e portas
    • A unidade lógica e aritmética 74181 também faz isso

  • Se você for a https://www.sandpile.org e procurar VPTERNLOG na página de opcodes de 3 bytes https://www.sandpile.org/x86/opc_3.htm, também verá a AVX512BITALG2, uma variante de mascaramento de byte/word que parece ter sido planejada pela Intel no passado
    Ela também aponta, a partir do operando Ib, para uma página de tabela-verdade ternária com todos os 256 casos: https://www.sandpile.org/x86/ternlog.htm

  • A escolha da função E2 como exemplo na documentação talvez seja porque ela é um mux praticamente básico e padrão entre as funções booleanas de três entradas: se B, então A; caso contrário, C
    É uma função universal, então não é preciso ser necessariamente fã do Amiga para escolhê-la. Claro, talvez fossem fãs mesmo

  • Outro exemplo de operações bit a bit guardadas em um inteiro são os códigos ROP do GDI do Win32: https://learn.microsoft.com/en-us/windows/win32/gdi/ternary-...

  • Eu não tinha o manual oficial de hardware do Amiga; em vez disso, li um livro chamado “Mapping the Amiga”. Ele explicava a mesma coisa de forma um pouco mais prolixa
    Não lembro quais mintermos usei na época, mas acho que, com esse livro, de algum modo implementei coisas como shadebobs, bobs e desenho de linhas 3D com XOR
    A página correspondente de Mapping the Amiga: https://archive.org/details/1993-thomson-randy-rhett-anderso...