แนะนำ HN: การคูณเมทริกซ์ที่ลดจำนวนครั้งของการคูณลงครึ่งหนึ่ง

 (github.com/trevorpogue)
3 คะแนน โดย GN⁺ 2024-03-17 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • ที่เก็บนี้เป็นซอร์สโค้ดสำหรับตรวจสอบสถาปัตยกรรม systolic array ที่คำนวณผลลัพธ์การคูณเมทริกซ์แบบเดียวกันได้โดยใช้ทรัพยากรฮาร์ดแวร์หรือเวลาในการรันน้อยลง ใน GEMM และตัวเร่งฮาร์ดแวร์ดีปเลิร์นนิง
  • วิธีที่เสนอเปลี่ยนการคูณเมทริกซ์บางส่วนให้เป็น การบวกแบบบิตต่ำ ที่มีต้นทุนถูกกว่า โดยมีเป้าหมายเพื่อลดจำนวน multiplier ที่ต้องใช้สำหรับประสิทธิภาพเท่าเดิมลงครึ่งหนึ่ง หรือเพิ่มประสิทธิภาพต่อหน่วย MAC
  • ผลลัพธ์ที่ได้คือ เร่ง CNN inference ได้สูงสุด 3×, มี throughput การคูณต่อ multiplier/clock มากกว่า 2× พร้อมทั้งใช้พื้นที่น้อยและทำงานที่ความถี่สัญญาณนาฬิกาสูง เมื่อเทียบกับตัวเร่งสมัยใหม่บนแพลตฟอร์มคอมพิวต์ใกล้เคียงกัน
  • ขอบเขตการใช้งานครอบคลุม dense matrix multiplication และงานที่พึ่งพามันเป็นหลัก เช่น fully-connected layer, CNN, RNN และ attention layer/transformer model โดยส่วนใหญ่ให้เอาต์พุตเหมือนวิธีเดิมในงาน fixed-point และ quantized inference
  • สถาปัตยกรรมถูกออกแบบให้คงฟังก์ชันและอินเทอร์เฟซแบบเดียวกับ systolic array เดิม จึงสามารถผสานเข้ากับระบบตัวเร่งเดิมได้ด้วยการแทนที่ MXU โดยไม่ต้องมีขั้นตอน pre-processing หรือ post-processing เพิ่มเติม

เป้าหมายและผลงานของโครงการ

  • Algebraic Enhancements for GEMM & AI Accelerators รวบรวมซอร์สโค้ดของระบบ GEMM และตัวเร่งฮาร์ดแวร์ดีปเลิร์นนิง
  • ระบบนี้ใช้เพื่อตรวจสอบสถาปัตยกรรม systolic array ที่นำอัลกอริทึมการคูณเมทริกซ์แบบมีประสิทธิภาพซึ่งถูกเสนอไว้หรือยังไม่ได้ถูกสำรวจมากพอ มาทำเป็นฮาร์ดแวร์
  • เป้าหมายคือคำนวณเอาต์พุตแบบเดียวกันโดยใช้ทรัพยากรฮาร์ดแวร์น้อยลงหรือใช้เวลารันสั้นลง
  • ประสิทธิภาพที่รายงานมีดังนี้
    • CNN inference เร็วขึ้นสูงสุด 3× เมื่อเทียบกับตัวเร่งรุ่นใหม่บนแพลตฟอร์มคอมพิวต์ประเภทเดียวกัน
    • mults/multiplier/clock cycle มากกว่า 2× ซึ่งเกินขีดจำกัดแบบดั้งเดิมที่ 1
    • ใช้พื้นที่น้อยและมีความถี่สัญญาณนาฬิกาสูง

