HN giới thiệu: Nhân ma trận giảm một nửa số phép nhân

 (github.com/trevorpogue)
3 điểm bởi GN⁺ 2024-03-17 | 1 bình luận | Chia sẻ qua WhatsApp
  • Kho lưu trữ này chứa mã nguồn để kiểm chứng một kiến trúc systolic array tính cùng kết quả nhân ma trận với ít tài nguyên phần cứng hơn hoặc thời gian thực thi ngắn hơn trong GEMM và bộ tăng tốc phần cứng học sâu
  • Phương pháp được đề xuất thay một phần phép nhân ma trận bằng phép cộng bit-width thấp rẻ hơn, nhằm giảm một nửa số multiplier cần cho cùng hiệu năng hoặc tăng hiệu năng trên mỗi đơn vị MAC
  • Kết quả đạt tăng tốc suy luận CNN tối đa 3× so với các bộ tăng tốc mới nhất trên nền tảng tính toán tương tự, thông lượng phép nhân trên mỗi multiplier/clock cao hơn 2×, diện tích thấp và tần số xung nhịp cao
  • Phạm vi áp dụng gồm dense matrix multiplication và các fully-connected layer, CNN, RNN, attention layer/transformer model chủ yếu sử dụng phép toán này; chủ yếu tạo ra cùng đầu ra như phương pháp hiện có trong suy luận fixed-point/quantized
  • Kiến trúc được thiết kế để giữ nguyên chức năng và giao diện như systolic array hiện có, nên có thể tích hợp bằng cách thay thế MXU của hệ thống tăng tốc hiện có mà không cần tiền xử lý hay hậu xử lý bổ sung

Mục tiêu và thành quả của dự án

  • Algebraic Enhancements for GEMM & AI Accelerators chứa mã nguồn của hệ thống GEMM và bộ tăng tốc phần cứng học sâu
  • Hệ thống này được dùng để kiểm chứng các kiến trúc systolic array triển khai trên phần cứng những thuật toán nhân ma trận hiệu quả đã được đề xuất hoặc chưa được khám phá đầy đủ
  • Mục tiêu là tính cùng đầu ra với ít tài nguyên phần cứng hơn hoặc thời gian thực thi ngắn hơn
  • Hiệu năng được trình bày như sau
    • Suy luận CNN nhanh hơn tối đa 3× so với các bộ tăng tốc mới nhất được triển khai trên cùng loại nền tảng tính toán
    • mults/multiplier/clock cycle từ 2× trở lên, vượt qua conventional limit là 1
    • Diện tích thấp và tần số xung nhịp cao

Kiến trúc đã được kiểm chứng trong các bài báo và luận án tiến sĩ

  • Fast Inner-Product Algorithms and Architectures for Deep Neural Network Accelerators
    • Giảm một nửa số multiplier cần thiết để đạt cùng hiệu năng trong nhân ma trận và kiến trúc phần cứng học sâu
    • Thuật toán inner-product thay thế đổi một nửa số phép nhân lấy các phép cộng bit-width thấp, chi phí thấp
    • Systolic array được đề xuất có thể được thay thế trực tiếp vào hệ thống systolic array hiện có, và có thể tăng gấp đôi hiệu năng trên mỗi đơn vị MAC mà không thay đổi chức năng hay thiết kế của phần còn lại trong hệ thống
    • Bản đầy đủ công khai: https://arxiv.org/abs/2311.12224
  • Karatsuba Matrix Multiplication and its Efficient Custom Hardware Implementations
    • Đề xuất KMM, mở rộng Karatsuba multiplication sang matrix multiplication
    • Giảm độ phức tạp của integer matrix multiplication và trình bày các triển khai custom hardware giúp cải thiện diện tích hoặc thời gian thực thi trong nhân ma trận và bộ tăng tốc học sâu
    • Bản đầy đủ công khai: https://arxiv.org/abs/2501.08889
  • Strassen Multisystolic Array Hardware Architectures
    • Trình bày triển khai custom hardware hiệu quả đầu tiên cho thuật toán fast matrix multiplication của Strassen
    • Đạt hiệu năng ở mức state-of-the-art trong bộ tăng tốc học sâu
    • Bản đầy đủ công khai: https://arxiv.org/abs/2502.10063
  • Luận án tiến sĩ Algebraic Enhancements for Systolic Arrays
    • Bao quát ba phương pháp trên cùng với tăng tốc học sâu, algebraic enhancements, thiết kế hệ thống tăng tốc học sâu được trình bày và công việc trong tương lai
    • Trực tuyến: https://macsphere.mcmaster.ca/handle/11375/30640

