HN Perkenalan: Perkalian Matriks yang Mengurangi Jumlah Perkalian hingga Setengah

 (github.com/trevorpogue)
3 poin oleh GN⁺ 2024-03-17 | 1 komentar | Bagikan ke WhatsApp
  • Repositori ini berisi source code untuk memverifikasi arsitektur systolic array yang menghitung hasil perkalian matriks yang sama dengan resource hardware atau waktu eksekusi yang lebih sedikit pada GEMM dan akselerator hardware deep learning
  • Metode yang diusulkan mengganti sebagian perkalian matriks dengan penjumlahan ber-bitwidth rendah yang lebih murah, dengan tujuan mengurangi jumlah multiplier yang dibutuhkan untuk performa yang sama hingga setengahnya atau meningkatkan performa per unit MAC
  • Hasilnya mencapai akselerasi inferensi CNN hingga 3×, throughput perkalian per multiplier/clock lebih dari 2×, area rendah, dan frekuensi clock tinggi dibandingkan akselerator terbaru pada platform komputasi serupa
  • Cakupan penerapannya meliputi dense matrix multiplication serta fully-connected layer, CNN, RNN, attention layer/model transformer yang terutama menggunakannya; terutama pada inferensi fixed-point dan terkuantisasi, metode ini menghasilkan output yang sama dengan metode konvensional
  • Arsitektur ini dirancang untuk mempertahankan fungsi dan antarmuka yang sama seperti systolic array konvensional, sehingga dapat diintegrasikan dengan mengganti MXU pada sistem akselerator yang ada tanpa preprocessing atau postprocessing tambahan

Tujuan dan capaian proyek

  • Algebraic Enhancements for GEMM & AI Accelerators berisi source code untuk sistem GEMM dan akselerator hardware deep learning
  • Sistem ini digunakan untuk memverifikasi arsitektur systolic array yang mengimplementasikan algoritme perkalian matriks efisien yang diusulkan atau belum cukup dieksplorasi di hardware
  • Tujuannya adalah menghitung output yang sama dengan resource hardware yang lebih sedikit atau waktu eksekusi yang lebih singkat
  • Performa yang disajikan sebagai hasilnya adalah sebagai berikut
    • Inferensi CNN hingga 3× lebih cepat dibandingkan akselerator terbaru yang diimplementasikan pada platform komputasi sejenis
    • mults/multiplier/clock cycle 2× atau lebih, melampaui conventional limit sebesar 1
    • Area rendah dan frekuensi clock tinggi

Arsitektur yang diverifikasi dalam paper dan disertasi doktoral

Mengapa meningkatkan performa per MAC/multiplier

  • Sebagian besar pekerjaan komputasi pada model deep learning umumnya dapat dipetakan menjadi matrix multiplication, yang tersusun dari rangkaian operasi multiply-accumulate
  • Tanpa algebraic innovation tambahan, throughput akselerator deep learning dibatasi oleh jumlah maksimum operasi MAC yang dapat dilakukan per clock cycle
  • Karena akselerator deep learning berisi banyak unit MAC, multiplier dan unit MAC cenderung menjadi compute resource yang mengambil porsi besar area hardware pada GEMM dan akselerator deep learning
  • Throughput accelerator dapat dibatasi langsung oleh jumlah multiplier yang dapat ditanggung oleh anggaran hardware
    • Pada implementasi FPGA, DSP unit yang menginstansiasi unit MAC dapat habis sebelum LUT dan register
  • Proyek ini mengeksplorasi cara melampaui batas tersebut dengan menerapkan algebraic enhancement pada algoritme matrix multiplication dan implementasi custom hardware