สถาปัตยกรรมที่ตรวจสอบแล้วในงานวิจัยและวิทยานิพนธ์ปริญญาเอก

  • Fast Inner-Product Algorithms and Architectures for Deep Neural Network Accelerators
    • ลดจำนวน multiplier ที่ต้องใช้ลงครึ่งหนึ่ง เพื่อให้ได้ประสิทธิภาพเท่าเดิมในงานคูณเมทริกซ์และสถาปัตยกรรมฮาร์ดแวร์ดีปเลิร์นนิง
    • อัลกอริทึม inner-product แบบทดแทนสลับการคูณครึ่งหนึ่งไปเป็นการบวกแบบบิตต่ำที่มีต้นทุนถูกกว่า
    • systolic array ที่เสนอสามารถนำไปเสียบแทนในระบบ systolic array เดิมได้ และเพิ่มประสิทธิภาพต่อหน่วย MAC ได้ 2 เท่า โดยไม่ต้องเปลี่ยนฟังก์ชันหรือดีไซน์ส่วนอื่นของระบบ
    • ฉบับเต็มแบบเปิดเผย: https://arxiv.org/abs/2311.12224
  • Karatsuba Matrix Multiplication and its Efficient Custom Hardware Implementations
    • เสนอ KMM ซึ่งขยาย Karatsuba multiplication ไปสู่ matrix multiplication
    • ลดความซับซ้อนของ integer matrix multiplication และนำเสนอการทำฮาร์ดแวร์แบบ custom ที่ช่วยปรับปรุงด้านพื้นที่หรือเวลารันในงานคูณเมทริกซ์และตัวเร่งดีปเลิร์นนิง
    • ฉบับเต็มแบบเปิดเผย: https://arxiv.org/abs/2501.08889
  • Strassen Multisystolic Array Hardware Architectures
    • นำเสนอการทำฮาร์ดแวร์แบบ custom ที่มีประสิทธิภาพชิ้นแรกสำหรับอัลกอริทึม fast matrix multiplication ของ Strassen
    • บรรลุประสิทธิภาพระดับแนวหน้าในตัวเร่งดีปเลิร์นนิง
    • ฉบับเต็มแบบเปิดเผย: https://arxiv.org/abs/2502.10063
  • Algebraic Enhancements for Systolic Arrays วิทยานิพนธ์ปริญญาเอก
    • ครอบคลุมสามวิธีข้างต้น, การเร่งดีปเลิร์นนิง, algebraic enhancements, การออกแบบระบบตัวเร่งดีปเลิร์นนิงที่นำเสนอ และงานต่อยอดในอนาคต
    • ออนไลน์: https://macsphere.mcmaster.ca/handle/11375/30640

เหตุผลที่ต้องเพิ่มประสิทธิภาพต่อ MAC·multiplier

  • งานคำนวณส่วนใหญ่ของโมเดลดีปเลิร์นนิงสามารถแมปเป็น matrix multiplication ได้โดยทั่วไป ซึ่งประกอบด้วยชุดของการดำเนินการ multiply-accumulate
  • หากไม่มีนวัตกรรมเชิงพีชคณิตเพิ่มเติม throughput ของตัวเร่งดีปเลิร์นนิงจะถูกจำกัดด้วยจำนวนสูงสุดของการดำเนินการ MAC ที่ทำได้ต่อ clock cycle
  • เนื่องจากตัวเร่งดีปเลิร์นนิงมี MAC unit จำนวนมาก multiplier และ MAC unit จึงมักเป็นทรัพยากรคำนวณที่กินพื้นที่ฮาร์ดแวร์อย่างมากใน GEMM และตัวเร่งดีปเลิร์นนิง
  • throughput ของตัวเร่งอาจถูกจำกัดโดยตรงด้วย จำนวน multiplier ที่งบประมาณฮาร์ดแวร์รองรับได้
    • ในการทำบน FPGA นั้น DSP unit ที่ใช้สร้าง MAC unit อาจหมดก่อน LUT และ register
  • โครงการนี้สำรวจการก้าวข้ามข้อจำกัดดังกล่าวด้วยการนำ algebraic enhancement ไปใช้กับอัลกอริทึม matrix multiplication และการทำฮาร์ดแวร์แบบ custom

