Décryptage de l’instruction ternaire logique bit à bit d’AVX

 (arnaud-carre.github.io)
2 points par GN⁺ 2024-10-07 | 1 commentaires | Partager sur WhatsApp
  • vpternlogd d’AVX-512 est une instruction SIMD qui exécute en une seule fois n’importe quelle logique booléenne bit à bit à trois entrées, sélectionnée via une valeur immédiate de 8 bits
  • L’idée clé n’est pas de mémoriser des expressions logiques complexes, mais de voir #imm8 comme une table de correspondance des 8 cas possibles pour les trois entrées A/B/C
  • Dès 1985, le blitter de l’Amiga utilisait lui aussi trois sources bitmap et un minterm de 8 bits pour définir de la même manière une combinaison logique ; 0xE2 était souvent utilisé pour les masked sprites
  • En lisant les 8 bits de la colonne résultat de bas en haut, on obtient la valeur immédiate ; une condition comme « exactement deux entrées sur trois valent 1 » se construit ainsi directement avec 0x68
  • L’exemple de vpternlogd dans la documentation d’Intel et le fréquent 0xE2 de la demoscene Amiga se rejoignent, montrant qu’une instruction SIMD moderne et un matériel graphique rétro partagent la même logique de conception

vpternlogd dans AVX-512

  • vpternlogd est une instruction de logique ternaire bit à bit qui a retenu l’attention dans les documents de présentation de la conception de l’ISA AVX-512
  • Elle prend trois entrées A, B et C, et permet d’exprimer n’importe quelle logique booléenne avec une seule instruction
    • Exemple : (NOT A) OR ((NOT B) XOR (C AND A))
  • Les entrées peuvent être des registres de 512 bits, ce qui permet d’appliquer une logique complexe simultanément sur l’ensemble des 512 bits
  • Au lieu d’ajouter sans cesse des instructions dédiées comme foo_and_a_or_not_b, on couvre de nombreuses logiques avec une instruction flexible et une valeur immédiate de 8 bits
VPTERNLOGD r0, r1, r3, #imm8
  • #imm8 détermine quelle fonction logique bit à bit sera exécutée
  • Beaucoup de documents se contentent d’expliquer que la valeur immédiate « détermine une certaine fonction binaire », ce qui rend la méthode de calcul concrète peu intuitive

Le blitter de l’Amiga et les minterms

  • Dans les années 1980, il était courant que les ordinateurs utilisent des puces personnalisées pour le traitement graphique
  • Le blitter du Commodore Amiga 500 appliquait des opérations logiques tout en déplaçant des graphismes bitmap d’un emplacement à un autre
  • Il pouvait traiter jusqu’à trois sources bitmap, et l’opération logique entre elles était spécifiée par un minterm de 8 bits
  • En ce sens, il partage la même structure que vpternlogd : trois sources et une valeur de 8 bits pour choisir la combinaison logique
  • Beaucoup de programmeurs Amiga réutilisaient des valeurs fréquentes plutôt que de comprendre en détail comment calculer le minterm
    • 0x00 pour effacer un buffer
    • 0xE2 pour dessiner un masked sprite
  • Le “Amiga Hardware Reference Manual” de 1989 expliquait le calcul des minterms avec une notation déroutante, ce qui n’aidait pas beaucoup les créateurs de démos de l’époque

Calculer la valeur de 8 bits comme une table de correspondance

  • #imm8 ou le minterm ne doit pas être vu comme une combinaison d’opérateurs logiques, mais comme une table de correspondance de 8 entrées
  • Comme les trois entrées A, B et C valent chacune 0 ou 1, il existe 8 combinaisons possibles
  • Il suffit de remplir directement la quatrième colonne avec le résultat souhaité
A B C Résultat souhaité
0 0 0 ?
0 0 1 ?
0 1 0 ?
0 1 1 ?
1 0 0 ?
1 0 1 ?
1 1 0 ?
1 1 1 ?
  • Par exemple, si l’on veut produire 1 lorsque exactement deux des trois entrées valent 1, il suffit de remplir la quatrième colonne selon cette condition
  • En lisant ensuite les 8 bits de la colonne résultat de bas en haut, on obtient 01101000, soit 0x68
  • La fonction 0x68 produit donc 1 lorsque exactement deux des trois entrées valent 1
  • On peut obtenir de la même manière la valeur #imm8 nécessaire pour n’importe quelle fonction logique entre trois sources

