เจาะลึกคำสั่งตรรกะบิตแบบสามตัวแปรของ AVX

 (arnaud-carre.github.io)
2 คะแนน โดย GN⁺ 2024-10-07 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • vpternlogd ของ AVX-512 คือคำสั่ง SIMD ที่เลือกและรันตรรกะ Boolean ระดับบิตแบบใดก็ได้ของอินพุตสามตัว ด้วย immediate 8 บิตในครั้งเดียว
  • แก่นสำคัญไม่ใช่การท่องจำสมการตรรกะที่ซับซ้อน แต่คือการมอง #imm8 เป็น ตารางค้นหา สำหรับ 8 กรณีของอินพุต A/B/C
  • blitter ของ Amiga ในปี 1985 ก็ใช้วิธีเดียวกันในการระบุการผสมตรรกะ โดยใช้แหล่งบิตแมปสามตัวและ minterm 8 บิต และ 0xE2 ก็ถูกใช้บ่อยกับ masked sprite
  • เมื่ออ่าน 8 บิตของคอลัมน์ผลลัพธ์จากล่างขึ้นบน ก็จะได้ค่า immediate ดังนั้นเงื่อนไขอย่าง “มีค่าเป็น 1 อยู่พอดีสองอินพุตจากสามอินพุต” ก็สร้างตรง ๆ เป็น 0x68 ได้
  • ตัวอย่าง vpternlogd ในเอกสารของ Intel และ 0xE2 ที่พบบ่อยใน demoscene ของ Amiga เชื่อมโยงกันพอดี แสดงให้เห็นว่าคำสั่ง SIMD สมัยใหม่และฮาร์ดแวร์กราฟิกย้อนยุคมีแนวคิดการออกแบบร่วมกัน

vpternlogd ของ AVX-512

  • vpternlogd เป็นคำสั่งตรรกะสามตัวแปรระดับบิตที่สะดุดตาในเอกสารนำเสนอการออกแบบ ISA ของ AVX-512
  • มันรับอินพุต A, B, C แล้วแสดงตรรกะ Boolean แบบใดก็ได้ด้วยคำสั่งเดียว
    • ตัวอย่าง: (NOT A) OR ((NOT B) XOR (C AND A))
  • อินพุตอาจเป็น รีจิสเตอร์ 512 บิต ทำให้สามารถใช้ตรรกะที่ซับซ้อนกับทั้ง 512 บิตพร้อมกันได้
  • แทนที่จะเพิ่มคำสั่งเฉพาะทางอย่าง foo_and_a_or_not_b ไปเรื่อย ๆ ก็ใช้คำสั่งยืดหยุ่นตัวเดียวร่วมกับ immediate 8 บิตเพื่อรองรับตรรกะได้หลายแบบ
VPTERNLOGD r0, r1, r3, #imm8
  • #imm8 ใช้กำหนดว่าจะทำฟังก์ชันตรรกะระดับบิตแบบใด
  • เอกสารจำนวนมากอธิบายเพียงว่า immediate นี้ “กำหนดฟังก์ชันไบนารีบางอย่าง” ทำให้ยากจะเข้าใจวิธีคำนวณจริงอย่างเป็นธรรมชาติ