ขอบเขตการใช้งานและข้อจำกัด

  • สถาปัตยกรรมฮาร์ดแวร์ systolic array ที่เสนอช่วยปรับปรุงการเร่ง dense matrix multiplication
  • สามารถใช้กับโมเดลและเลเยอร์ DNN ที่แตกออกมาเป็น matrix multiplication เป็นหลัก
    • fully-connected layer
    • CNN
    • RNN
    • attention layer และ transformer model
  • ผลงานส่วนใหญ่มุ่งที่ fixed-point data type และการอนุมานของโครงข่ายประสาทเทียมแบบ quantized
    • แนวคิด fixed-point บางส่วนอาจต่อยอดไปยัง floating point ได้ในอนาคต
    • เนื่องจากใช้ fixed-point data type อัลกอริทึมและสถาปัตยกรรมฮาร์ดแวร์ที่นำเสนอจึงสร้างเอาต์พุตแบบเดียวกับอัลกอริทึมและสถาปัตยกรรมเดิม
    • ไม่มีการเปลี่ยนแปลงในด้าน numerical stability
  • แม้ผลลัพธ์จะตรวจสอบบน FPGA แต่สถาปัตยกรรมที่เสนอมีลักษณะทั่วไป และการปรับปรุงส่วนใหญ่ใช้ได้ทั้งกับ custom integrated circuit และการทำบน FPGA
  • สถาปัตยกรรมนี้อิงกับ systolic array
    • เป็นรูปแบบดีไซน์ที่มีประสิทธิภาพซึ่งใช้ในงานออกแบบ GEMM และตัวเร่งดีปเลิร์นนิงอย่าง Google TPU
    • แนวคิดบางส่วนอาจขยายไปสู่ดีไซน์ non-systolic array ได้ในอนาคต
    • ยังคงฟังก์ชันและอินเทอร์เฟซเดียวกับ systolic array เดิม
    • algebraic enhancement ถูกบรรจุอยู่ภายใน systolic array อย่างสมบูรณ์ จึงไม่ต้องมีขั้นตอน pre-processing หรือ post-processing เพิ่มเติม

พรีวิวผลลัพธ์ด้านประสิทธิภาพ

  • ผลการสังเคราะห์และประสิทธิภาพจากการรวมสถาปัตยกรรมของ [1] และ [3] ทำได้ดังนี้เมื่อเทียบกับตัวเร่งรุ่นใหม่บนแพลตฟอร์มคอมพิวต์ใกล้เคียงกัน

โครงสร้างระบบตัวเร่ง

  • ระบบตัวเร่งดีปเลิร์นนิงที่ทำไว้ในซอร์สโค้ดถูกใช้เพื่อโฮสต์และตรวจสอบ systolic array ที่เสนอใน [1]-[4]
  • การทำระบบนี้เน้นสำหรับการอนุมานด้วยอินพุต fixed-point และ quantized ของ non-sparse DNN model
    • convolutional layer
    • fully-connected layer
    • pooling layer
  • ทุก DNN layer ถูกเร่งด้วยฮาร์ดแวร์อย่างสมบูรณ์
  • ดีไซน์ฮาร์ดแวร์เพียงชุดเดียวสามารถเร่ง ML model ที่มี layer dimensions และ kernel sizes แบบ arbitrary ได้
  • input bitwidth และขนาดของ systolic array สามารถกำหนดเป็นพารามิเตอร์ได้
  • ยังถูกปรับแต่งอย่างมากให้เป็น GEMM accelerator แบบทั่วไปด้วย