Vì sao tăng hiệu năng trên mỗi MAC/multiplier

  • Phần lớn khối lượng tính toán của mô hình học sâu thường có thể ánh xạ thành matrix multiplication, vốn gồm chuỗi các phép multiply-accumulate
  • Nếu không có thêm algebraic innovation, thông lượng của bộ tăng tốc học sâu bị giới hạn bởi số phép toán MAC tối đa có thể thực hiện trong mỗi clock cycle
  • Vì bộ tăng tốc học sâu chứa nhiều MAC unit, multiplier và MAC unit dễ trở thành compute resource chiếm nhiều diện tích phần cứng trong GEMM và bộ tăng tốc học sâu
  • Thông lượng của accelerator có thể bị giới hạn trực tiếp bởi số lượng multiplier mà ngân sách phần cứng cho phép
    • Trong triển khai FPGA, các DSP unit dùng để instantiate MAC unit có thể cạn trước LUT và register
  • Dự án này khám phá hướng vượt qua giới hạn đó bằng cách áp dụng algebraic enhancement vào thuật toán matrix multiplication và triển khai custom hardware

Phạm vi áp dụng và ràng buộc

  • Kiến trúc phần cứng systolic array được đề xuất cải thiện tăng tốc dense matrix multiplication
  • Có thể dùng trong các DNN model và layer chủ yếu được phân rã thành matrix multiplication
    • fully-connected layer
    • CNN
    • RNN
    • attention layer và transformer model
  • Phần lớn đóng góp tập trung vào kiểu dữ liệu fixed-point và suy luận mạng nơ-ron quantized
    • Một số khái niệm fixed-point có thể được mở rộng sang floating point trong tương lai
    • Vì sử dụng kiểu dữ liệu fixed-point, các thuật toán và kiến trúc phần cứng được trình bày tạo ra cùng đầu ra như thuật toán/kiến trúc hiện có
    • Không có thay đổi về numerical stability
  • Kết quả đã được kiểm chứng trên FPGA, nhưng các kiến trúc được đề xuất mang tính tổng quát và phần lớn cải tiến có thể áp dụng cho cả custom integrated circuit lẫn triển khai FPGA
  • Kiến trúc dựa trên systolic array
    • Đây là kiểu thiết kế hiệu quả được dùng trong các thiết kế tăng tốc GEMM và học sâu như Google TPU
    • Một số khái niệm có thể được mở rộng sang thiết kế non-systolic array trong tương lai
    • Giữ cùng chức năng và giao diện với systolic array hiện có
    • Algebraic enhancement được self-contained hoàn toàn bên trong systolic array, không cần bước tiền xử lý hay hậu xử lý bổ sung

Xem trước kết quả hiệu năng

  • Kết quả tổng hợp và hiệu năng khi kết hợp các kiến trúc trong [1] và [3] đạt được những điều sau so với các bộ tăng tốc mới nhất trên nền tảng tính toán tương tự