Cakupan penerapan dan batasan

  • Arsitektur hardware systolic array yang diusulkan meningkatkan akselerasi dense matrix multiplication
  • Dapat dimanfaatkan pada model dan layer DNN yang terutama diuraikan menjadi matrix multiplication
    • fully-connected layer
    • CNN
    • RNN
    • attention layer dan model transformer
  • Sebagian besar kontribusi berfokus pada tipe data fixed-point dan inferensi jaringan saraf terkuantisasi
    • Beberapa konsep fixed-point mungkin dapat diperluas ke floating point di masa depan
    • Karena menggunakan tipe data fixed-point, algoritme dan arsitektur hardware yang disajikan menghasilkan output yang sama dengan algoritme/arsitektur konvensional
    • Tidak ada perubahan pada numerical stability
  • Hasilnya telah diverifikasi pada FPGA, tetapi arsitektur yang diusulkan bersifat umum dan sebagian besar peningkatan dapat diterapkan baik pada custom integrated circuit maupun implementasi FPGA
  • Arsitekturnya berbasis systolic array
    • Ini adalah tipe desain efisien yang digunakan pada desain akselerasi GEMM dan deep learning seperti Google TPU
    • Beberapa konsep mungkin dapat diperluas ke desain non-systolic array di masa depan
    • Mempertahankan fungsi dan antarmuka yang sama dengan systolic array konvensional
    • Algebraic enhancement sepenuhnya self-contained di dalam systolic array, sehingga tidak memerlukan tahap preprocessing atau postprocessing tambahan

Pratinjau hasil performa

  • Hasil sintesis dan performa yang menggabungkan arsitektur [1] dan [3] mencapai hal berikut dibandingkan akselerator terbaru pada platform komputasi serupa

    • Inferensi CNN hingga 3× lebih cepat

    • mults/multiplier/clock cycle 2× lebih tinggi

Struktur sistem akselerator

  • Sistem akselerator deep learning yang diimplementasikan dalam source code digunakan untuk meng-host dan memverifikasi systolic array yang diusulkan dalam [1]-[4]
  • Implementasi sistem dikhususkan untuk inferensi input fixed-point dan terkuantisasi pada model DNN non-sparse
    • convolutional layer
    • fully-connected layer
    • pooling layer
  • Semua layer DNN sepenuhnya diakselerasi di hardware
  • Satu desain hardware dapat mengakselerasi model ML dengan arbitrary layer dimensions dan kernel sizes
  • Input bitwidth dan dimensi systolic array dapat diatur sebagai parameter
  • Juga sangat dioptimalkan sebagai GEMM accelerator umum

Blok utama

  • Matrix Multiply Unit / MXU

    • Mencakup arsitektur systolic array yang melakukan perkalian matriks
    • Berbagai systolic array/MXU yang diusulkan pada tiap metode dalam [1]-[4] menggantikan posisi MXU dalam sistem

  • GEMM Unit

    • Mencakup MXU, SRAM, dan addition logic
    • Mengakumulasi matrix tile agar GEMM untuk matriks berukuran arbitrer dapat dijalankan

  • Post-GEMM Unit

    • Melakukan fungsi spesifik neural network pada output matrix multiplication
    • Mencakup penambahan bias, inter-layer rescaling untuk quantization, activation, padding, dan pooling

  • Memory Unit

    • Mencakup SRAM on-chip yang menyimpan layer activation dan memory access control logic
    • Mengimplementasikan algoritme hardware caching dan memory access yang efisien untuk memetakan convolution menjadi GEMM secara in-place tanpa data duplication atau delay
    • Menggunakan memory partitioning scheme yang menjalankan SRAM memory dan control pada half atau quarter clock rate sambil mengeluarkan data baru pada full clock rate, sehingga meningkatkan overall system frequency dan power

  • Off-chip DDR DRAM

    • Digunakan untuk menyimpan weights

  • RxTx Unit

    • Menangani PCIe interface yang terhubung ke host

  • Instruction Unit

    • Mendekode accelerator instruction yang dikirim oleh host
    • Memungkinkan satu desain hardware mengakselerasi model ML dengan arbitrary layer dimensions dan kernel sizes

