AVX-Bitlogik mit ternären Instruktionen verstehen

 (arnaud-carre.github.io)
2 Punkte von GN⁺ 2024-10-07 | 1 Kommentare | Auf WhatsApp teilen
  • vpternlogd in AVX-512 ist eine SIMD-Instruktion, die beliebige bitweise Boolesche Logik mit drei Eingaben in einem Schritt ausführt, ausgewählt per 8-Bit-Immediate
  • Der Kern ist nicht, sich komplizierte Logikformeln zu merken, sondern #imm8 als Lookup-Tabelle für die 8 möglichen Fälle der drei Eingaben A/B/C zu betrachten
  • Schon der Amiga-Blitter von 1985 spezifizierte auf dieselbe Weise logische Kombinationen mit drei Bitmap-Quellen und einem 8-Bit-Minterm; für masked Sprites wurde oft 0xE2 verwendet
  • Liest man die 8 Bits der Ergebnisspalte von unten nach oben, erhält man den Immediate-Wert, sodass sich auch Bedingungen wie „genau zwei der drei Eingaben sind 1“ direkt als 0x68 konstruieren lassen
  • Das vpternlogd-Beispiel aus der Intel-Dokumentation und das in der Amiga-Demoszene verbreitete 0xE2 treffen hier zusammen und zeigen, dass moderne SIMD-Instruktionen und Retro-Grafikhardware dieselbe Designidee teilen

vpternlogd in AVX-512

  • vpternlogd ist eine bitweise ternäre Logik-Instruktion, die in den Präsentationsunterlagen zum AVX-512-ISA-Design auffällt
  • Sie nimmt drei Eingaben A, B und C an und kann beliebige Boolesche Logik in einer einzigen Instruktion ausdrücken
    • Beispiel: (NOT A) OR ((NOT B) XOR (C AND A))
  • Die Eingaben können 512-Bit-Register sein, sodass sich komplexe Logik gleichzeitig auf alle 512 Bit anwenden lässt
  • Statt fortlaufend Spezialinstruktionen wie foo_and_a_or_not_b hinzuzufügen, verarbeitet eine flexible Instruktion zusammen mit einem 8-Bit-Immediate viele verschiedene Logikfunktionen
VPTERNLOGD r0, r1, r3, #imm8
  • #imm8 bestimmt, welche bitlogische Funktion ausgeführt wird
  • Viele Dokumente erklären nur, dass der Immediate „eine bestimmte Binärfunktion festlegt“, wodurch die eigentliche Berechnung schwer intuitiv zu erfassen ist

Amiga-Blitter und Minterm

  • In den 1980er Jahren war es üblich, für die Grafikverarbeitung Custom Chips einzusetzen
  • Der Blitter des Commodore Amiga 500 verschob Bitmap-Grafiken von einer Position zur anderen und konnte dabei logische Operationen anwenden
  • Er konnte bis zu drei Bitmap-Quellen verarbeiten, und die logische Verknüpfung zwischen ihnen wurde durch einen 8-Bit-Wert, den Minterm, festgelegt
  • Darin ähnelt seine Struktur vpternlogd: Drei Quellen plus ein 8-Bit-Wert wählen eine logische Kombination aus
  • Viele Amiga-Programmierer verstanden die Berechnung von Minterms nicht direkt, sondern verwendeten häufig gebrauchte Werte wieder
    • Zum Löschen eines Puffers: 0x00
    • Zum Zeichnen eines masked Sprite: 0xE2
  • Das „Amiga Hardware Reference Manual“ von 1989 erklärte die Minterm-Berechnung mit verwirrender Symbolik und war für damalige Demo-Programmierer wenig hilfreich

Den 8-Bit-Wert als Lookup-Tabelle berechnen

  • #imm8 beziehungsweise der Minterm lässt sich nicht als Kombination von Logikoperatoren, sondern als Lookup-Tabelle mit 8 Einträgen verstehen
  • Da die drei Eingaben A, B und C jeweils 0 oder 1 sein können, gibt es 8 mögliche Kombinationen
  • Man muss nur das gewünschte Ergebnis direkt in die vierte Spalte eintragen
A B C Gewünschtes Ergebnis
0 0 0 ?
0 0 1 ?
0 1 0 ?
0 1 1 ?
1 0 0 ?
1 0 1 ?
1 1 0 ?
1 1 1 ?
  • Möchte man zum Beispiel genau dann 1 als Ergebnis erhalten, wenn von den drei Eingaben genau zwei 1 sind, trägt man in die vierte Spalte entsprechend passende Werte ein
  • Liest man die 8 Bits dieser Ergebnisspalte von unten nach oben, erhält man 01101000, also 0x68
  • Die Funktion 0x68 setzt das Ergebnis also genau dann auf 1, wenn zwei der drei Eingaben 1 sind
  • Auf dieselbe Weise lässt sich der benötigte #imm8-Wert für jede beliebige logische Funktion zwischen drei Quellen bestimmen