Cấu trúc hệ thống tăng tốc

  • Hệ thống tăng tốc học sâu được triển khai trong mã nguồn được dùng để host và kiểm chứng các systolic array được đề xuất trong [1]-[4]
  • Triển khai hệ thống chuyên biệt cho suy luận với đầu vào fixed-point/quantized của non-sparse DNN model
    • convolutional layer
    • fully-connected layer
    • pooling layer
  • Tất cả DNN layer đều được tăng tốc hoàn toàn bằng phần cứng
  • Một thiết kế phần cứng duy nhất có thể tăng tốc ML model với arbitrary layer dimensions và kernel sizes
  • input bitwidth và systolic array dimension có thể được thiết lập dưới dạng parameter
  • Cũng được tối ưu hóa cao như một GEMM accelerator thông dụng

Các khối chính

  • Matrix Multiply Unit / MXU

    • Chứa kiến trúc systolic array thực hiện nhân ma trận
    • Các systolic array/MXU khác nhau được đề xuất trong từng phương pháp của [1]-[4] được thay vào vị trí MXU của hệ thống

  • GEMM Unit

    • Chứa MXU, SRAM và addition logic
    • Cho phép thực thi GEMM với ma trận kích thước tùy ý bằng cách tích lũy các matrix tile

  • Post-GEMM Unit

    • Thực hiện các neural network-specific function trên đầu ra matrix multiplication
    • Bao gồm thêm bias, inter-layer rescaling cho quantization, activation, padding và pooling

  • Memory Unit

    • Chứa on-chip SRAM lưu layer activation và memory access control logic
    • Triển khai thuật toán caching và memory access hardware hiệu quả, ánh xạ convolution thành GEMM in-place mà không cần data duplication hay delay
    • Sử dụng memory partitioning scheme chạy SRAM memory và control ở half hoặc quarter clock rate trong khi xuất dữ liệu mới ở full clock rate, nhằm cải thiện frequency và power của toàn hệ thống

  • Off-chip DDR DRAM

    • Dùng để lưu weights

  • RxTx Unit

    • Đảm nhiệm PCIe interface kết nối với host

  • Instruction Unit

    • Decoding accelerator instruction do host gửi
    • Cho phép một thiết kế phần cứng duy nhất tăng tốc ML model với arbitrary layer dimensions và kernel sizes

Cấu trúc mã nguồn

  • compiler
    • Compiler phân tích Python ML model description thành accelerator instruction
    • Bao gồm mã giao tiếp với PCIe driver để bắt đầu model execution trên accelerator, đọc kết quả và performance counter, và kiểm tra correctness
  • rtl
    • SystemVerilog accelerator RTL có thể tổng hợp
  • sim
    • Script thiết lập simulation environment để kiểm chứng
  • tests
    • Mã nguồn UVM testbench viết bằng Python và cocotb
  • utils
    • Các Python package bổ sung và utility script phát triển dùng trong dự án
  • rtl/top/define.svh và rtl/top/pkg.sv
    • Chứa nhiều configurable parameter
    • FIP_METHOD định nghĩa systolic array type, với ví dụ như baseline, FIP, FFIP [1]
    • SZI và SZJ định nghĩa height và width của systolic array
    • LAYERIO_WIDTH và WEIGHT_WIDTH định nghĩa input bitwidth
  • rtl/arith
    • Chứa mxu.sv và mac_array.sv
    • Chứa RTL của baseline và một số kiến trúc systolic array được đề xuất là FIP, FFIP [1], tùy theo giá trị FIP_METHOD