Struktur source code

  • compiler
    • Compiler yang mem-parsing deskripsi model ML Python menjadi accelerator instruction
    • Mencakup kode yang berinteraksi dengan PCIe driver untuk memulai model execution pada accelerator, membaca result dan performance counter, serta menguji correctness
  • rtl
    • SystemVerilog accelerator RTL yang dapat disintesis
  • sim
    • Script penyiapan simulation environment untuk verifikasi
  • tests
    • Source code UVM testbench yang ditulis dengan Python dan cocotb
  • utils
    • Package Python tambahan dan utility script pengembangan yang digunakan dalam proyek
  • rtl/top/define.svh dan rtl/top/pkg.sv
    • Mencakup berbagai configurable parameter
    • FIP_METHOD mendefinisikan systolic array type, dengan baseline, FIP, FFIP [1], dan lainnya sebagai contoh
    • SZI dan SZJ mendefinisikan height dan width systolic array
    • LAYERIO_WIDTH dan WEIGHT_WIDTH mendefinisikan input bitwidth
  • rtl/arith
    • Mencakup mxu.sv dan mac_array.sv
    • Berisi RTL untuk baseline serta sebagian arsitektur systolic array yang diusulkan, yaitu FIP dan FFIP [1], sesuai nilai FIP_METHOD

Dokumentasi tambahan

Bacaan terkait