Amiga blitter และ minterm

  • คอมพิวเตอร์ในยุค 1980 มักใช้ ชิปคัสตอม สำหรับงานกราฟิก
  • blitter ของ Commodore Amiga 500 สามารถย้ายกราฟิกแบบบิตแมปจากตำแหน่งหนึ่งไปยังอีกตำแหน่งหนึ่งพร้อมใช้การดำเนินการเชิงตรรกะได้
  • มันรองรับแหล่งบิตแมปได้สูงสุดสามแหล่ง และการดำเนินการเชิงตรรกะระหว่างแหล่งเหล่านี้จะถูกกำหนดด้วยค่า minterm แบบ 8 บิต
  • ในแง่ที่เลือกการผสมตรรกะด้วยแหล่งข้อมูลสามตัวและค่า 8 บิต มันจึงมีโครงสร้างแบบเดียวกับ vpternlogd
  • โปรแกรมเมอร์ Amiga จำนวนมากไม่ได้เข้าใจวิธีคำนวณ minterm โดยตรง แต่จะใช้ค่าที่พบบ่อยซ้ำ ๆ
    • ล้างบัฟเฟอร์ใช้ 0x00
    • วาด masked sprite ใช้ 0xE2
  • “Amiga Hardware Reference Manual” ปี 1989 อธิบายการคำนวณ minterm ด้วยสัญลักษณ์ที่ชวนสับสน จึงไม่ได้ช่วยผู้ทำเดโมในยุคนั้นมากนัก

คำนวณค่า 8 บิตแบบตารางค้นหา

  • #imm8 หรือ minterm ไม่จำเป็นต้องมองเป็นการผสมกันของโอเปอเรเตอร์ตรรกะ แต่สามารถมองเป็นตารางค้นหา 8 รายการได้
  • อินพุตสามตัว A, B, C ต่างมีค่าได้เป็น 0 หรือ 1 ดังนั้นจึงมีความเป็นไปได้ทั้งหมด 8 แบบ
  • เพียงกรอกผลลัพธ์ที่ต้องการลงในคอลัมน์ที่สี่โดยตรง
A B C ผลลัพธ์ที่ต้องการ
0 0 0 ?
0 0 1 ?
0 1 0 ?
0 1 1 ?
1 0 0 ?
1 0 1 ?
1 1 0 ?
1 1 1 ?
  • ตัวอย่างเช่น ถ้าต้องการให้ผลลัพธ์เป็น 1 เมื่อมีค่าเป็น 1 อยู่พอดีสองอินพุต จากสามอินพุต ก็กรอกค่าลงในคอลัมน์ที่สี่ตามเงื่อนไขนั้น
  • เมื่ออ่าน 8 บิตของคอลัมน์ผลลัพธ์ จากล่างขึ้นบน จะได้ 01101000 หรือ 0x68
  • ดังนั้นฟังก์ชัน 0x68 จะตั้งผลลัพธ์เป็น 1 เมื่อมีอินพุตสองตัวจากสามตัวเป็น 1 พอดี
  • ด้วยวิธีเดียวกันนี้ เราสามารถหาค่า #imm8 ที่ต้องใช้สำหรับฟังก์ชันตรรกะใด ๆ ระหว่างแหล่งข้อมูลสามตัวได้

0xE2 ของ masked sprite

  • หนึ่งในค่า minterm ที่พบบ่อยมากบน Amiga คือ 0xE2
  • ค่านี้มักใช้ตอนเรนเดอร์ masked 2D sprite
    • A: bitmap ของ sprite
    • B: mask ของ sprite
    • C: background
  • เงื่อนไขสามารถเขียนเป็นตรรกะของโปรแกรมแบบง่าย ๆ ได้ดังนี้
    • ถ้าพิกเซล mask B ถูกตั้งค่าไว้ ผลลัพธ์คือ sprite A
    • ถ้าพิกเซล mask B ไม่ได้ถูกตั้งค่าไว้ ผลลัพธ์คือ background C
A B C ผลลัพธ์ที่ต้องการ
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
  • เมื่ออ่านคอลัมน์ผลลัพธ์จากล่างขึ้นบน จะได้ 11100010 หรือ 0xE2
  • 0xE2 เป็นค่า minterm ที่พบได้บ่อยมากในวัฒนธรรม demoscene ของ Amiga

