AVX bitwise ternary instruction को समझना

 (arnaud-carre.github.io)
2 पॉइंट द्वारा GN⁺ 2024-10-07 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • AVX-512 का vpternlogd एक SIMD instruction है जो तीन inputs पर मनचाही bitwise Boolean logic को 8-bit immediate value चुनकर एक ही बार में execute करता है
  • इसका मूल विचार जटिल logic expressions याद रखना नहीं, बल्कि #imm8 को तीन inputs A/B/C के 8 possible cases के लिए एक lookup table की तरह देखना है
  • 1985 के Amiga blitter में भी तीन bitmap sources और 8-bit minterm के जरिए इसी तरह logic combinations तय किए जाते थे, और masked sprite के लिए 0xE2 अक्सर इस्तेमाल होता था
  • result column के 8 bits को नीचे से ऊपर पढ़ने पर immediate value बनती है, इसलिए “तीन inputs में से ठीक दो ही 1 हों” जैसी condition भी सीधे 0x68 के रूप में बनाई जा सकती है
  • Intel docs में दिया गया vpternlogd example और Amiga demoscene का आम 0xE2 एक-दूसरे से जुड़ते हैं, और दिखाते हैं कि modern SIMD instructions और retro graphics hardware में एक जैसी design sense मिलती है

AVX-512 का vpternlogd

  • vpternlogd AVX-512 ISA design announcement material में नज़र आने वाला एक उल्लेखनीय bitwise ternary logic instruction है
  • यह तीन inputs A, B, C लेकर किसी भी Boolean logic को एक instruction में व्यक्त कर सकता है
    • उदाहरण: (NOT A) OR ((NOT B) XOR (C AND A))
  • inputs 512-bit registers हो सकते हैं, इसलिए complex logic को पूरे 512 bits पर एक साथ apply किया जा सकता है
  • foo_and_a_or_not_b जैसे dedicated instructions बार-बार जोड़ने के बजाय, एक flexible instruction और 8-bit immediate value से कई तरह की logic संभाली जाती है
VPTERNLOGD r0, r1, r3, #imm8
  • #imm8 तय करता है कि कौन-सा bitwise logic function चलाया जाएगा
  • कई documents सिर्फ इतना बताते हैं कि immediate value “किसी specific binary function को तय करती है”, इसलिए असली calculation method को सहज रूप से समझना कठिन हो जाता है

Amiga blitter और minterm

  • 1980s के computers में graphics processing के लिए custom chips का इस्तेमाल आम था
  • Commodore Amiga 500 का blitter bitmap graphics को एक जगह से दूसरी जगह ले जाते समय logic operations apply करता था
  • यह अधिकतम तीन bitmap sources को संभालता था, और उनके बीच की logic operation 8-bit value minterm से तय की जाती थी
  • तीन sources और 8-bit value से logic combination चुनने के लिहाज़ से इसकी संरचना vpternlogd जैसी ही है
  • कई Amiga programmers minterm calculation को सीधे समझने के बजाय अक्सर इस्तेमाल होने वाली values दोबारा उपयोग करते थे
    • buffer साफ़ करने के लिए 0x00
    • masked sprite draw करने के लिए 0xE2
  • 1989 की “Amiga Hardware Reference Manual” ने minterm calculation को उलझे हुए symbols से समझाया था, इसलिए उस समय demo बनाने वालों के लिए यह ज़्यादा मददगार नहीं थी

8-bit value को lookup table की तरह निकालना

  • #imm8 या minterm को logic operators के combination की तरह नहीं, बल्कि 8 entries वाली lookup table की तरह देखा जा सकता है
  • तीन inputs A, B, C में से हर एक 0 या 1 हो सकता है, इसलिए कुल 8 possible combinations होते हैं
  • आपको बस चौथे column में चाहा गया result सीधे भरना है
A B C वांछित result
0 0 0 ?
0 0 1 ?
0 1 0 ?
0 1 1 ?
1 0 0 ?
1 0 1 ?
1 1 0 ?
1 1 1 ?
  • उदाहरण के लिए, अगर आप चाहते हैं कि तीन inputs में ठीक दो ही 1 होने पर result 1 बने, तो चौथे column में उसी condition के मुताबिक values भरें
  • फिर उस result column के 8 bits को नीचे से ऊपर पढ़ने पर 01101000, यानी 0x68 मिलता है
  • इसलिए 0x68 function तीन inputs में ठीक दो inputs के 1 होने पर result को 1 सेट करता है
  • इसी तरीके से तीन sources के बीच किसी भी logic function के लिए ज़रूरी #imm8 value निकाली जा सकती है

