Mengungguli perkalian matriks NumPy dengan 150 baris kode C

 (salykova.github.io)
1 poin oleh GN⁺ 2024-07-05 | 1 komentar | Bagikan ke WhatsApp

Ringkasan

Pengantar

  • Perkalian matriks merupakan elemen penting dalam jaringan saraf modern
  • NumPy mencapai kinerja tinggi dengan menggunakan pustaka BLAS eksternal
  • Artikel ini menjelaskan cara mengimplementasikan perkalian matriks berperforma tinggi yang sederhana, portabel, dan dapat diskalakan

Kinerja NumPy

  • NumPy menggunakan OpenBLAS pada CPU AMD
  • Pengukuran kinerja dihitung dalam FLOP/s
  • Kinerja NumPy single-thread dan multi-thread diukur pada CPU Ryzen 7 7700

Batas teoretis

  • Menjelaskan hierarki memori CPU dan ekstensi SIMD
  • Secara teoretis, dapat mencapai 163 GFLOPS pada single-thread dan 1203 GFLOPS pada multi-thread

Implementasi sederhana

  • Menjelaskan algoritme dasar perkalian matriks dan mengukur kinerja implementasi sederhana
  • Implementasi sederhana mencapai 2.7 GFLOPS

Kernel

  • Menjelaskan cara menyelesaikan perkalian matriks dengan membaginya menjadi submasalah kecil
  • Mengoptimalkan kernel menggunakan instruksi SIMD
  • Mencapai 147 GFLOPS dengan kernel 16x6

Masking dan packing

  • Menjelaskan cara menangani kasus batas untuk memproses ukuran matriks sembarang
  • Mengoptimalkan kinerja dengan masking dan packing
  • Implementasi baru mencapai 56 GFLOPS

Caching

  • Menjelaskan sistem memori cache CPU
  • Mengoptimalkan penggunaan ulang data dan pengelolaan cache dengan memanfaatkan cache CPU

Opini GN⁺

  • Artikel ini sangat edukatif karena menjelaskan langkah demi langkah cara mengimplementasikan perkalian matriks berperforma tinggi
  • Anda dapat mempelajari metode optimasi yang memanfaatkan instruksi SIMD dan cache CPU
  • Membantu memahami cara kerja internal pustaka seperti NumPy
  • Proyek lain dengan fungsi serupa antara lain Intel MKL, OpenBLAS, dan lainnya
  • Saat mengadopsi teknologi baru atau open source, perlu mempertimbangkan kinerja dan portabilitas

Bacaan terkait

1 komentar

 
GN⁺ 2024-07-05
Komentar Hacker News

  • Sebagian besar software tidak dioptimalkan, jadi masih banyak ruang untuk peningkatan performa

    • Pemilihan algoritme adalah yang paling penting
    • Perlu dicek apakah pekerjaan berat seperti pemanggilan kernel bisa dikurangi
    • Performa bisa ditingkatkan melalui vektorisasi
    • Perlu dicek apakah efisiensi cache bisa dioptimalkan
    • Perlu ditinjau kemungkinan optimasi yang spesifik untuk hardware

  • Makalah yang dirujuk di repositori BLIS adalah referensi otoritatif untuk memahami topik ini

    • Tidak paham alasan mengapa ada yang menganggap BLAS yang dioptimalkan performanya buruk
    • Sebaiknya menggunakan BLAS milik AMD alih-alih numpy
    • BLIS memiliki paralelisasi yang lebih baik daripada OpenBLAS

  • Instruksi SIMD tidak diperlukan untuk vektorisasi micro-kernel

    • Dengan ukuran blok yang tepat, micro-kernel C murni milik BLIS dapat mencapai lebih dari 80% performa implementasi yang dioptimalkan secara manual

  • Sebagian besar pola coding tidak sepenuhnya spesifik terhadap hardware, sehingga banyak performa yang terlewat

    • Layak merujuk pada makalah klasik ilmu komputer "There's plenty of room at the top"

  • Patut diapresiasi karena benchmark dibuat mudah untuk diulang

    • Pada CPU Xeon 16-core, matmul.c membutuhkan 1,41 detik saat dikompilasi dengan gcc -O3, 1,47 detik saat dikompilasi dengan clang -O2, dan NumPy membutuhkan 1,07 detik
    • Diperkirakan kernel avx512 akan lebih cepat
    • Menggunakan pthreads alih-alih omp dan mengelola thread pool secara eksplisit dapat mengurangi overhead

  • Diragukan apakah implementasi numpy benar-benar menggunakan multithreading

  • Ingin tahu mengapa performanya lebih baik daripada OpenBLAS

    • Membahas detail seperti caching
    • Ingin tahu apakah ini lebih dioptimalkan untuk prosesor tertentu

  • Membandingkan Python di satu sisi dan C di sisi lain tidak adil

    • Akan lebih baik jika keduanya ditulis dalam C lalu dibandingkan

  • Inefisiensi dalam pembuatan mask terasa mengganggu

    • Ada metode yang lebih efisien seperti membuat array konstanta global atau membandingkannya dengan vektor konstanta
    • Namun ini masalah kecil, dan pada praktiknya kemungkinan tidak akan banyak berbeda

  • Meragukan kepraktisan melakukan multithreading pada perkalian matriks itu sendiri

    • Multithreading akan lebih berguna pada algoritme yang menggunakan perkalian matriks

  • Menyebut tinyBLAS milik jart

    • Menyediakan tautan terkait