Explorando la instrucción ternaria de lógica de bits de AVX

 (arnaud-carre.github.io)
2 puntos por GN⁺ 2024-10-07 | 1 comentarios | Compartir por WhatsApp
  • vpternlogd de AVX-512 es una instrucción SIMD que ejecuta de una sola vez cualquier lógica booleana arbitraria a nivel de bit sobre tres entradas, eligiéndola con un valor inmediato de 8 bits
  • La clave no está en memorizar expresiones lógicas complejas, sino en ver #imm8 como una tabla de consulta para los 8 casos posibles de las tres entradas A/B/C
  • El blitter del Amiga de 1985 también usaba el mismo método para definir combinaciones lógicas con tres fuentes de mapa de bits y un minterm de 8 bits, y 0xE2 se usaba a menudo para sprites con máscara
  • Si se leen los 8 bits de la columna de resultados de abajo hacia arriba, se obtiene el valor inmediato, así que condiciones como “exactamente dos de las tres entradas son 1” también pueden construirse directamente como 0x68
  • El ejemplo de vpternlogd en la documentación de Intel y el común 0xE2 de la demoscene de Amiga se cruzan aquí, mostrando que las instrucciones SIMD modernas y el hardware gráfico retro comparten la misma intuición de diseño

vpternlogd de AVX-512

  • vpternlogd es una instrucción ternaria de lógica a nivel de bit que destacó en el material de presentación del diseño de la ISA AVX-512
  • Recibe tres entradas A, B y C, y puede expresar cualquier lógica booleana en una sola instrucción
    • Ejemplo: (NOT A) OR ((NOT B) XOR (C AND A))
  • Las entradas pueden ser registros de 512 bits, por lo que es posible aplicar una lógica compleja sobre los 512 bits completos al mismo tiempo
  • En vez de seguir agregando instrucciones dedicadas como foo_and_a_or_not_b, se resuelven muchas lógicas con una sola instrucción flexible y un valor inmediato de 8 bits
VPTERNLOGD r0, r1, r3, #imm8
  • #imm8 decide qué función de lógica de bits se ejecuta
  • Muchos documentos solo explican que el valor inmediato “determina cierta función binaria”, lo que dificulta entender de forma intuitiva cómo se calcula realmente

El blitter de Amiga y los minterms

  • En las computadoras de los años 80 era común usar chips personalizados para el procesamiento gráfico
  • El blitter de la Commodore Amiga 500 aplicaba operaciones lógicas mientras movía gráficos de mapa de bits de una posición a otra
  • Podía manejar hasta tres fuentes de mapa de bits, y las operaciones lógicas entre ellas se especificaban con un valor de 8 bits llamado minterm
  • Tiene la misma estructura que vpternlogd en el sentido de que selecciona una combinación lógica a partir de tres fuentes y un valor de 8 bits
  • Muchos programadores de Amiga reutilizaban valores frecuentes en vez de entender directamente cómo calcular el minterm
    • Para limpiar un búfer: 0x00
    • Para dibujar un sprite con máscara: 0xE2
  • El “Amiga Hardware Reference Manual” de 1989 explicaba el cálculo de minterms con una notación confusa, así que no fue de gran ayuda para quienes hacían demos en esa época

Calcular el valor de 8 bits como tabla de consulta

  • #imm8 o el minterm puede verse no como una combinación de operadores lógicos, sino como una tabla de consulta de 8 entradas
  • Como las tres entradas A, B y C pueden ser 0 o 1, existen 8 combinaciones posibles
  • Basta con llenar directamente la cuarta columna con el resultado deseado
A B C Resultado deseado
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 ejemplo, si se quiere que el resultado sea 1 cuando exactamente dos de las tres entradas son 1, se llena la cuarta columna con los valores que cumplen esa condición
  • Si luego se leen los 8 bits de esa columna de abajo hacia arriba, se obtiene 01101000, es decir 0x68
  • Por lo tanto, la función 0x68 pone el resultado en 1 cuando exactamente dos entradas valen 1
  • Del mismo modo, se puede obtener el valor #imm8 necesario para cualquier función lógica arbitraria entre las tres fuentes