ความเชื่อมโยงที่บังเอิญกับเอกสารของ Intel

  • Intel 64 and IA-32 Architectures Software Developer’s Manual ของ Intel มีตัวอย่าง #imm8 ของ vpternlogd รวมอยู่ด้วย
  • ฟังก์ชันที่ผู้ใช้กำหนดได้มีทั้งหมด 256 แบบ และตัวอย่างในเอกสารก็เชื่อมโยงกับ 0xE2 ที่เคยใช้บ่อยกับ masked sprite บน Amiga
  • ข้อสังเกตที่เริ่มจาก งานนำเสนอการออกแบบ ISA ของ AVX-512 โดย Tom Forsyth นำไปสู่ประเด็นที่ว่า คำสั่ง SIMD สมัยใหม่กับชิป blitter ในปี 1985 ใช้โครงสร้างการเลือกตรรกะ 8 บิตแบบเดียวกัน

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-10-07
ความคิดเห็นบน Hacker News

  • มีวิธีง่าย ๆ ในการหา immediate value จากนิพจน์ที่ต้องการคำนวณ เช่น ถ้าต้องการคำนวณ (NOT A) OR ((NOT B) XOR (C AND A)) ก็เขียนได้เป็น ~_MM_TERNLOG_A | (~_MM_TERNLOG_B ^ (_MM_TERNLOG_C & _MM_TERNLOG_A))
    มันก็คือนิพจน์ที่ต้องการคำนวณตรง ๆ และจะถูก evaluate เป็น immediate value จากค่าคงที่ _MM_TERNLOG_A/B/C ที่นิยามไว้ใน intrinsic header ของ gcc และ clang: typedef enum { _MM_TERNLOG_A = 0xF0, _MM_TERNLOG_B = 0xCC, _MM_TERNLOG_C = 0xAA } _MM_TERNLOG_ENUM;
    ใน MSVC ก็นิยามเองได้

    • ถ้าไม่อยากให้ดูเหมือนเวทมนตร์ ก็เขียนเป็น เลขฐานสอง ได้: A = 0b11110000, B = 0b11001100, C = 0b10101010
    • คู่มือ Amiga แนะนำให้ทำ normalization เป็น รูปปกติผลคูณเชิงตรรกะ

  • เห็นแค่ชื่อเรื่องแล้วคิดว่าหมายถึงคำสั่งนี้ทำงานไม่ถูกต้อง แต่บทความจริง ๆ แค่อธิบาย วิธีการทำงาน ของมัน

    • เข้าใจว่า “busted” ในที่นี้หมายถึงจับได้ว่าคนของ Intel เป็น แฟน Amiga น่าจะมีอะไรบางอย่างหล่นหายไปตอนแปลจากภาษาฝรั่งเศสซึ่งเป็นภาษาแม่ของผู้เขียนมาเป็นภาษาอังกฤษ

  • ตอนเป็นวัยรุ่น ผมไม่ได้เขียนคำว่า “CRAP!” ลงบนหน้านั้นของคู่มือฮาร์ดแวร์ก็จริง แต่ผมนั่งจ้องมันอยู่นานมากเพื่อพยายามทำความเข้าใจ
    สุดท้ายก็เหมือนแทบทุกคน คือไปหา Bobs กับ BLTCON0 สำหรับการคัดลอกแบบง่าย ๆ มาใช้ แล้วทำเป็นไม่เห็นส่วนนั้น
    แต่หลายปีต่อมาผมได้ A+ วิชาตรรกศาสตร์เชิงคำนวณที่มหาวิทยาลัย ดังนั้นบาดแผลทางใจนั้นอาจช่วยได้อยู่บ้าง

  • ถ้าพูดถึงชื่อเรื่อง “ternary logic” ปกติหมายถึง ตรรกะที่มีค่าความจริงสามค่า แต่บทความนี้พูดถึงคำสั่งคอมไพเลอร์ที่จัดการเกตตรรกะไบนารีทั้งหมดที่รับอินพุตสามตัว

    • ชื่อคำสั่ง x86 คือ ternlog และ intrinsic ก็ชื่อ ternarylogic ดังนั้นถึงจะน่าเสียดาย แต่ชื่อเรื่องก็เหมาะสมแล้ว
      แถมคำว่า bitwise ก็ช่วยแยกจาก “ตรรกะสามค่า” ได้ในระดับหนึ่งอยู่แล้ว และ ternary ก็ถูกใช้บ่อยมากในความหมายว่าอินพุตสามตัวเช่นกัน a ? b : c ก็มักเรียกว่า ตัวดำเนินการแบบสามส่วน และจริง ๆ แล้ว ternlog ก็เลียนแบบการดำเนินการสามส่วนนั้นได้ ซึ่งบทความก็พูดถึงเรื่องนั้นโดยตรง
    • มันใกล้เคียงกับ “คำสั่งตรรกะที่เป็นแบบสามส่วน” มากกว่า “คำสั่งตรรกะสามค่า”
    • ไม่รู้ว่าตรรกะที่มีค่าความจริงสามค่าคืออะไร คิดว่าคุณอาจกำลังนึกถึง trinary ไม่ใช่ ternary หรือเปล่า
      จากมุมมองของ C++, JavaScript, Python การใช้ที่พบบ่อยที่สุดน่าจะเป็น นิพจน์สามส่วน รูปแบบ (a < b) ? 5 : 2 https://www.programiz.com/cpp-programming/ternary-operator
      อย่างไรก็ดี ไม่ว่าจะตั้งสมมติฐานแบบไหนก็ไม่ได้สำคัญมากนัก คำหรือวลีมักมีได้หลายความหมาย และ ternary หมายถึงประกอบด้วยสามส่วน จึงเข้ากับที่นี่ด้วย
    • ternary ในที่นี้ไม่ได้หมายถึงอย่างนั้น
      ใน C เครื่องหมาย + รับอินพุตสองตัว จึงเป็น ตัวดำเนินการทวิภาค ส่วน ?: รับอินพุตสามตัว จึงเป็นตัวดำเนินการสามส่วน เพียงแต่ใน C มันมีอยู่ตัวเดียว จึงมักถูกเรียกว่า “the ternary operator” เท่านั้น ไม่ได้มีอะไรพิเศษโดยเนื้อแท้
      vpternlogd implements ตัวดำเนินการสามส่วนระดับบิตทุกแบบที่รับอินพุตสามตัว
    • ผมก็สับสนตรงนี้เหมือนกัน แต่ชื่อแบบ “evaluate นิพจน์ไบนารีที่มีสามเทอม” ก็คงไม่กระชับเท่าไร

  • คิดว่ามันคล้ายกับฟังก์ชัน BitBlt ของ Windows หรือเปล่า อย่างน้อยน่าจะมีมาตั้งแต่ Windows 3.1 แล้ว โดยพารามิเตอร์ op ใช้กำหนดว่าจะผสม source, destination, mask อย่างไร
    จำได้ว่ามีชื่อโค้ดอย่าง BLACKNESS ที่ทำให้เป็นสีดำไม่ว่าอินพุตจะเป็นอะไร และ COPY ที่คัดลอก source ไปยัง destination BLACKNESS กับ WHITENESS ฟังดูเป็นกวีนิด ๆ อย่างไรไม่รู้
    จากที่จำได้จาก Petzold แม้มันจะ implement ด้วยซอฟต์แวร์ แต่ตอนเรียกใช้ opcode จะถูกแปลงเป็น assembly เฉพาะภายในฟังก์ชัน จึงเหมือนจะเป็นกรณีที่พบได้ยากของ self-modifying code ในระบบปฏิบัติการ Windows

    • ใช่แล้ว BitBlt เดิมใช้ “operation codes” แบบ 16 บิตที่ซับซ้อน ซึ่งเก็บการดำเนินการไบนารีในรูป สัญกรณ์โปแลนด์ย้อนกลับ
      ต่อมามีการเพิ่ม “operation index” ที่เก็บข้อมูลเดียวกันใน 1 ไบต์เหมือน Amiga ซึ่งสั้นกว่าและสวยงามกว่า ตอนนี้ raster operation code แต่ละตัวเก็บทั้ง operation index และ operation code ทำให้ encoding ซ้ำซ้อนกัน https://devblogs.microsoft.com/oldnewthing/20180528-00/?p=98...

  • เหมือนกับวิธีที่ FPGA implement ฟังก์ชันตรรกะตามอำเภอใจด้วย lookup table

    • โดยพื้นฐานแล้ว CPU, GPU, FPGA ต่างก็มาบรรจบกันเป็นรูปแบบวิวัฒนาการเดียวกันของการคำนวณ มีขอบเขตการ optimize ต่างกัน แต่ expose ความสามารถเดียวกัน
    • ตรรกะทั้งหมด implement ด้วยหน่วยความจำได้ และหน่วยความจำทั้งหมดก็ implement ด้วยตรรกะที่มีโครงสร้าง feedback บางรูปแบบได้
      เพียงแต่โดยทั่วไปจะไม่ทำแบบนั้น ยกเว้นงานเฉพาะทางอย่าง FPGA หรือคำสั่งในบทความนี้ รีจิสเตอร์ความเร็วสูงและ static RAM บางครั้งก็สร้างด้วยตรรกะ แต่การสร้างโดยตรงด้วยทรานซิสเตอร์พบได้บ่อยกว่าการสร้างด้วยเกต
    • ส่วนใหญ่ใช่ แต่ไม่ทั้งหมด Actel/Microsemi ใช้ มัลติเพล็กเซอร์ขนาดเล็กและต้นไม้ของเกต
    • หน่วยคำนวณและตรรกะ 74181 ก็ทำแบบนั้นเช่นกัน

  • ไปที่ https://www.sandpile.org แล้วหา VPTERNLOG ในหน้า opcode 3 ไบต์ https://www.sandpile.org/x86/opc_3.htm จะเห็น AVX512BITALG2 ซึ่งเป็น variant แบบ byte/word masking ที่ดูเหมือน Intel เคยวางแผนไว้ในอดีต
    นอกจากนี้จาก operand Ib ยังลิงก์ไปยังหน้าตารางตรรกะสามส่วนที่รวมทั้ง 256 กรณีไว้ https://www.sandpile.org/x86/ternlog.htm

  • ที่เอกสารเลือกฟังก์ชัน E2 เป็นตัวอย่าง อาจเพราะมันเป็น mux ที่แทบจะพื้นฐานและเป็นมาตรฐานที่สุดในบรรดาฟังก์ชันบูลีนสามอินพุต: ถ้า B ก็เป็น A ไม่เช่นนั้นเป็น C
    นี่เป็นฟังก์ชันสากล จึงไม่จำเป็นต้องเป็นแฟน Amiga ถึงจะเลือกใช้ได้ แน่นอนว่าจริง ๆ แล้วเขาอาจเป็นแฟนก็ได้

  • อีกตัวอย่างหนึ่งของการใส่การดำเนินการระดับบิตไว้ในจำนวนเต็มคือ ROP code ของ GDI ใน Win32: https://learn.microsoft.com/en-us/windows/win32/gdi/ternary-...

  • ไม่มีคู่มือฮาร์ดแวร์ Amiga อย่างเป็นทางการ เลยอ่านหนังสือ “Mapping the Amiga” แทน ซึ่งอธิบายเนื้อหาเดียวกันแบบยืดยาวกว่าเล็กน้อย
    จำไม่ได้แล้วว่าตอนนั้นใช้มินเทอมไหน แต่คิดว่าหลังอ่านหนังสือเล่มนี้ก็พอจะ implement สิ่งต่าง ๆ อย่าง shadebobs, bobs, การวาดเส้น 3D แบบ XOR ได้อย่างไรก็ไม่รู้
    หน้าที่เกี่ยวข้องใน Mapping the Amiga: https://archive.org/details/1993-thomson-randy-rhett-anderso...