บล็อกหลัก

  • Matrix Multiply Unit / MXU

    • มีสถาปัตยกรรม systolic array สำหรับทำการคูณเมทริกซ์
    • systolic array/MXU ที่แตกต่างกันจากแต่ละวิธีใน [1]-[4] ถูกสลับมาแทนที่ตำแหน่ง MXU ของระบบ

  • GEMM Unit

    • ประกอบด้วย MXU, SRAM และ addition logic
    • ทำให้สามารถรัน GEMM ของเมทริกซ์ขนาดใดก็ได้ด้วยการสะสม matrix tile

  • Post-GEMM Unit

    • ทำฟังก์ชันเฉพาะของ neural network กับเอาต์พุตจาก matrix multiplication
    • รวมถึงการเพิ่ม bias, inter-layer rescaling เพื่อ quantization, activation, padding และ pooling

  • Memory Unit

    • มี on-chip SRAM สำหรับเก็บ layer activation และ logic ควบคุมการเข้าถึงหน่วยความจำ
    • ใช้อัลกอริทึมฮาร์ดแวร์สำหรับ caching และ memory access ที่มีประสิทธิภาพเพื่อแมป convolution เป็น GEMM แบบ in-place โดยไม่มีการทำข้อมูลซ้ำหรือหน่วงเวลา
    • ใช้ memory partitioning scheme ที่รัน SRAM memory และการควบคุมที่อัตรา clock ครึ่งหนึ่งหรือหนึ่งในสี่ แต่ยังปล่อยข้อมูลใหม่ที่อัตรา clock เต็ม เพื่อปรับปรุงความถี่และพลังงานของทั้งระบบ

  • Off-chip DDR DRAM

    • ใช้เก็บ weights

  • RxTx Unit

    • รับผิดชอบ PCIe interface สำหรับเชื่อมต่อกับ host

  • Instruction Unit

    • ถอดรหัส accelerator instruction ที่ส่งมาจาก host
    • ทำให้ดีไซน์ฮาร์ดแวร์ชุดเดียวสามารถเร่ง ML model ที่มี layer dimensions และ kernel sizes แบบ arbitrary ได้

องค์ประกอบของซอร์สโค้ด

  • compiler
    • compiler ที่แปลง Python ML model description เป็น accelerator instruction
    • รวมโค้ดที่เชื่อมต่อกับ PCIe driver เพื่อเริ่มการรันโมเดลบนตัวเร่ง อ่านผลลัพธ์และ performance counter และทดสอบความถูกต้อง
  • rtl
    • SystemVerilog accelerator RTL ที่สังเคราะห์ได้
  • sim
    • สคริปต์ตั้งค่าสภาพแวดล้อม simulation สำหรับการตรวจสอบ
  • tests
    • ซอร์สโค้ด UVM testbench ที่เขียนด้วย Python และ cocotb
  • utils
    • Python package เพิ่มเติมและ utility script สำหรับการพัฒนาที่ใช้ในโครงการ
  • rtl/top/define.svh และ rtl/top/pkg.sv
    • มี configurable parameter หลายตัว
    • FIP_METHOD กำหนดชนิดของ systolic array เช่น baseline, FIP, FFIP [1]
    • SZI และ SZJ กำหนดความสูงและความกว้างของ systolic array
    • LAYERIO_WIDTH และ WEIGHT_WIDTH กำหนด input bitwidth
  • rtl/arith
    • มี mxu.sv และ mac_array.sv
    • มี RTL ของ baseline และสถาปัตยกรรม systolic array ที่เสนอบางส่วน ได้แก่ FIP, FFIP [1] ตามค่า FIP_METHOD