El 0xE2 de los sprites con máscara

  • Uno de los valores de minterm más comunes en Amiga es 0xE2
  • Este valor se usaba con frecuencia al renderizar un sprite 2D con máscara
    • A: bitmap del sprite
    • B: máscara del sprite
    • C: fondo
  • La condición puede expresarse con una lógica de programa simple
    • Si el píxel de máscara B está activado, el resultado es el sprite A
    • Si el píxel de máscara B no está activado, el resultado es el fondo C
A B C Resultado deseado
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
  • Si se lee la columna de resultados de abajo hacia arriba, se obtiene 11100010, es decir 0xE2
  • 0xE2 es un valor de minterm muy común en la cultura demoscene de Amiga

Una conexión casual con la documentación de Intel

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-10-07
Opiniones en Hacker News

  • Hay una forma sencilla de obtener el valor inmediato a partir de la expresión que se quiere calcular. Por ejemplo, si quieres calcular (NOT A) OR ((NOT B) XOR (C AND A)), puedes escribirlo como ~_MM_TERNLOG_A | (~_MM_TERNLOG_B ^ (_MM_TERNLOG_C & _MM_TERNLOG_A))
    Es literalmente la expresión que se quiere calcular, y se evalúa como un valor inmediato a partir de las constantes _MM_TERNLOG_A/B/C definidas en los headers de intrinsics de gcc y clang: typedef enum { _MM_TERNLOG_A = 0xF0, _MM_TERNLOG_B = 0xCC, _MM_TERNLOG_C = 0xAA } _MM_TERNLOG_ENUM;
    En MSVC se pueden definir manualmente

    • Para que no parezca magia, basta escribirlo en binario: A = 0b11110000, B = 0b11001100, C = 0b10101010
    • El manual de Amiga recomienda normalizarlo a forma normal conjuntiva

  • Al ver solo el título pensé que significaba que esta instrucción no funcionaba bien. En realidad, el artículo solo explica cómo funciona

    • Entendí que aquí “busted” significa que descubrieron que la gente de Intel era fan de Amiga. Parece que algo se perdió al pasar del francés, la lengua materna del autor, al inglés

  • Mi yo adolescente no escribió “CRAP!” en esa página del manual de hardware, pero sí me quedé mirándola muchísimo tiempo tratando de entenderla
    Al final, como casi todos, terminé buscando y usando Bobs y BLTCON0 para copias simples, y fingí no haber visto esa parte
    Aun así, años después saqué A+ en lógica computacional en la universidad, así que quizá ese trauma ayudó en algo

  • Sobre el título: “ternary logic” normalmente significa lógica con tres valores de verdad. Pero este artículo trata de una instrucción de compilador que maneja todas las compuertas lógicas binarias con tres entradas

    • El nombre de la instrucción x86 es ternlog y el intrinsic también es ternarylogic, así que, aunque sea una lástima, el título es adecuado
      Además, bitwise ya ayuda en cierta medida a distinguirlo de la “lógica de tres valores”, y ternary también se usa muy a menudo para indicar tres entradas. A a ? b : c se le suele llamar operador ternario, y de hecho ternlog puede imitar esa operación ternaria; el artículo trata justo de eso
    • No es tanto una “instrucción de lógica ternaria”, sino una “instrucción lógica ternaria”
    • No sé qué es una lógica con tres valores de verdad. Me pregunto si no estás pensando en trinary en vez de ternary
      Desde la perspectiva de C++, JavaScript y Python, una expresión ternaria de la forma (a < b) ? 5 : 2 parece ser el uso más común. https://www.programiz.com/cpp-programming/ternary-operator
      En cualquier caso, no importa mucho qué suposición se haga. Las palabras o frases suelen tener varios significados, y ternary significa compuesto de tres partes, así que también encaja aquí
    • Aquí ternary no significa eso
      En C, + es un operador binario porque recibe dos entradas, y ?: es un operador ternario porque recibe tres. Como es el único en C, normalmente se le llama “the ternary operator”, pero no tiene nada intrínsecamente especial
      vpternlogd implementa todos los operadores ternarios bit a bit con tres entradas
    • A mí también me confundió esa parte. Aunque “evalúa una expresión binaria de tres términos” sería un nombre menos conciso

  • Me pregunto si se parece a la función BitBlt de Windows. Creo que existía al menos desde Windows 3.1, y el parámetro op definía cómo combinar origen, destino y máscara
    Recuerdo que había nombres de códigos como BLACKNESS, que genera negro sin importar la entrada, y COPY, que copia el origen al destino. BLACKNESS y WHITENESS tenían un eco extrañamente poético
    Por lo que recuerdo de Petzold, estaba implementado en software, pero al invocarlo el opcode se traducía dentro de la función a ensamblador personalizado, así que parecía ser un raro caso de código automodificable en el sistema operativo Windows

    • Correcto. Originalmente, BitBlt usaba “operation codes” complejos de 16 bits que almacenaban operaciones binarias en notación polaca inversa
      Luego, al estilo de Amiga, se agregó un “operation index” que guarda la misma información en 1 byte, más corto y elegante. Hoy cada raster operation code codifica tanto el operation index como el operation code, por lo que la codificación queda duplicada. https://devblogs.microsoft.com/oldnewthing/20180528-00/?p=98...

  • Es igual a la forma en que una FPGA implementa funciones lógicas arbitrarias con tablas de consulta

    • Básicamente, CPU, GPU y FPGA convergen hacia la misma forma evolutiva de cómputo. Exponen las mismas capacidades con distintas áreas de optimización
    • Toda lógica puede implementarse con memoria, y toda memoria puede implementarse con lógica que tenga algún tipo de configuración de retroalimentación
      Pero salvo para propósitos especiales como las FPGA o la instrucción de este artículo, normalmente no se hace así. Los registros rápidos y la RAM estática a veces se construyen con lógica, pero es más común hacerlos directamente con transistores que con compuertas
    • La mayoría sí, pero no todas. Actel/Microsemi usa pequeños multiplexores y árboles de compuertas
    • La unidad aritmético-lógica 74181 también lo hace así

  • Si vas a https://www.sandpile.org y buscas VPTERNLOG en la página de opcodes de 3 bytes https://www.sandpile.org/x86/opc_3.htm, también puedes ver AVX512BITALG2, una variante de enmascaramiento de bytes/words que Intel parece haber planeado en el pasado
    Además, desde el operando Ib enlaza a una página de tabla lógica ternaria con los 256 casos posibles: https://www.sandpile.org/x86/ternlog.htm

  • Puede que hayan elegido la función E2 como ejemplo en la documentación porque es casi la mux más básica y estándar entre las funciones booleanas de tres entradas: si B, entonces A; si no, C
    Es una función universal, así que no hace falta ser fan de Amiga para elegirla. Aunque, claro, también podrían haberlo sido

  • Otro ejemplo de empaquetar operaciones bit a bit dentro de un entero son los códigos ROP de GDI en Win32: https://learn.microsoft.com/en-us/windows/win32/gdi/ternary-...

  • No tenía el manual oficial de hardware de Amiga; en su lugar consultaba un libro llamado “Mapping the Amiga”. Explicaba lo mismo de forma un poco más extensa
    No recuerdo qué minterms usé entonces, pero creo que con ese libro de alguna manera logré implementar cosas como shadebobs, bobs y dibujo de líneas 3D con XOR
    La página correspondiente de Mapping the Amiga: https://archive.org/details/1993-thomson-randy-rhett-anderso...