Le 0xE2 du masked sprite

  • L’une des valeurs de minterm les plus courantes sur Amiga est 0xE2
  • Cette valeur est souvent utilisée pour le rendu de sprites 2D masqués
    • A : bitmap du sprite
    • B : masque du sprite
    • C : arrière-plan
  • La condition s’exprime simplement avec une logique de programme classique
    • si le pixel de masque B est activé, le résultat est le sprite A
    • si le pixel de masque B n’est pas activé, le résultat est l’arrière-plan C
A B C Résultat souhaité
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
  • En lisant la colonne résultat de bas en haut, on obtient 11100010, soit 0xE2
  • 0xE2 est une valeur de minterm extrêmement fréquente dans la culture demoscene Amiga

Un lien inattendu avec la documentation d’Intel

À lire aussi

1 commentaires

 
GN⁺ 2024-10-07
Commentaires Hacker News

  • Il existe une méthode simple pour obtenir la valeur immédiate à partir de l’expression que l’on veut calculer. Par exemple, si l’on veut calculer (NOT A) OR ((NOT B) XOR (C AND A)), il suffit d’écrire quelque chose comme ~_MM_TERNLOG_A | (~_MM_TERNLOG_B ^ (_MM_TERNLOG_C & _MM_TERNLOG_A))
    C’est littéralement l’expression que l’on veut calculer, et elle est évaluée en valeur immédiate à partir des constantes _MM_TERNLOG_A/B/C définies dans les en-têtes d’intrinsics de gcc et clang : typedef enum { _MM_TERNLOG_A = 0xF0, _MM_TERNLOG_B = 0xCC, _MM_TERNLOG_C = 0xAA } _MM_TERNLOG_ENUM;
    Avec MSVC, il suffit de les définir soi-même

    • Pour que cela ait l’air moins magique, on peut l’écrire en binaire : A = 0b11110000, B = 0b11001100, C = 0b10101010
    • Le manuel de l’Amiga recommande de normaliser en forme normale conjonctive

  • Rien qu’en lisant le titre, j’ai cru qu’il signifiait que cette instruction ne fonctionnait pas correctement. En réalité, l’article explique simplement son fonctionnement

    • Ici, j’ai compris « busted » comme le fait d’avoir pris les gens d’Intel en flagrant délit d’être des fans d’Amiga. Il semble qu’une nuance se soit perdue en passant du français, la langue maternelle de l’auteur, à l’anglais

  • Adolescent, je n’ai pas écrit « CRAP! » sur cette page du manuel matériel, mais je l’ai vraiment fixée très longtemps en essayant de comprendre
    Au final, comme presque tout le monde, j’ai cherché et utilisé BLTCON0 pour les Bobs et les simples copies, et j’ai fait comme si cette partie n’existait pas
    Cela dit, quelques années plus tard, j’ai eu A+ en logique mathématique à l’université ; ce traumatisme a donc peut-être aidé, au moins un peu

  • À propos du titre, « ternary logic » désigne généralement une logique à trois valeurs de vérité. Mais cet article traite d’une instruction de compilation qui gère toutes les portes logiques binaires à trois entrées

    • Le nom de l’instruction x86 est ternlog et l’intrinsic s’appelle aussi ternarylogic, donc même si c’est regrettable, le titre est approprié
      En plus, bitwise suffit déjà dans une certaine mesure à la distinguer de la « logique à trois valeurs », et ternary est très souvent utilisé pour signifier trois entrées. a ? b : c est aussi couramment appelé opérateur ternaire, et ternlog peut effectivement imiter cette opération ternaire ; l’article traite justement de cela
    • Ce n’est pas tant une « instruction de logique ternaire » qu’une « instruction logique ternaire »
    • Je ne vois pas bien ce que serait une logique à trois valeurs de vérité. Vous ne penseriez pas plutôt à trinary qu’à ternary ?
      Du point de vue de C++, JavaScript ou Python, l’usage le plus courant me semble être l’expression ternaire de la forme (a < b) ? 5 : 2. https://www.programiz.com/cpp-programming/ternary-operator
      Quoi qu’il en soit, l’hypothèse de départ n’a pas grande importance. Les mots et expressions ont souvent plusieurs sens, et ternary signifie composé de trois parties, ce qui convient ici aussi
    • Ici, ternary ne veut pas dire cela
      En C, + prend deux entrées, c’est donc un opérateur binaire, tandis que ?: prend trois entrées, c’est donc un opérateur ternaire. Comme c’est le seul en C, on l’appelle généralement « the ternary operator », mais il n’a rien de spécialement particulier par nature
      vpternlogd implémente tous les opérateurs ternaires bit à bit à trois entrées
    • Moi aussi, cette partie m’a dérouté. Cela dit, un nom comme « évalue une expression binaire à trois termes » serait moins concis

  • Je me demande si c’est similaire à la fonction BitBlt de Windows. Elle existe, il me semble, au moins depuis Windows 3.1, et le paramètre op détermine comment combiner source, destination et masque
    Je me souviens de noms de codes comme BLACKNESS, qui produit du noir indépendamment des entrées, ou COPY, qui copie la source vers la destination. BLACKNESS et WHITENESS avaient une résonance étrangement poétique
    D’après mon souvenir de Petzold, c’était implémenté en logiciel, mais lors de l’appel l’opcode était transformé en assembleur personnalisé à l’intérieur de la fonction ; c’était donc apparemment un rare cas de code automodifiant dans le système d’exploitation Windows

    • Exact. BitBlt utilisait à l’origine des « operation codes » 16 bits complexes qui stockaient l’opération binaire en notation polonaise inverse
      Plus tard, comme sur l’Amiga, un « operation index » a été ajouté pour mettre les mêmes informations dans un seul octet, ce qui est plus court et plus élégant. Aujourd’hui, chaque raster operation code contient à la fois l’operation index et l’operation code, ce qui rend l’encodage redondant. https://devblogs.microsoft.com/oldnewthing/20180528-00/?p=98...

  • C’est la même manière dont les FPGA implémentent des fonctions logiques arbitraires sous forme de tables de correspondance

    • Fondamentalement, CPU, GPU et FPGA convergent tous vers une même forme d’évolution, à la façon des crabes du calcul. Ils exposent les mêmes capacités avec des domaines d’optimisation différents
    • Toute logique peut être implémentée par de la mémoire, et toute mémoire peut être implémentée par une logique ayant une forme de boucle de rétroaction
      Mais en dehors d’usages spécialisés comme les FPGA ou l’instruction dont parle cet article, on ne fait généralement pas cela. Les registres rapides et la RAM statique sont parfois faits en logique, mais il est plus courant de les réaliser directement avec des transistors plutôt qu’avec des portes
    • La plupart le font, mais pas tous. Actel/Microsemi utilise un petit arbre de multiplexeurs et de portes
    • L’unité arithmétique et logique 74181 fait aussi cela

  • Si vous allez sur https://www.sandpile.org puis, dans la page des opcodes sur 3 octets https://www.sandpile.org/x86/opc_3.htm, recherchez VPTERNLOG, vous verrez aussi AVX512BITALG2, une variante avec masquage byte/word qu’Intel semble avoir planifiée par le passé
    La page renvoie aussi, depuis l’opérande Ib, à une page de tables de vérité ternaires couvrant les 256 cas possibles : https://www.sandpile.org/x86/ternlog.htm

  • Le choix de la fonction E2 comme exemple dans la documentation s’explique peut-être par le fait que, parmi les fonctions booléennes à trois entrées, c’est quasiment le mux le plus basique et standard : si B, alors A, sinon C
    C’est une fonction universelle, donc il n’est pas nécessaire d’être fan d’Amiga pour la choisir. Bien sûr, il se peut qu’ils l’aient vraiment été

  • Autre exemple d’opérations bit à bit encodées dans un entier : les codes ROP du GDI Win32 : https://learn.microsoft.com/en-us/windows/win32/gdi/ternary-...

  • Il n’y avait pas de manuel matériel Amiga officiel ; à la place, j’ai lu un livre intitulé « Mapping the Amiga ». Il expliquait la même chose de manière un peu plus verbeuse
    Je ne me souviens plus quels minterms j’avais utilisés à l’époque, mais je crois qu’avec ce livre j’avais fini par implémenter tant bien que mal des shadebobs, des bobs et du tracé de lignes 3D en XOR
    La page correspondante de Mapping the Amiga : https://archive.org/details/1993-thomson-randy-rhett-anderso...