1 komentar

 
GN⁺ 2024-03-17
Pendapat di Hacker News

  • Kelihatannya cukup keren, tapi apa jebakannya? Misalnya, saya penasaran kenapa ini belum diimplementasikan di akselerator
    Saya penasaran apakah ini benar-benar hanya algoritma yang terlupakan, atau ada batasan yang memengaruhi biaya pembuatan akselerator dan sebagainya

    • Ini bukan sekadar algoritma software sederhana, melainkan optimisasi arsitektur hardware
      Untuk mendapatkan manfaatnya, kita harus membuat hardware yang sesuai dengan dimensi algoritmanya, dan itu keputusan yang mahal
    • Untuk akselerator perkalian matriks fixed-point, menurut saya tidak ada jebakan khusus; ini hanya algoritma yang terlewatkan
      Algoritma ini berbasis algoritma Winograd, dan kebetulan Winograd kemudian juga mengusulkan algoritma terpisah yang menjadi sangat terkenal dalam akselerasi CNN, sehingga algoritma ini mungkin kurang mendapat perhatian. Namun ini hanya dugaan
    • Ada banyak algoritma perkalian matriks, dan masing-masing punya kelebihan serta kekurangan besar
      Selalu ada keseimbangan antara akurasi, waktu eksekusi, dan skalabilitas, dan metode ini kemungkinan akurasinya buruk pada floating-point
    • Tidak sepenuhnya terlupakan
      Ini masih tersisa sampai taraf tertentu di dalam autentikator Wegman-Carter berbasis pseudo-dot-product seperti UMAC. Untuk latar belakangnya, lihat Bab 3 dari [1]
      [1] https://cr.yp.to/antiforgery/pema-20071022.pdf
    • Saya hanya membaca sekilas, jadi mohon koreksi kalau salah; pemahaman saya, ini bukan pengganti perkalian matriks, melainkan metode aproksimasi yang memberi hasil cukup baik untuk jenis sistem linear yang terlihat di AI/ML
      Untuk penggunaan seperti itu, rasanya sudah cukup bagus

  • Ini mengingatkan saya pada upaya mencoba hal serupa pada 2018, yang akhirnya saya hentikan setelah semua lamaran PhD saya ditolak
    https://github.com/ixaxaar/pytorch-dni
    Konsep di sini melangkah lebih jauh: mencoba mereplikasi backpropagation dengan jaringan eksternal, dan berargumen bahwa otak mungkin benar-benar melakukannya seperti itu

    • Saya kurang melihat kaitannya
      Pekerjaan ini adalah optimisasi level rendah untuk perkalian matriks, sedangkan repositori yang ditautkan tampaknya mencoba mengganti gradien hasil backpropagation dengan estimasi yang lebih murah. Saya penasaran apa kemiripan di antara keduanya
    • Ini terasa seperti situasi yang mendekati tidak ada makan siang gratis
      Waktu yang dihemat dengan mengaproksimasi gradien seperti ini sepertinya akan hilang karena dibutuhkan lebih banyak iterasi training akibat turunnya akurasi gradien, bukan begitu?
    • Terlepas dari diskusi teknis, saya penasaran GIF arsitektur itu dibuat dengan apa. Tampilannya bagus

  • Sangat menarik dan layak dibaca. Untuk orang-orang di komentar yang bingung kenapa ini lebih baik, makalahnya membahas sintesis pipeline perkalian matriks di perangkat keras seperti FPGA atau ASIC
    Di CPU atau GPU, waktu penjumlahan dan perkalian umumnya mirip sehingga sulit terasa bedanya, tetapi unit perkalian memakan transistor jauh lebih banyak. Mengurangi kompleksitas rangkaian bisa meningkatkan kecepatan dan throughput paralel, sekaligus menurunkan daya dan kompleksitas wiring. Pendekatan ini bisa sangat berguna khususnya untuk akselerator perkalian matriks sparse yang efisien
    Cara keren lain untuk menghilangkan perkalian dalam perkalian matriks adalah memakai semiring lain [1]. Misalnya Tropical Semiring [2] mengganti perkalian dengan penjumlahan, dan penjumlahan dengan min atau max. Ini tetap perkalian matriks, tetapi operasi binernya berubah. Riset Tropical Algebra [3], bidang yang relatif baru, saat ini cukup aktif dan kaya, serta digunakan dalam berbagai masalah optimisasi dan riset optimisasi jaringan saraf [4]
    Metode ini juga cocok untuk sintesis perangkat keras, karena sebagian besar blok logika yang dapat dikonfigurasi pada FPGA bisa melakukan add/min/max dalam satu clock, sedangkan perkalian yang efisien membutuhkan multiplier perangkat keras on-chip khusus yang fixed
    Semiring lain yang terkait untuk menghapus perkalian secara efisien adalah memakai Log Semiring [5]. Jika probabilitas harus dikalikan secara berantai seperti pada rantai Markov, angkanya cepat menjadi sangat kecil sehingga akurasi floating point menurun. Dengan mengambil log terlebih dahulu untuk melakukan scaling, perkalian menjadi penjumlahan, dan penjumlahan menjadi 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

    • Makalah [4] benar-benar memikat
      Saya hampir pemula di bidang ini, tetapi sepertinya makalah itu menunjukkan bahwa hampir semua jaringan ReLU dapat direpresentasikan sebagai rasio tropical dari dua polinomial tropical, sehingga dapat dianalisis dengan prinsip-prinsip geometris seperti visualisasi permukaan. Makalah itu juga dikutip dalam riset yang lebih baru: https://scholar.google.com/scholar?cites=1003719112553620451... Saya penasaran apakah sudah ada kemajuan berarti di sini
    • Wah, ini persis hal yang dibahas oleh Unified Algebra
      http://www.cs.toronto.edu/~hehner/UA.pdf
    • Bagian bahwa mengambil log untuk menskalakan angka membuat perkalian menjadi penjumlahan dan penjumlahan menjadi x + log1p(exp(y - x)) itu berarti penjumlahan/pengurangan dalam sistem bilangan log jauh lebih mahal daripada perkalian
      Terutama jika memperhatikan hasil pembulatan yang benar, tabel lookup perangkat keras yang dibutuhkan jadi cukup besar
    • Bukankah pendekatan mengambil log untuk mengubah perkalian menjadi penjumlahan ini sama dengan pendekatan GF(2^x) yang sudah dipakai selama puluhan tahun?
      Satu-satunya batasan yang terpikir adalah ukuran field-nya
    • Yang agak terkait adalah number theoretic transform
      https://ieeexplore.ieee.org/abstract/document/1451721

  • Mengejutkan bahwa ini benar-benar bekerja
    Biasanya biaya untuk mendeteksi apakah harus memakai perkalian atau penjumlahan lebih lambat daripada langsung melakukan perkalian. Apalagi saat menjalankan pekerjaan dalam jumlah sangat besar secara paralel

    • Saya penasaran hasilnya akan seperti apa jika dibandingkan dengan OpenBLAS dan cuBLAS

  • Menarik bahwa prosedur yang ditemukan pada 1968 belum digunakan untuk tujuan ini sampai sekarang

    • GF(2^x) juga tidak ada yang tahu akan dipakai untuk apa sampai pertengahan abad lalu
      Ah, kalau dipikir-pikir, ilmu komputer sendiri juga nyaris belum ada sampai pertengahan abad lalu

  • Jika tertarik pada teori matematika di balik algoritma waktu sub-kubik untuk perkalian matriks, bisa mulai dari sini: https://en.wikipedia.org/wiki/Matrix_multiplication_algorith...
    Diduga bahwa untuk setiap bilangan real j > 0, ada suatu n sehingga dua matriks n x n sembarang dapat dikalikan dalam O(n^(2+j)) langkah
    Saat ini sudah dibuktikan untuk 2+j = w = 2.3728596, yaitu j > 0.3728596

    • Saya tidak yakin pernyataan ini benar
      Jika dimulai dengan “untuk setiap j ada suatu n”, maka pada kalimat berikutnya n dan j menjadi konstanta. Jadi itu hanya mengatakan bahwa matriks berukuran konstan bisa dikalikan dalam waktu konstan. Secara teknis benar, tetapi sepertinya maksudnya adalah klaim yang lebih kuat
    • Sepertinya makin lama kemajuannya makin sulit
      Mungkin saja mentok di j=1/e. Saya bahkan tidak akan menyebut ini dugaan; itu cuma konstanta praktis yang berada dekat nilai saat ini. Akan cukup lucu kalau matematika menjahili kita seperti itu
    • Memprediksi bahwa ini berlaku untuk sembarang j > 0 cukup berani
      Bisakah berbagi intuisi kenapa berpikir demikian?

  • README ini sangat buruk dalam menjelaskan apa peningkatannya dan bagaimana jumlah perkalian bisa dikurangi setengahnya.
    Bagaimana dengan waktu eksekusi Big O? Apakah ini mengubah batas optimal yang diketahui?
    Gambarnya juga berantakan dan hampir tidak menjelaskan mengapa pendekatan ini lebih cepat atau lebih baik. Karena itu, saya jadi enggan mengklik sampai ke PDF-nya.
    Kalau ingin meningkatkan kredibilitas proyek, sebaiknya jelaskan dengan jujur dan jelas apa yang sebenarnya terjadi, lalu berikan penjelasan dan diagram yang gamblang alih-alih gambar yang terasa seperti menarik orang dengan hype. Sulit membedakan apakah ini terobosan besar atau bukan apa-apa. Sayangnya, ini juga terasa seperti pilihan yang disengaja untuk memanfaatkan demam AI. Alternatif yang lebih ingin saya percayai adalah bahwa penulisnya hanya perlu memperbaiki dan memberikan konteks yang lebih baik.

    • Untuk pertanyaan “Bagaimana waktu eksekusi Big O-nya?”, klaimnya adalah mengurangi jumlah perkalian setengahnya, jadi tidak berpengaruh pada Big O.
      Matematika untuk mengurangi jumlah perkalian setengahnya dalam makalah (https://arxiv.org/abs/2311.12224) tidak sulit dipahami. Cukup baca Persamaan 2 untuk perkalian matriks tradisional dan Persamaan 3–6.
      Tampaknya jelas bahwa sebagai gantinya, sesuai yang diiklankan, jumlah perkalian dikurangi setengahnya dengan menambahkan banyak penjumlahan/pengurangan. Setelah itu, mereka memvektorisasi algoritma tersebut dengan lebih baik, dan seperti biasanya pekerjaan semacam ini cepat menjadi rumit.
      Kekhawatiran utama saya adalah stabilitas numerik.
    • README-nya tidak banyak menjelaskan, tetapi bagian pendahuluan makalahnya sendiri cukup mudah diakses.
      Soal apakah ini revolusioner, menurut saya ini adalah peningkatan faktor konstan yang rapi dan bisa langsung diterapkan pada akselerator fixed-point dengan batasan area. Ini tidak akan mengubah semuanya dalam semalam, tetapi juga bukan sesuatu yang tidak berarti. Ini pekerjaan yang bagus.
    • Saya tidak ingin terdengar elitis, tetapi saya sama sekali tidak mengerti inti komentar ini.
      Jika Anda tidak memahami notasi Big O sampai tidak tahu bahwa “mengurangi perkalian setengahnya” tidak mengubah Big O, saya tidak tahu mengapa Anda menanyakannya.