Tài liệu bổ sung

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-03-17
Các ý kiến trên Hacker News

  • Trông khá hay, nhưng điểm vướng là gì? Chẳng hạn, tôi thắc mắc vì sao nó chưa được triển khai sẵn trong các bộ tăng tốc
    Không biết đây thật sự chỉ là một thuật toán bị lãng quên, hay có ràng buộc nào ảnh hưởng đến chi phí sản xuất bộ tăng tốc, v.v.

    • Đây không phải là một thuật toán phần mềm đơn thuần, mà là tối ưu hóa kiến trúc phần cứng
      Muốn có lợi thì phải tạo phần cứng khớp với các chiều của thuật toán, và đó là một quyết định tốn kém
    • Nếu là bộ tăng tốc nhân ma trận số cố định thì không có bẫy gì đặc biệt, tôi nghĩ đơn giản là một thuật toán bị bỏ sót
      Nó dựa trên thuật toán của Winograd, nhưng tình cờ là về sau Winograd cũng đề xuất một thuật toán riêng khác trở nên rất nổi tiếng trong tăng tốc CNN, nên thuật toán này có thể ít được chú ý hơn. Tuy vậy đây chỉ là suy đoán
    • Có rất nhiều thuật toán nhân ma trận, và mỗi thuật toán đều có ưu nhược điểm lớn
      Luôn là sự cân bằng giữa độ chính xác, thời gian thực thi, khả năng mở rộng, và cách này có khả năng cho độ chính xác kém với số dấu phẩy động
    • Không phải là hoàn toàn bị lãng quên
      Nó vẫn còn tồn tại ở một mức nào đó trong các bộ xác thực Wegman-Carter dựa trên tích trong giả như UMAC. Có thể xem chương 3 của [1] để biết bối cảnh
      [1] https://cr.yp.to/antiforgery/pema-20071022.pdf
    • Tôi chỉ lướt qua nên nếu sai xin hãy sửa, nhưng tôi hiểu đây không phải là một phương án thay thế cho nhân ma trận, mà là một phương pháp xấp xỉ cho kết quả khá tốt với kiểu hệ tuyến tính thường thấy trong AI/ML
      Với mục đích đó thì có vẻ đủ ổn

  • Tôi nhớ lại hồi năm 2018 từng thử làm thứ tương tự, nhưng bị từ chối hết các hồ sơ ứng tuyển tiến sĩ nên đã bỏ dở
    https://github.com/ixaxaar/pytorch-dni
    Ý tưởng ở đây còn đi xa hơn một bước: cố gắng sao chép lan truyền ngược bằng một mạng bên ngoài, và cho rằng não bộ thực sự có khả năng làm như vậy

    • Tôi không rõ điểm liên hệ
      Công trình này là tối ưu hóa cấp thấp cho nhân ma trận, còn kho lưu trữ bạn liên kết có vẻ nhằm thay thế gradient lan truyền ngược bằng một ước lượng rẻ hơn. Tôi tò mò hai thứ này giống nhau ở điểm nào
    • Cảm giác đây gần giống tình huống không có bữa trưa miễn phí
      Thời gian tiết kiệm được nhờ xấp xỉ gradient như vậy có vẻ sẽ biến mất vì mất độ chính xác của gradient khiến cần nhiều vòng huấn luyện hơn, không phải sao?
    • Tách khỏi phần thảo luận kỹ thuật, tôi tò mò bạn đã dùng gì để tạo GIF kiến trúc đó. Trông đẹp đấy

  • Thực sự rất thú vị và đáng đọc. Với những ai trong phần bình luận còn bối rối không hiểu vì sao cách này tốt hơn, bài báo đang nói về việc tổng hợp pipeline nhân ma trận trên phần cứng như FPGA hoặc ASIC
    Trên CPU hoặc GPU, thời gian cộng và nhân nhìn chung khá tương đương nên khó cảm nhận khác biệt, nhưng đơn vị nhân chiếm nhiều transistor hơn rất nhiều. Giảm độ phức tạp của mạch có thể tăng tốc độ và thông lượng xử lý song song, đồng thời giảm điện năng và độ phức tạp của dây nối. Cách tiếp cận này có thể đặc biệt hữu ích cho các bộ tăng tốc nhân ma trận thưa hiệu quả
    Một cách hay khác để loại bỏ phép nhân trong nhân ma trận là dùng một bán vành (semiring) khác [1]. Ví dụ Tropical Semiring [2] thay phép nhân bằng phép cộng, và thay phép cộng bằng min hoặc max. Nó vẫn là nhân ma trận, nhưng ở dạng mà các phép toán nhị phân đã thay đổi. Nghiên cứu về Tropical Algebra [3], một lĩnh vực tương đối mới, hiện khá sôi động và phong phú, được dùng trong nhiều bài toán tối ưu hóa và nghiên cứu tối ưu hóa mạng nơ-ron [4]
    Cách này cũng rất phù hợp với tổng hợp phần cứng, vì hầu hết các khối logic cấu hình được của FPGA có thể thực hiện add/min/max trong một chu kỳ xung nhịp, trong khi phép nhân hiệu quả cần các bộ nhân phần cứng chuyên dụng cố định trên chip
    Một cách liên quan khác để loại bỏ hiệu quả phép nhân bằng bán vành là dùng Log Semiring [5]. Nếu phải nhân nối tiếp các xác suất như trong chuỗi Markov, các con số sẽ nhanh chóng trở nên rất nhỏ và làm giảm độ chính xác dấu phẩy động. Nếu trước tiên lấy log để co giãn thang đo, phép nhân trở thành phép cộng, còn phép cộng trở thành 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

    • Bài báo ở [4] thực sự cuốn hút
      Tôi gần như là người mới trong lĩnh vực này, nhưng có vẻ bài đó cho thấy gần như mọi mạng ReLU đều có thể được biểu diễn dưới dạng tỷ số tropical của hai đa thức tropical, và do đó có thể được phân tích bằng các nguyên lý hình học như trực quan hóa bề mặt. Nó cũng được trích dẫn trong các nghiên cứu gần đây hơn: https://scholar.google.com/scholar?cites=1003719112553620451... Tôi tò mò liệu đã có tiến triển đáng kể nào ở đây chưa
    • Chà, đây chính là nội dung mà Unified Algebra xử lý
      http://www.cs.toronto.edu/~hehner/UA.pdf
    • Phần nói rằng nếu lấy log để co giãn các con số thì phép nhân trở thành phép cộng và phép cộng trở thành x + log1p(exp(y - x)); trong hệ số log, phép cộng/trừ đắt hơn phép nhân rất nhiều
      Đặc biệt nếu còn quan tâm đến kết quả làm tròn đúng, bảng tra cứu phần cứng cần thiết sẽ khá lớn
    • Cách lấy log để biến phép nhân thành phép cộng chẳng phải giống với cách tiếp cận của GF(2^x) đã được dùng suốt nhiều thập kỷ sao?
      Giới hạn duy nhất tôi nghĩ ra là kích thước của trường
    • Có một thứ phần nào liên quan là biến đổi số học
      https://ieeexplore.ieee.org/abstract/document/1451721

  • Thật ngạc nhiên là cách này thực sự hoạt động
    Thông thường chi phí để phát hiện nên dùng phép nhân hay phép cộng còn chậm hơn việc cứ thực hiện phép nhân. Đặc biệt là khi thực hiện một khối lượng công việc khổng lồ song song

    • Không biết nếu so với OpenBLAS và cuBLAS thì sẽ thế nào

  • Thú vị là một quy trình được phát minh từ năm 1968 đến nay vẫn chưa được dùng cho mục đích này

    • GF(2^x) cũng chẳng ai biết dùng vào việc gì cho đến giữa thế kỷ trước
      À, nghĩ lại thì bản thân khoa học máy tính cũng gần như chưa tồn tại cho đến giữa thế kỷ trước

  • Nếu quan tâm đến lý thuyết toán học đằng sau thuật toán thời gian dưới bậc ba cho nhân ma trận, có thể bắt đầu từ đây: https://en.wikipedia.org/wiki/Matrix_multiplication_algorith...
    Người ta phỏng đoán rằng với mọi số thực j > 0, tồn tại một n nào đó sao cho có thể nhân hai ma trận n x n bất kỳ trong O(n^(2+j)) bước
    Hiện đã chứng minh được với 2+j = w = 2.3728596, tức là j > 0.3728596

    • Tôi không chắc cách diễn đạt này có đúng không
      Nếu bắt đầu bằng “với mọi j, tồn tại một n nào đó” thì trong câu sau n và j trở thành hằng số. Khi đó nó chỉ nói rằng có thể nhân ma trận kích thước hằng số trong thời gian hằng số. Về mặt kỹ thuật thì đúng, nhưng có lẽ người viết muốn nêu một khẳng định mạnh hơn
    • Có vẻ càng về sau tiến triển càng khó hơn
      Có lẽ nó sẽ chạm sàn ở j=1/e. Tôi thậm chí sẽ không gọi đây là phỏng đoán, chỉ là một hằng số tiện lợi gần với giá trị hiện tại. Sẽ khá buồn cười nếu toán học chơi khăm chúng ta như vậy
    • Dự đoán rằng điều này đúng với mọi j > 0 là khá táo bạo
      Bạn có thể chia sẻ trực giác vì sao lại nghĩ vậy không?

  • README này giải thích rất kém về điểm cải tiến là gì và làm thế nào để giảm một nửa số phép nhân
    Thời gian chạy Big O thì sao? Nó có thay đổi cận tối ưu đã biết không?
    Hình minh họa cũng rối mắt và hầu như không giải thích được vì sao cách tiếp cận này nhanh hơn hay tốt hơn. Vì vậy tôi cũng ngại bấm vào PDF
    Nếu muốn tăng độ tin cậy của dự án, nên giải thích trung thực và rõ ràng chuyện gì đang thực sự diễn ra, đồng thời cung cấp phần giải thích và sơ đồ rõ ràng thay vì những hình ảnh có vẻ như lôi kéo người ta bằng quảng cáo thổi phồng. Khó phân biệt đây là một đột phá lớn hay chẳng có gì đáng kể. Đáng tiếc là cũng có cảm giác đây là lựa chọn có chủ ý nhằm tận dụng cơn sốt AI. Một khả năng khác mà tôi muốn tin hơn là tác giả đơn giản chỉ cần chỉnh sửa và cung cấp bối cảnh tốt hơn

    • Về câu hỏi “Thời gian chạy Big O là gì?”, vì tuyên bố là giảm một nửa số phép nhân nên nó không ảnh hưởng đến Big O
      Trong bài báo (https://arxiv.org/abs/2311.12224), phần toán học giúp giảm một nửa số phép nhân không khó hiểu. Chỉ cần đọc phép nhân ma trận truyền thống ở công thức 2 và các công thức 3~6
      Có vẻ rõ ràng là đổi lại việc giảm một nửa số phép nhân như quảng bá, nó bổ sung rất nhiều phép cộng/trừ. Sau đó họ vector hóa thuật toán đó tốt hơn, và như thường thấy với những việc kiểu này, nó nhanh chóng trở nên phức tạp
      Mối lo chính là độ ổn định số học
    • README không giải thích nhiều, nhưng phần mở đầu của chính bài báo thì khá dễ tiếp cận
      Còn về chuyện có mang tính đột phá hay không, tôi xem đây là một cải thiện hệ số hằng số gọn gàng, có thể áp dụng ngay cho bộ tăng tốc số cố định bị ràng buộc về diện tích. Nó sẽ không thay đổi mọi thứ chỉ sau một đêm, nhưng cũng không phải là không có gì. Đây là một công trình tốt
    • Tôi không muốn nghe có vẻ tinh hoa chủ nghĩa, nhưng tôi hoàn toàn không hiểu ý chính của bình luận này
      Nếu bạn không hiểu ký hiệu Big O đến mức không biết rằng “giảm một nửa số phép nhân” không làm thay đổi Big O, thì tôi không hiểu vì sao bạn lại hỏi điều đó