0xE2 für masked Sprites

  • Einer der auf dem Amiga besonders häufig verwendeten Minterm-Werte ist 0xE2
  • Dieser Wert wird oft beim Rendern eines masked 2D-Sprite verwendet
    • A: Sprite-Bitmap
    • B: Sprite-Maske
    • C: Hintergrund
  • Die Bedingung lässt sich als einfache Programmlogik ausdrücken
    • Wenn das Maskenpixel B gesetzt ist, ist das Ergebnis Sprite A
    • Wenn das Maskenpixel B nicht gesetzt ist, ist das Ergebnis Hintergrund C
A B C Gewünschtes Ergebnis
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
  • Liest man die Ergebnisspalte von unten nach oben, erhält man 11100010, also 0xE2
  • 0xE2 ist in der Amiga-Demoszene ein sehr verbreiteter Minterm-Wert

Zufällige Verbindung zur Intel-Dokumentation

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-10-07
Hacker-News-Kommentare

  • Es gibt eine einfache Möglichkeit, den Immediate-Wert aus dem Ausdruck zu erhalten, den man berechnen will. Wenn man zum Beispiel (NOT A) OR ((NOT B) XOR (C AND A)) berechnen möchte, kann man das so schreiben: ~_MM_TERNLOG_A | (~_MM_TERNLOG_B ^ (_MM_TERNLOG_C & _MM_TERNLOG_A))
    Das ist buchstäblich der Ausdruck, den man berechnen will, und er wird aus den in den Intrinsic-Headern von gcc und clang definierten Konstanten _MM_TERNLOG_A/B/C zum Immediate-Wert ausgewertet: typedef enum { _MM_TERNLOG_A = 0xF0, _MM_TERNLOG_B = 0xCC, _MM_TERNLOG_C = 0xAA } _MM_TERNLOG_ENUM;
    In MSVC kann man sie einfach selbst definieren.

    • Damit es weniger magisch wirkt, schreibt man es in Binärschreibweise: A = 0b11110000, B = 0b11001100, C = 0b10101010
    • Das Amiga-Handbuch empfiehlt, in die disjunktive Normalform zu normalisieren.

  • Nur vom Titel her dachte ich, die Anweisung funktioniere nicht richtig. Der eigentliche Artikel erklärt einfach nur ihre Funktionsweise.

    • Ich habe „busted“ hier so verstanden, dass man Intel-Leute als Amiga-Fans entlarvt hat. Beim Übertragen aus der Muttersprache des Autors, Französisch, ins Englische scheint etwas verloren gegangen zu sein.

  • Mein Teenager-Ich hat auf diese Seite im Hardware-Handbuch zwar nicht „CRAP!“ geschrieben, aber ich habe wirklich lange daraufgestarrt, um sie zu verstehen.
    Am Ende habe ich, wie fast alle, die Bobs und BLTCON0 für einfaches Kopieren nachgeschlagen und so getan, als hätte ich diesen Teil nicht gesehen.
    Trotzdem habe ich ein paar Jahre später an der Uni in mathematischer Logik eine 1+ bekommen; vielleicht hat dieses Trauma also bis zu einem gewissen Grad geholfen.

  • Zum Titel: „ternary logic“ bezeichnet normalerweise Logik mit drei Wahrheitswerten. Dieser Artikel behandelt aber eine Compiler-Instruktion für beliebige binäre Logikgatter mit drei Eingaben.

    • Der x86-Instruktionsname ist ternlog, und das Intrinsic heißt ebenfalls ternarylogic; daher ist der Titel, wenn auch etwas unglücklich, passend.
      Außerdem grenzt bitwise es bereits ein Stück weit von „dreiwertiger Logik“ ab, und ternary wird sehr häufig auch im Sinn von drei Eingaben verwendet. a ? b : c nennt man ebenfalls oft den ternären Operator, und tatsächlich kann ternlog diese ternäre Operation nachbilden; genau darum geht es im Artikel auch.
    • Es ist weniger eine „ternäre Logik-Instruktion“ als eine „ternäre logische Instruktion“.
    • Ich weiß nicht, was Logik mit drei Wahrheitswerten sein soll. Vielleicht meinst du eher trinary statt ternary.
      Aus Sicht von C++, JavaScript und Python scheint eine ternäre Expression der Form (a < b) ? 5 : 2 die häufigste Verwendung zu sein. https://www.programiz.com/cpp-programming/ternary-operator
      Wie auch immer, es ist nicht besonders wichtig, welche Annahme man trifft. Wörter und Wendungen haben nun einmal mehrere Bedeutungen, und ternary bedeutet aus drei Teilen bestehend, also passt es auch hier.
    • ternary bedeutet hier nicht das.
      In C ist + ein binärer Operator, weil er zwei Eingaben nimmt, und ?: ein ternärer Operator, weil er drei Eingaben nimmt. Er wird gewöhnlich nur deshalb „the ternary operator“ genannt, weil er in C der einzige ist; grundsätzlich ist daran nichts Besonderes.
      vpternlogd implementiert jeden bitweisen ternären Operator mit drei Eingaben.
    • Mich hat dieser Teil ebenfalls verwirrt. Allerdings wäre ein Name wie „wertet einen binären Ausdruck mit drei Termen aus“ weniger prägnant.

  • Ich fragte mich, ob das der Windows-Funktion BitBlt ähnelt. Die gab es, glaube ich, mindestens seit Windows 3.1; über den Parameter op wird festgelegt, wie Quelle, Ziel und Maske kombiniert werden.
    Ich erinnere mich an Codenamen wie BLACKNESS, das unabhängig von den Eingaben Schwarz erzeugt, und COPY, das die Quelle ins Ziel kopiert. BLACKNESS und WHITENESS hatten irgendwie einen poetischen Klang.
    Aus Petzold habe ich in Erinnerung, dass es zwar in Software implementiert war, der Opcode beim Aufruf aber innerhalb der Funktion in maßgeschneiderten Assembler übersetzt wurde; das wirkte wie ein seltener Fall von selbstmodifizierendem Code im Windows-Betriebssystem.

    • Genau. BitBlt verwendete ursprünglich komplexe 16-Bit-„operation codes“, die binäre Operationen in umgekehrter polnischer Notation speicherten.
      Später kam, ähnlich wie beim Amiga, ein „operation index“ hinzu, der dieselben Informationen in 1 Byte fasste; kürzer und eleganter. Heute enthält jeder Raster-Operation-Code sowohl den operation index als auch den operation code, sodass die Codierung redundant ist. https://devblogs.microsoft.com/oldnewthing/20180528-00/?p=98...

  • Das ist dasselbe Prinzip, nach dem ein FPGA beliebige logische Funktionen als Lookup-Tabelle implementiert.

    • Im Grunde konvergieren CPU, GPU und FPGA alle zu krebsähnlichen Evolutionsformen des Rechnens. Sie haben unterschiedliche Optimierungsbereiche und legen dieselben Fähigkeiten frei.
    • Jede Logik lässt sich mit Speicher implementieren, und jeder Speicher lässt sich mit Logik implementieren, die irgendeine Form von Rückkopplung hat.
      Abgesehen von Spezialzwecken wie FPGAs oder der Instruktion in diesem Artikel macht man das normalerweise aber nicht. Schnelle Register und statisches RAM werden bisweilen aus Logik gebaut, häufiger ist es jedoch, sie direkt aus Transistoren statt aus Gates aufzubauen.
    • Meistens, aber nicht immer. Actel/Microsemi verwendet kleine Multiplexer- und Gate-Bäume.
    • Die arithmetisch-logische Einheit 74181 macht das auch so.

  • Wenn man auf https://www.sandpile.org geht und auf der Seite mit 3-Byte-Opcodes https://www.sandpile.org/x86/opc_3.htm nach VPTERNLOG sucht, sieht man auch AVX512BITALG2, offenbar von Intel früher geplante Varianten mit Byte-/Word-Masking.
    Außerdem wird von dort auf eine Seite mit der ternären Wahrheitstabelle für alle 256 Fälle im Operanden Ib verlinkt: https://www.sandpile.org/x86/ternlog.htm

  • Dass in der Dokumentation die Funktion E2 als Beispiel gewählt wurde, könnte daran liegen, dass sie unter den booleschen Funktionen mit drei Eingaben so ziemlich der grundlegendste und standardmäßigste Mux ist: wenn B, dann A, sonst C.
    Das ist eine universelle Funktion, man muss also kein Amiga-Fan sein, um sie auszuwählen. Natürlich könnte man trotzdem einer gewesen sein.

  • Ein weiteres Beispiel dafür, bitweise Operationen in Integern zu kodieren, sind die GDI-ROP-Codes von Win32: https://learn.microsoft.com/en-us/windows/win32/gdi/ternary-...

  • Das offizielle Amiga-Hardwarehandbuch hatte ich nicht; stattdessen habe ich das Buch „Mapping the Amiga“ gelesen. Es erklärte dasselbe etwas ausführlicher.
    Ich weiß nicht mehr, welche Minterme damals verwendet wurden, aber mithilfe dieses Buches habe ich es irgendwie geschafft, Dinge wie shadebobs, bobs und XOR-3D-Linienzeichnen zu implementieren.
    Die entsprechende Seite aus Mapping the Amiga: https://archive.org/details/1993-thomson-randy-rhett-anderso...