เอกสารเพิ่มเติม

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

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

 
GN⁺ 2024-03-17
ความคิดเห็นจาก Hacker News

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

    • นี่ไม่ใช่อัลกอริทึมซอฟต์แวร์ธรรมดา แต่เป็นการเพิ่มประสิทธิภาพระดับ สถาปัตยกรรมฮาร์ดแวร์
      ถ้าจะให้ได้ประโยชน์ ต้องสร้างฮาร์ดแวร์ให้ตรงกับมิติของอัลกอริทึม ซึ่งเป็นการตัดสินใจที่มีต้นทุนสูง
    • ถ้าเป็น ตัวเร่งการคูณเมทริกซ์ แบบ fixed-point ก็ไม่มีจุดที่ต้องระวังเป็นพิเศษ ผมมองว่าเป็นแค่อัลกอริทึมที่ถูกมองข้าม
      มันอิงกับอัลกอริทึมของ Winograd แล้วบังเอิญว่า Winograd ภายหลังก็เสนออีกอัลกอริทึมหนึ่งที่โด่งดังมากในงานเร่ง CNN ทำให้อัลกอริทึมนี้อาจได้รับความสนใจน้อยกว่า ทั้งหมดนี้ก็เป็นแค่การคาดเดา
    • อัลกอริทึมการคูณเมทริกซ์มีอยู่มากมาย และแต่ละแบบก็มีข้อดีข้อเสียชัดเจน
      มันคือการหาจุดสมดุลระหว่าง ความแม่นยำ, เวลาในการรัน, การขยายขนาด อยู่เสมอ และวิธีนี้อาจให้ความแม่นยำไม่ดีนักเมื่อใช้กับเลขทศนิยมลอยตัว
    • ไม่ได้ถูกลืมไปเสียทีเดียว
      มันยังหลงเหลืออยู่บ้างใน ตัวพิสูจน์ยืนยันแบบ Wegman-Carter ที่อิงกับ pseudodot product เช่น UMAC ดูพื้นหลังได้ในบทที่ 3 ของ [1]
      [1] https://cr.yp.to/antiforgery/pema-20071022.pdf
    • ผมแค่อ่านผ่าน ๆ อาจเข้าใจผิดได้ ถ้าผิดก็ช่วยแก้ให้ที แต่ผมเข้าใจว่านี่ไม่ใช่ตัวแทนการคูณเมทริกซ์โดยตรง แต่เป็น วิธีประมาณค่า ที่ให้ผลค่อนข้างดีสำหรับระบบเชิงเส้นประเภทที่พบใน AI/ML
      ถ้าใช้เพื่อจุดประสงค์นั้นก็ดูเพียงพอใช้ได้ไม่ใช่หรือ

  • ทำให้นึกถึงตอนปี 2018 ที่ผมเคยจะลองทำอะไรคล้าย ๆ กัน แต่สุดท้ายก็เลิกไปเพราะสมัครเรียนปริญญาเอกไม่ติดเลยสักที่
    https://github.com/ixaxaar/pytorch-dni
    แนวคิดนี้ก้าวไปอีกขั้น โดยพยายามจำลอง backpropagation ด้วยเครือข่ายภายนอก และอ้างว่าสมองจริงอาจทำแบบนั้นอยู่

    • ผมยังไม่เห็นจุดเชื่อมโยงเท่าไร
      งานนี้เป็นการเพิ่มประสิทธิภาพระดับล่างของการคูณเมทริกซ์ ส่วนรีโพที่ลิงก์มาดูเหมือนพยายามแทนที่เกรเดียนต์จาก backprop ด้วยค่าประมาณที่ถูกกว่า เลยสงสัยว่าความคล้ายกันของทั้งสองอย่างอยู่ตรงไหน
    • เรื่องนี้ให้ความรู้สึกเหมือนกรณี ไม่มีของฟรี
      เวลาที่ประหยัดได้จากการประมาณเกรเดียนต์แบบนี้ น่าจะหายไปเพราะต้องเทรนซ้ำเพิ่มขึ้นจากการสูญเสียความแม่นยำของเกรเดียนต์ ไม่ใช่หรือ?
    • แยกจากประเด็นเทคนิค ผมสงสัยว่า GIF สถาปัตยกรรมนั้นทำด้วยอะไร ดูดีมาก

  • น่าสนใจมากและคุ้มค่าแก่การอ่าน สำหรับคนที่สับสนจากคอมเมนต์ว่าทำไมมันถึงดีกว่า งานวิจัยนี้พูดถึงการสังเคราะห์ pipeline การคูณเมทริกซ์ บนฮาร์ดแวร์อย่าง FPGA หรือ ASIC
    บน CPU หรือ GPU เวลาของการบวกกับการคูณมักใกล้เคียงกันจึงรู้สึกความต่างได้ยาก แต่ยูนิตคูณกินทรานซิสเตอร์มากกว่ามาก ถ้าลดความซับซ้อนของวงจรลงได้ ก็สามารถเพิ่มความเร็วและ throughput แบบขนาน พร้อมทั้งลดพลังงานและความซับซ้อนของการเดินสายได้ วิธีนี้อาจมีประโยชน์เป็นพิเศษกับตัวเร่งการคูณเมทริกซ์แบบ sparse ที่มีประสิทธิภาพ
    อีกวิธีเจ๋ง ๆ ในการตัดการคูณออกจากการคูณเมทริกซ์คือใช้ semiring แบบอื่น [1] ตัวอย่างเช่น Tropical Semiring [2] แทนที่การคูณด้วยการบวก และแทนที่การบวกด้วย min หรือ max มันยังคงเป็นการคูณเมทริกซ์อยู่ เพียงแต่เปลี่ยนรูปของตัวดำเนินการทวิภาคเท่านั้น งานวิจัยในสาขาที่ค่อนข้างใหม่อย่าง Tropical Algebra [3] ตอนนี้ค่อนข้างคึกคักและมีเนื้อหามากมาย และถูกนำไปใช้กับปัญหาการหาค่าเหมาะที่สุดหลายแบบรวมถึงงานวิจัยด้านการปรับเหมาะโครงข่ายประสาท [4]
    วิธีนี้ก็เหมาะกับการสังเคราะห์ฮาร์ดแวร์เช่นกัน เพราะบล็อกลอจิกที่ตั้งค่าได้ของ FPGA ส่วนใหญ่สามารถทำ add/min/max ได้ในหนึ่งคล็อก ในขณะที่การคูณอย่างมีประสิทธิภาพต้องพึ่งฮาร์ดแวร์ตัวคูณเฉพาะทางบนชิปแบบตายตัว
    อีก semiring ที่เกี่ยวข้องกันซึ่งใช้ตัดการคูณออกได้อย่างมีประสิทธิภาพคือ Log Semiring [5] ถ้าต้องคูณความน่าจะเป็นต่อเนื่องกัน เช่น ใน Markov chain ตัวเลขจะเล็กมากอย่างรวดเร็วและทำให้ความแม่นยำของ floating point ลดลง หากนำลอการิทึมมาปรับสเกลก่อน การคูณจะกลายเป็นการบวก และการบวกจะกลายเป็น x + log1p(exp(y - x))
    [1] https://en.wikipedia.org/wiki/Semiring
    [2] https://en.wikipedia.org/wiki/Tropical_semiring
    [3] https://en.wikipedia.org/wiki/Tropical_geometry
    [4] https://proceedings.mlr.press/v80/zhang18i/zhang18i.pdf
    [5] https://en.wikipedia.org/wiki/Log_semiring

    • งานวิจัยใน [4] น่าหลงใหลจริง ๆ
      ผมยังเกือบเป็นมือใหม่ในด้านนี้ แต่ดูเหมือนว่ามันแสดงให้เห็นว่า เครือข่าย ReLU เกือบทั้งหมดสามารถแทนได้ด้วย tropical quotient ของพหุนาม tropical สองตัว และจึงสามารถวิเคราะห์ด้วยหลักการเชิงเรขาคณิตอย่างการทำภาพพื้นผิวได้ งานที่ใหม่กว่านี้ก็ยังอ้างอิงมันอยู่: https://scholar.google.com/scholar?cites=1003719112553620451... สงสัยว่ามีความก้าวหน้าที่สำคัญในเรื่องนี้หรือไม่
    • ว้าว นี่แหละคือสิ่งที่ Unified Algebra ว่าด้วย
      http://www.cs.toronto.edu/~hehner/UA.pdf
    • ตรงที่บอกว่าถ้าปรับสเกลตัวเลขด้วยการทำลอการิทึม การคูณจะกลายเป็นการบวก และการบวกจะกลายเป็น x + log1p(exp(y - x)) นั้น ใน ระบบจำนวนลอการิทึม การบวก/ลบแพงกว่าการคูณมาก
      โดยเฉพาะถ้าต้องสนใจผลการปัดเศษที่ถูกต้องด้วย ฮาร์ดแวร์ lookup table ที่ต้องใช้จะมีขนาดค่อนข้างใหญ่
    • วิธีทำลอการิทึมเพื่อเปลี่ยนการคูณเป็นการบวก ไม่ใช่แนวทางเดียวกับ GF(2^x) ที่ใช้กันมาหลายสิบปีหรอกหรือ?
      ข้อจำกัดเดียวที่นึกออกคือขนาดของ field
    • สิ่งที่เกี่ยวข้องกันอยู่บ้างคือ number theoretic transform
      https://ieeexplore.ieee.org/abstract/document/1451721

  • น่าทึ่งที่มันใช้งานได้จริง
    ปกติแล้วต้นทุนในการตรวจว่าควรใช้การคูณหรือการบวก กลับช้ากว่าการคูณไปเลย โดยเฉพาะเมื่อทำงานปริมาณมหาศาลแบบขนานกันยิ่งเป็นแบบนั้น

    • สงสัยว่าเมื่อเทียบกับ OpenBLAS และ cuBLAS แล้วจะได้ประมาณไหน

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

    • GF(2^x) เองก็จนถึงช่วงกลางศตวรรษที่แล้วก็ยังไม่มีใครรู้ว่าจะเอาไปใช้ทำอะไร
      อ้อ จะว่าไป วิทยาการคอมพิวเตอร์เองก็แทบยังไม่มีอยู่เลยจนถึงช่วงกลางศตวรรษที่แล้ว

  • ถ้าสนใจทฤษฎีคณิตศาสตร์เบื้องหลัง อัลกอริทึมเวลาไม่ถึงกำลังสาม สำหรับการคูณเมทริกซ์ เริ่มจากที่นี่ได้: https://en.wikipedia.org/wiki/Matrix_multiplication_algorith...
    มีข้อคาดการณ์ว่าสำหรับจำนวนจริงทุกค่า j > 0 จะมี n บางค่าอยู่ ทำให้เมทริกซ์ขนาด n x n สองตัวใด ๆ สามารถคูณกันได้ใน O(n^(2+j)) ขั้นตอน
    ปัจจุบันพิสูจน์ได้ที่ 2+j = w = 2.3728596 กล่าวคือสำหรับ j > 0.3728596

    • ไม่แน่ใจว่าคำอธิบายนี้ถูกไหม
      ถ้าเริ่มต้นด้วย “สำหรับทุก j จะมี n บางค่าอยู่” ในประโยคถัดไป n กับ j ก็กลายเป็นค่าคงที่ เท่ากับว่าพูดได้แค่ว่าเมทริกซ์ขนาดคงที่คูณกันได้ในเวลาคงที่ ซึ่งก็ถูกในเชิงเทคนิค แต่ดูเหมือนตั้งใจจะอ้างสิ่งที่แรงกว่านั้น
    • ดูเหมือนยิ่งเวลาผ่านไปความก้าวหน้าจะยิ่งยากขึ้น
      บางทีอาจไปตันที่ j=1/e ก็ได้ ผมไม่ถึงกับเรียกสิ่งนี้ว่าข้อคาดเดา แต่มันก็เป็นแค่ค่าคงที่ที่หยิบมาได้สะดวกใกล้กับค่าปัจจุบัน ถ้าคณิตศาสตร์เล่นตลกแบบนั้นกับเราก็คงขำดี
    • การคาดการณ์ว่ามันเป็นจริงสำหรับ j > 0 ใด ๆ ก็ดูค่อนข้างกล้าทีเดียว
      ช่วยแชร์ intuition หน่อยได้ไหมว่าทำไมถึงคิดแบบนั้น?

  • README นี้อธิบายได้แย่มากว่าจุดปรับปรุงคืออะไร และลดจำนวนการคูณลงครึ่งหนึ่งได้อย่างไร
    แล้ว เวลาในการทำงานแบบ Big O เป็นเท่าไร? นี่เปลี่ยนขอบเขตที่ดีที่สุดที่รู้กันอยู่หรือเปล่า?
    รูปประกอบก็ดูรกรุงรัง และแทบไม่ได้อธิบายเลยว่าทำไมแนวทางนี้ถึงเร็วหรือดีกว่าแบบอื่น เลยทำให้ไม่ค่อยอยากกดไปอ่าน PDF ต่อ
    ถ้าอยากเพิ่มความน่าเชื่อถือให้โปรเจกต์ ก็ควรอธิบายอย่างตรงไปตรงมาและชัดเจนว่าจริง ๆ แล้วเกิดอะไรขึ้น และใช้คำอธิบายกับแผนภาพที่ชัดเจน แทนรูปที่เหมือนพยายามดึงคนเข้ามาด้วยการโฆษณาเกินจริง แบบนี้แยกยากว่านี่คือความก้าวหน้าครั้งใหญ่จริง ๆ หรือไม่สำคัญอะไรเลย น่าเสียดายที่มันให้ความรู้สึกเหมือนเป็นการเลือกทำแบบจงใจเพื่ออาศัยกระแส AI ทางเลือกที่อยากเชื่อมากกว่าคือผู้เขียนแค่ต้องแก้ไขและให้บริบทให้ดีขึ้น

    • สำหรับคำถามว่า “เวลาในการทำงานแบบ Big O เป็นเท่าไร?” การอ้างว่าลดจำนวนการคูณลงครึ่งหนึ่งนั้นไม่ได้ส่งผลต่อ Big O
      ในงานวิจัย(https://arxiv.org/abs/2311.12224) คณิตศาสตร์ที่ใช้ลดจำนวนการคูณลงครึ่งหนึ่งไม่ได้เข้าใจยากนัก แค่อ่านสูตร 2 และสูตร 3~6 ของการคูณเมทริกซ์แบบดั้งเดิมก็พอ
      ดูชัดเจนว่าแลกกับการเพิ่มการบวก/การลบจำนวนมากเพื่อให้ลดการคูณลงครึ่งหนึ่งตามที่โฆษณาไว้ หลังจากนั้นก็ทำให้ขั้นตอนวิธีนั้นเวกเตอร์ไรซ์ได้ดีขึ้น ซึ่งงานแบบนี้ก็มักจะซับซ้อนขึ้นอย่างรวดเร็วอยู่แล้ว
      ความกังวลหลักคือ เสถียรภาพเชิงตัวเลข
    • README แทบไม่อธิบายอะไร แต่บทนำของตัวงานวิจัยเองค่อนข้างอ่านเข้าถึงได้
      ถ้าถามว่าเป็นความก้าวหน้าครั้งใหญ่ไหม ผมมองว่าเป็นการปรับปรุงด้วยค่าคงที่แบบสวยงามที่นำไปใช้ได้ตรง ๆ กับ ตัวเร่ง fixed-point ที่มีข้อจำกัดด้านพื้นที่บนชิป มันไม่ได้เปลี่ยนทุกอย่างในชั่วข้ามคืน แต่ก็ไม่ใช่ว่าไม่มีความหมายเลย เป็นงานที่ดี
    • ไม่ได้อยากให้ฟังดูเป็นพวกชนชั้นนำ แต่ผมไม่เข้าใจประเด็นของคอมเมนต์นี้เลยจริง ๆ
      ถ้าคุณไม่เข้าใจสัญกรณ์ Big O มากพอจะรู้ว่า “ลดจำนวนการคูณลงครึ่งหนึ่ง” ไม่ได้เปลี่ยน Big O ก็ไม่เข้าใจว่าทำไมถึงถามเรื่องนั้น