masked sprite का 0xE2

  • Amiga में बहुत आम minterm values में से एक 0xE2 है
  • यह value masked 2D sprite render करते समय अक्सर इस्तेमाल होती है
    • A: sprite bitmap
    • B: sprite mask
    • C: background
  • इस condition को एक सरल program logic की तरह व्यक्त किया जा सकता है
    • अगर mask pixel B set है, तो result sprite A होगा
    • अगर mask pixel B set नहीं है, तो result background C होगा
A B C वांछित result
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
  • result column को नीचे से ऊपर पढ़ने पर 11100010, यानी 0xE2 मिलता है
  • 0xE2 Amiga demoscene culture में बहुत आम minterm value है

Intel docs से एक दिलचस्प जुड़ाव

  • Intel की Intel 64 and IA-32 Architectures Software Developer’s Manual में vpternlogd के #imm8 examples शामिल हैं
  • कुल 256 possible user functions हैं, और document का example Amiga में masked sprite के लिए आम 0xE2 से जुड़ता है
  • Tom Forsyth की AVX-512 ISA design presentation से शुरू हुआ यह observation इस निष्कर्ष तक पहुँचता है कि modern SIMD instructions और 1985 के blitter chip, दोनों 8-bit logic selection की एक जैसी संरचना साझा करते हैं

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-10-07
Hacker News टिप्पणियाँ

  • जिस expression की गणना करनी है, उससे immediate value निकालने का एक आसान तरीका है। उदाहरण के लिए, अगर आप (NOT A) OR ((NOT B) XOR (C AND A)) निकालना चाहते हैं, तो इसे ~_MM_TERNLOG_A | (~_MM_TERNLOG_B ^ (_MM_TERNLOG_C & _MM_TERNLOG_A)) की तरह लिख सकते हैं
    यह शाब्दिक रूप से वही expression है जिसकी गणना करनी है, और gcc तथा clang के intrinsic headers में परिभाषित _MM_TERNLOG_A/B/C constants से immediate value के रूप में evaluate हो जाता है: typedef enum { _MM_TERNLOG_A = 0xF0, _MM_TERNLOG_B = 0xCC, _MM_TERNLOG_C = 0xAA } _MM_TERNLOG_ENUM;
    MSVC में इसे सीधे define किया जा सकता है

    • अगर इसे जादुई न दिखाना हो, तो binary में लिख सकते हैं: A = 0b11110000, B = 0b11001100, C = 0b10101010
    • Amiga manual इसे sum-of-products canonical form में normalize करने की सलाह देता है

  • सिर्फ शीर्षक देखकर मुझे लगा था कि इसका मतलब यह है कि यह instruction ठीक से काम नहीं करता। असली लेख तो बस इसके काम करने के तरीके को समझाता है

    • यहाँ “busted” का मतलब मैंने यह समझा कि Intel वाले लोग Amiga fans हैं, यह पकड़ लिया गया। लगता है लेखक की मातृभाषा फ़्रेंच से अंग्रेज़ी में आते हुए कुछ nuance छूट गया है

  • अपनी किशोरावस्था में मैंने hardware manual के उस पेज पर “CRAP!” तो नहीं लिखा था, लेकिन उसे समझने की कोशिश में बहुत देर तक घूरता रहा था
    आख़िर में, लगभग सभी की तरह, मैंने Bobs और साधारण copy operations के लिए BLTCON0 lookup करके इस्तेमाल किया, और उस हिस्से को अनदेखा कर दिया
    फिर भी कुछ साल बाद विश्वविद्यालय में computational logic में A+ मिला, तो शायद उस trauma ने कुछ मदद की होगी

  • शीर्षक की बात करें तो, “ternary logic” का मतलब आम तौर पर तीन truth values वाली logic होता है। लेकिन यह लेख ऐसे compiler instruction पर है जो तीन inputs लेने वाले सभी binary logic gates को संभालता है

    • x86 instruction का नाम ternlog है और intrinsic भी ternarylogic है, इसलिए थोड़ी असहजता के बावजूद शीर्षक उचित है
      ऊपर से bitwise पहले ही कुछ हद तक इसे “three-valued logic” से अलग करता है, और ternary का इस्तेमाल “three-input” के अर्थ में भी बहुत आम है। a ? b : c को भी अक्सर ternary operator कहा जाता है, और वास्तव में ternlog उस ternary operation की नकल कर सकता है; लेख भी उसी पर बात करता है
    • यह “ternary logic instruction” से ज़्यादा “ternary logical instruction” जैसा है
    • मुझे समझ नहीं आता कि तीन truth values वाली logic क्या है। शायद आपका मतलब ternary नहीं बल्कि trinary था
      C++, JavaScript और Python के नज़रिए से (a < b) ? 5 : 2 जैसी ternary expression ही सबसे सामान्य usage लगती है। https://www.programiz.com/cpp-programming/ternary-operator
      खैर, कोई भी धारणा लें, बहुत फ़र्क नहीं पड़ता। शब्दों और वाक्यांशों के कई अर्थ होते हैं, और ternary का अर्थ तीन भागों से बना हुआ भी है, इसलिए यहाँ भी यह फिट बैठता है
    • यहाँ ternary का वही मतलब नहीं है
      C में + दो inputs लेता है, इसलिए वह binary operator है, और ?: तीन inputs लेता है, इसलिए वह ternary operator है। C में वह अकेला है, इसलिए आम तौर पर उसे “the ternary operator” कहा जाता है, पर अपने स्वभाव में वह कोई विशेष अपवाद नहीं है
      vpternlogd तीन inputs लेने वाले सभी bitwise ternary operators को implement करता है
    • यह हिस्सा मुझे भी उलझाने वाला लगा। हालाँकि “तीन terms वाले binary expression का evaluation” जैसा नाम कम संक्षिप्त होता

  • मुझे लगा यह शायद Windows के BitBlt function जैसा कुछ है। कम से कम Windows 3.1 के समय से तो था ही, और op parameter से यह तय होता था कि source, destination, mask को कैसे combine करना है
    मुझे याद है कि ऐसे code names थे जैसे input से परे काला बनाने वाला BLACKNESS, या source को destination पर copy करने वाला COPY। BLACKNESS और WHITENESS में किसी तरह की काव्यात्मक गूँज थी
    Petzold में पढ़ा था कि यह software में implement था, लेकिन call के समय opcode function के अंदर custom assembly में translate हो जाता था, इसलिए Windows OS में self-modifying code का एक दुर्लभ उदाहरण था

    • सही। BitBlt मूल रूप से binary operations को reverse Polish notation में store करने वाले जटिल 16-bit “operation codes” इस्तेमाल करता था
      बाद में Amiga की तरह उसी जानकारी को 1 byte में रखने वाला “operation index” जोड़ा गया, जो छोटा और अधिक सुघड़ है। अब हर raster operation code में operation index और operation code दोनों ही भरे होते हैं, इसलिए encoding दोहराव वाली हो गई है। https://devblogs.microsoft.com/oldnewthing/20180528-00/?p=98...

  • यह वैसा ही है जैसे FPGA किसी मनचाहे logic function को lookup table के रूप में implement करता है

    • मूल रूप से CPU, GPU और FPGA सभी computation के एक जैसे evolutionary form पर converge करते हैं। इनके optimization क्षेत्र अलग हैं, लेकिन ये समान क्षमताएँ expose करते हैं
    • सारी logic को memory से implement किया जा सकता है, और सारी memory को किसी न किसी प्रकार के feedback arrangement वाली logic से implement किया जा सकता है
      बस FPGA या इस लेख की instruction जैसी special-purpose स्थितियों को छोड़ दें, तो आम तौर पर ऐसा नहीं किया जाता। high-speed registers और static RAM कभी-कभी logic से बनाए जाते हैं, लेकिन gates की बजाय सीधे transistors से बनाना ज़्यादा आम है
    • ज़्यादातर मामलों में हाँ, लेकिन पूरी तरह नहीं। Actel/Microsemi छोटे multiplexers और gate trees का उपयोग करते हैं
    • 74181 arithmetic logic unit भी ऐसा ही करता है

  • https://www.sandpile.org पर जाएँ और 3-byte opcode पेज https://www.sandpile.org/x86/opc_3.htm में VPTERNLOG खोजें, तो आपको AVX512BITALG2 भी दिखेगा, जो शायद Intel द्वारा पहले कभी योजनाबद्ध byte/word masking variant था
    वहाँ से Ib operand में मौजूद सभी 256 cases वाली ternary logic table के पेज https://www.sandpile.org/x86/ternlog.htm का लिंक भी मिलता है

  • documentation example में E2 function शायद इसलिए चुना गया, क्योंकि तीन-input boolean functions में यह लगभग सबसे बुनियादी और मानक mux है: B हो तो A, नहीं तो C
    यह एक universal function है, इसलिए इसे चुनने के लिए Amiga fan होना ज़रूरी नहीं। हालाँकि हो सकता है वे सचमुच fan रहे हों

  • integer में bitwise operations भरने का एक और उदाहरण Win32 के GDI ROP codes हैं: https://learn.microsoft.com/en-us/windows/win32/gdi/ternary-...

  • आधिकारिक Amiga hardware manual तो नहीं था, उसकी जगह मैंने “Mapping the Amiga” किताब देखी थी। उसमें वही बात थोड़ी ज़्यादा विस्तार से समझाई गई थी
    उस समय कौन-से minterms इस्तेमाल किए थे, यह याद नहीं, लेकिन लगता है इसी किताब को देखकर मैंने किसी तरह shadebobs, bobs, XOR 3D line drawing जैसी चीज़ें implement की थीं
    Mapping the Amiga का संबंधित पेज: https://archive.org/details/1993-thomson-randy-rhett-anderso...