Mengungguli perkalian matriks NumPy dengan 150 baris kode C

 (salykova.github.io)
1 poin oleh GN⁺ 2024-07-05 | 1 komentar | Bagikan ke WhatsApp
  • Perkalian matriks NumPy bergantung pada library BLAS eksternal, tetapi implementasi ini bertujuan membawa performa single-thread dan multithread hingga setara BLAS hanya dengan C murni serta FMA3·AVX2
  • Inti performanya adalah struktur yang membagi $C$ menjadi blok-blok kecil, lalu microkernel 16×6 mengulang rank-1 update di dalam register YMM untuk mengurangi akses memori
  • Pada matriks berukuran arbitrer, penanganan batas mudah menjadi bottleneck, sehingga implementasi ini menggabungkan mask store dan buffer zero padding untuk menghindari penurunan performa akibat mask load
  • Reuse cache diperoleh melalui blocking k_c, m_c, n_c, dan performa puncak aktual sangat bergantung pada tuning jumlah thread, ukuran kernel, dan ukuran tile
  • AVX-512 dikecualikan demi dukungan CPU yang lebih luas, sehingga pada CPU AVX-512 BLAS bisa lebih cepat; perbandingan dengan OpenBLAS juga dilakukan dengan AVX-512 dimatikan

Tujuan implementasi dan pembanding

  • Kode implementasinya dipublikasikan di sgemm.c, dan mengoptimalkan perkalian matriks FP32 multithread pada prosesor modern
  • NumPy bergantung pada library BLAS eksternal untuk operasi aljabar linear seperti perkalian matriks
    • Contohnya Intel MKL, Accelerate, BLIS, GotoBLAS, dan OpenBLAS
    • OpenBLAS, GotoBLAS, dan BLIS ditulis dalam C/FORTRAN/Assembly, serta mencakup implementasi perkalian matriks yang dioptimalkan manual untuk tiap mikroarsitektur CPU
  • Tujuannya adalah implementasi perkalian matriks yang ditulis dalam C murni tanpa assembly tingkat rendah, tetapi tetap memenuhi syarat berikut
    • Berjalan pada ukuran matriks arbitrer
    • Berjalan pada prosesor x86-64 modern
    • Bersaing dengan library BLAS yang ada
    • Kodenya sederhana dan mudah diperluas
  • Referensinya adalah Fast Multidimensional Matrix Multiplication on CPU from Scratch oleh Simon Boehm, Matrix Multiplication oleh Sergey Slotin, Can you multiply a matrix? oleh Geohot, serta makalah terkait GotoBLAS dan BLIS

Kondisi benchmark dan perhitungan FLOPS

  • Lingkungan pengujian adalah AMD Ryzen 7 9700X, 32GB DDR5 6000 MHz CL36, OpenBLAS 0.3.26, GCC 13.3, Ubuntu 24.04.1 LTS
  • Flag kompilasi yang digunakan adalah -O3 -march=native -mno-avx512f -fopenmp
  • Untuk perbandingan yang adil, saat menginstal OpenBLAS perlu menetapkan TARGET yang sesuai dan menonaktifkan instruksi AVX-512
    • Prosesor Zen4/5 dikompilasi dengan make TARGET=ZEN
    • Jika tidak, OpenBLAS akan menggunakan instruksi AVX-512 secara default
  • Perkalian matriks FP32 OpenBLAS dijalankan melalui API cblas_sgemm
  • Benchmark menargetkan matriks persegi
    • Dievaluasi dari m=n=k=200 hingga m=n=k=10000 dengan interval 200
    • Perkalian matriks diulang n_iter kali, dan waktu eksekusi median digunakan untuk pengukuran performa
  • Jika matriks $A$ berukuran $M \times K$ dikalikan dengan matriks $B$ berukuran $K \times N$, total jumlah operasinya adalah $2MNK$ FLOP
    • Performa dihitung dengan FLOPS=(2*m*n*k)/exec_time

Batas teoretis dan basis SIMD

  • CPU x86-64 modern memproses banyak data secara paralel dengan ekstensi SIMD
  • Instruksi utamanya adalah AVX2 dan FMA
    • Keduanya menggunakan register YMM 256-bit
    • Setiap register YMM dapat menampung 8 float 32-bit
  • Instruksi FMA VFMADD231PS menjalankan operasi packed single berbentuk YMM1 = YMM2 * YMM3 + YMM1
  • Pada Ryzen 9700X, throughput fused multiply-add adalah 0,5 cycle/instruction, yakni 2 instruksi per siklus
  • Secara teoretis, Ryzen 9700X dapat menjalankan 32 FLOP per siklus pada satu core
    • Rumusnya adalah 8 floats × 2(add+mul) × 2(1/TP)
    • Dengan asumsi clock berkelanjutan 4,7GHz pada 8 core, peak teoretis multithread diperkirakan 1203 FLOPS

Implementasi dasar dan microkernel

  • Matriks disimpan dalam urutan column-major
    • A[row][col] diakses pada pointer C sebagai ptr[col*M + row]
  • Implementasi paling sederhana menelusuri semua baris dan kolom $C$, lalu menghitung dot product baris $A$ dan kolom $B$ untuk tiap elemen
  • Inti implementasi berperforma tinggi adalah microkernel yang membagi $C$ menjadi submatriks $m_R \times n_R$ dan menghitung tiap submatriks secara efisien
  • Kernel menginisialisasi $\bar{C}$ di register dengan 0, lalu beriterasi sepanjang dimensi $K$
    • Mengambil vektor kolom $\bar{A}$ dan vektor baris $\bar{B}$ ke register
    • Menghitung outer product dari kedua vektor dan menambahkannya ke akumulator $\bar{C}$
    • Tiap langkah adalah rank-1 update
  • Cara ini mengurangi jumlah elemen yang diambil ke register menjadi $(m_R+n_R)K$, dibandingkan akses memori metode naive sebesar $2K m_R n_R$
  • CPU AVX memiliki 16 register YMM, sehingga ukuran kernel harus memenuhi batasan berikut
    • $(m_R/8) \cdot n_R + m_R/8 + 1 \le 16$
    • $m_R$ harus kelipatan 8
  • Secara teoretis, makin besar dan makin setara nilai $m_R$ dan $n_R$, makin besar pengurangan akses memori; tetapi pada Ryzen 9700X aktual, kernel 16×6 menunjukkan performa terbaik
  • Implementasi menggunakan intrinsic dari immintrin.h
    • __m256 adalah tipe vektor 256-bit dan merepresentasikan isi register YMM
    • _mm256_loadu_ps memuat vektor kolom A
    • _mm256_broadcast_ss melakukan broadcast nilai skalar B menjadi vektor berisi 8 float
    • _mm256_fmadd_ps memperbarui akumulator
    • _mm256_storeu_ps menyimpan hasil ke memori
  • Assembly yang dihasilkan mencakup instruksi SIMD FMA seperti vfmadd231ps dan vbroadcastss

Padding untuk matriks berukuran arbitrer

  • Kernel dasar 16×6 langsung bekerja saat $M$ dan $N$ masing-masing merupakan kelipatan 16 dan 6
  • Jika jumlah kolom $n$ di area batas kurang dari 6, loop penyimpanan hanya dijalankan hingga j < n
  • Jika jumlah baris $m$ kurang dari 16, _mm256_storeu_ps menyimpan 8 elemen sekaligus, sehingga diperlukan mask store
    • _mm256_maskstore_ps hanya menyimpan elemen memori yang bit mask-nya aktif
    • Mask dibuat berdasarkan jumlah baris yang bertumpang tindih, yaitu $m$
  • Jika load di area batas juga ditangani dengan _mm256_maskload_ps, performa kernel bisa turun besar
    • Instruksi tambahan untuk menghitung mask menambah overhead
    • Karena $n$ bukan konstanta compile-time, compiler sulit melakukan unroll loop secara efisien
  • Sebagai gantinya, jika $m \neq m_R$, $\bar{A}$ disalin ke buffer dan diberi padding 0; jika $n \neq n_R$, $\bar{B}$ juga disalin ke buffer dan diisi 0
  • Implementasi terkait ada di matmul_pad.h

Cache blocking dan reuse data

  • Di antara register dan DRAM terdapat hierarki cache CPU, dan CPU desktop modern biasanya menggunakan cache L1, L2, dan L3
  • Cache lebih cepat daripada DRAM tetapi kapasitasnya terbatas, sehingga tidak mungkin memasukkan seluruh $A$, $B$, dan $C$ ke cache
  • Cara membagi matriks menjadi blok-blok kecil, menaruhnya di cache, lalu menggunakan ulang data yang sama pada banyak rank-1 update disebut cache blocking atau tiling
  • Cache blocking single-thread berbentuk loop 5 tingkat yang mirip struktur BLIS
    • Loop terluar membuat blok $C_j$ dan $B_j$ sepanjang dimensi $N$
    • Loop berikutnya membuat blok $A_j$ dan $B_p$ sepanjang dimensi $K$
    • $B_p$ dipacking menjadi $\tilde{B}_p$, dan jika perlu diberi padding 0 untuk reuse cache L3
    • Loop berikutnya membuat blok $C_i$ dan $A_j$ sepanjang dimensi $M$, dan $A_j$ dipacking menjadi $\tilde{A}_j$
    • Dua loop terakhir membagi blok cache menjadi panel $m_R \times k_c$ dan $k_c \times n_R$, lalu meneruskannya ke kernel
  • $\tilde{A}_j$ dan $\tilde{B}_p$ yang sudah dipacking disimpan secara berbeda
    • Panel internal $\tilde{A}_j$ disimpan secara column-major
    • Panel internal $\tilde{B}_p$ disimpan secara row-major
  • Parameter cache blocking perlu disesuaikan dengan ukuran cache tiap model CPU
    • $k_c \times n_c$ menjadi titik awal untuk mengisi cache L3
    • $m_c \times k_c$ menjadi titik awal untuk mengisi cache L2
    • $k_c \times n_R$ menjadi titik awal untuk mengisi cache L1
  • Dalam praktiknya, nilai yang lebih besar daripada nilai teoretis sering memberi performa lebih baik, dan karena CPU mengelola penempatan cache secara otomatis, loop dan pola akses perlu dirancang pada level algoritme
  • Implementasinya ada di matmul_cache.h

Optimisasi mikro kernel

  • Alih-alih mendefinisikan akumulator sebagai array seperti __m256 C_buffer[6][2], variabel akumulator dideklarasikan dengan diuraikan secara eksplisit
  • Cara ini membantu GCC mengoptimalkan kode dengan lebih baik dan menghindari register spilling
  • Perhitungan mask juga diubah agar menggunakan instruksi vektor
    • Menggunakan array statis mask[32] serta _mm256_cvtepi8_epi32 dan _mm_loadu_si64
  • Implementasi tersebut ada di matmul_micro.h

Strategi multithreading

  • Target paralelisasi adalah operasi aritmetika dan packing
  • Loop ke-5, ke-4, dan ke-3 di luar microkernel beriterasi dalam satuan ukuran blok cache
    • Agar semua thread tetap sibuk, jumlah iterasi harus setidaknya sama dengan jumlah thread
    • Dimensi matriks input kira-kira harus minimal jumlah thread × ukuran blok cache
  • Ukuran blok cache yang menunjukkan performa baik pada single-thread Ryzen 9700X adalah $n_c=1535$, $m_c=1024$
    • Untuk memanfaatkan seluruh 8 core, diperlukan dimensi ukuran minimal $\max(m_c,n_c) \times 8 = 1535 \times 8 = 12280$
  • Sebaliknya, dua loop terakhir mengiterasi blok kecil $m_R$, $n_R$, sehingga cocok untuk paralelisasi
    • Umumnya $m_R$ dan $n_R$ kurang dari 20
    • Jika $m_c$ dan $n_c$ dipilih sebagai kelipatan jumlah core, pekerjaan dapat dibagi merata
  • Pada Ryzen 9700X, pendekatan yang memparalelkan dua loop internal bersama dengan #pragma omp parallel for collapse(2) num_threads(NTHREADS) menghasilkan performa terbaik
  • Pada prosesor dengan banyak core, terutama lingkungan dengan lebih dari 16 core, paralelisme bertingkat dan paralelisasi 2–3 loop dapat dipertimbangkan
  • Packing $\tilde{A}$ dan $\tilde{B}$ juga diparalelkan dengan OpenMP
    • pack_blockA diparalelkan dengan menelusuri mc dalam satuan MR
    • pack_blockB diparalelkan dengan menelusuri nc dalam satuan NR
  • Parameter yang menunjukkan performa baik pada implementasi multithread di Ryzen 9700X adalah sebagai berikut
    • $m_c = m_R \times \text{number of threads} \times 5$
    • $n_c = n_R \times \text{number of threads} \times 50$
  • Implementasi multithread final ada di matmul_parallel.h

Bacaan terkait

1 komentar

 
GN⁺ 2024-07-05
Komentar Hacker News

  • Jika inti tulisan ini adalah bahwa biasanya masih ada ruang untuk peningkatan performa, maka justru besarnya peningkatan yang mungkin terjadi cenderung diremehkan. Ini tetap berlaku meski upaya yang masuk ke library perkalian matriks jauh lebih besar daripada kebanyakan software lainnya.
    Jika kodenya belum benar-benar sangat dioptimalkan, peningkatan 10–1000x atau lebih dari kode yang ada sering terjadi tanpa usaha besar. Secara kasar menurut urutan pentingnya, yang paling utama adalah apakah pilihan algoritmanya tepat dan apakah pekerjaannya sendiri bisa dihilangkan; setelah itu, besar juga dampak dari mengurangi kerja berat seperti bolak-balik ke kernel atau malloc.
    Vektorisasi memang bisa memakai intrinsic vektor eksplisit, tetapi sering kali cukup dengan menyusun ulang data dari array of structs menjadi struct of arrays/arrays agar menghasilkan kode mesin yang sama. Efisiensi cache juga penting, dan pada kode paralel ini menjadi lebih rumit ketika isolasi data per thread tidak terjaga, misalnya karena false sharing. Terakhir, optimasi spesifik perangkat keras seperti intrinsic atau assembly yang ditulis tangan juga dimungkinkan

    • Dampak jaringan juga tidak boleh dilupakan. Suatu kali saya menemukan kueri terdistribusi yang mengambil sekitar 1 juta baris lewat jaringan lalu melakukan join dan hanya menyisakan 5–10 baris, dan itu menghasilkan peningkatan performa ratusan kali lipat.
      Begitu kuerinya diubah agar join terjadi di server jarak jauh dan hanya 5–10 baris yang dikirim lewat jaringan, performanya langsung naik. Overhead tetap dan latensi memang selalu ada, tetapi jika Anda mengirim data jauh lebih banyak daripada yang dibutuhkan melalui koneksi jaringan, performa pada akhirnya akan hancur. Tulisan “It's the latency, stupid” tentang dampak latensi juga layak dibaca: http://www.stuartcheshire.org/rants/latency.html
      Secara keseluruhan saya setuju dengan pertimbangan-pertimbangan di atas dan urutannya secara kasar
    • “Apakah pilihan algoritmanya tepat” pada praktiknya juga punya sisi yang sudah berubah menjadi cargo cult. Algoritma yang “lebih cepat” kadang punya konstanta nyata yang sangat buruk, sehingga pendekatan yang melakukan lebih banyak kerja justru sering memberi performa lebih baik.
      Banyak wawancara kerja akhirnya berubah menjadi kuis hafalan algoritma yang obscure dengan alasan “karena Google melakukannya”, alih-alih melihat apakah kandidat bisa menalar mengapa implementasinya lambat, mem-benchmark, lalu memperbaikinya

  • Pola coding yang umum sering tidak cukup terspesialisasi untuk perangkat keras sehingga menyisakan banyak performa. Tulisan ini adalah contoh yang menarik, dan demonstrasi klasik lainnya adalah “There's plenty of room at the top”.
    https://www.science.org/doi/10.1126/science.aam9744

  • Untuk memahami hal ini, makalah-makalah di repositori BLIS adalah rujukan yang paling mendekati sumber utama. Saya tidak tahu mengapa ada yang mengira BLAS yang dioptimalkan tidak menghasilkan performa bagus; untuk matriks yang cukup besar, Anda seharusnya bisa mengharapkan lebih dari 90% puncak CPU.
    Terakhir kali saya melihat, OpenBLAS serial umumnya mirip dengan MKL, dan BLAS mengimplementasikan GEMM, bukan matmul, sebagai blok dasar aljabar linear. Saya juga kurang paham mengapa memakai numpy alih-alih framework benchmark, dan di Zen menurut saya perbandingannya seharusnya dengan BLAS milik AMD, yaitu implementasi berbasis BLIS. Dulu BLIS tampaknya punya cerita yang lebih baik soal paralelisasi dibanding OpenBLAS, dan AMD BLIS juga punya pergantian implementasi untuk dimensi “kecil”, meski saya tidak tahu apakah itu sekarang ada di OpenBLAS.
    Vektorisasi micro-kernel tidak selalu membutuhkan intrinsic SIMD; compiler C yang bagus bisa melakukan vektorisasi penuh sekaligus unrolling loop. Micro-kernel C murni di BLIS, dengan ukuran blok yang sesuai, mencapai lebih dari 80% performa dibanding implementasi Haswell yang dioptimalkan manual. Perbedaannya mungkin karena prefetch, tetapi saya sendiri tidak memahaminya dengan tepat

    • Intrinsic SIMD dan unrolling loop manual memang jelas diperlukan. Itulah sebabnya semua library BLAS melakukan vektorisasi dan unrolling loop secara manual.
      Compiler modern pun masih belum bisa melakukan auto-vectorization dan loop unrolling dengan benar dengan tingkat keberhasilan 100%

  • Tulisannya dan implementasinya terlihat bagus, tetapi saya penasaran apa sebenarnya “rahasianya”. OpenBLAS sudah dioptimalkan dengan assembly+C selama puluhan tahun tepat untuk masalah ini, jadi bagaimana bisa dikalahkan?
    Penjelasannya banyak membahas caching dan semacamnya; saya penasaran apakah BLAS memang tidak memanfaatkan hal-hal seperti itu, atau apakah ini lebih disetel untuk prosesor tertentu

    • OpenBLAS memang tidak sampai seoptimal itu untuk arsitektur modern tertentu. Matriksnya juga tidak terlalu besar, dan numpy punya overhead cffi.
      Perbedaan performanya jauh lebih menonjol pada throughput puncak daripada throughput rata-rata, padahal hampir tidak ada aplikasi yang benar-benar mementingkan nilai puncak. Kode benchmark yang ditampilkan tampaknya membuat sisi numpy melewati allocator Python sementara implementasi C tidak, jadi tempat pertama yang perlu dicek adalah kemungkinan kesalahan atau ketidaksesuaian microbenchmark. Banyak rutin numpy mendukung operasi in-place, jadi sepertinya perlu melihat benchmark versi in-place secara eksplisit di kedua sisi.
      Numpy juga punya pengecekan batas dan penanganan error yang berjalan terlepas dari implementasi di bawahnya, dan ini menjadi alasan mengapa untuk matriks kecil ia bisa jauh lebih lambat bahkan dibanding list Python murni. Jika ditambah beberapa ribu siklus overhead murni, memang sulit membuatnya cepat.
      Implementasi ini adalah pendekatan yang cukup disiplin untuk menjenuhkan cache yang relevan, dan dalam arti tertentu memang sudah jelas, tetapi perbaikan engineering yang gamblang seperti ini tetap layak ditekankan dalam diskusi seperti ini. OpenBLAS memang sudah mengerahkan banyak tenaga, tetapi kecil kemungkinan mereka sudah memikirkan semuanya. Untuk menjelaskannya dengan benar, perlu analisis mendalam terhadap kode di kedua sisi
    • Mengalahkan OpenBLAS bukan sesuatu yang mengejutkan dan juga bukan tanpa preseden. Misalnya, library aljabar linear Mir untuk bahasa D juga pernah melakukannya beberapa tahun lalu [1]
      Untuk implementasi C++ dan C, lihat saja pendekatan metaprogramming [2], [3]. Yang benar-benar mengejutkan adalah banyak bahasa modern seperti Matlab, Julia, dan Mojo masih bergantung pada OpenBLAS, walaupun tentu masing-masing punya alasannya
      [1] Numeric age for D: Mir GLAS is faster than OpenBLAS and Eigen (2016):
      http://blog.mir.dlang.io/glas/benchmark/openblas/2016/09/23/...
      [2] Vastly outperforming LAPACK with C++ metaprogramming (2018):
      https://wordsandbuttons.online/vastly_outperforming_lapack_w...
      [3] Outperforming LAPACK with C metaprogramming (2018):
      https://wordsandbuttons.online/outperforming_lapack_with_c_m...
    • -march=native bisa memberi keuntungan karena mengompilasi sesuai model CPU yang tepat. Numpy kemungkinan besar dikompilasi untuk target x86-64 yang lebih umum dan lebih lama.
      Pada CPU Ryzen, -march=native mungkin memakai v4, sedangkan numpy tampaknya menargetkan v1 atau v2.
      https://en.wikipedia.org/wiki/X86-64#Microarchitecture_level...
    • numpy 2.0 mengintegrasikan Google highway untuk memanfaatkan SIMD dengan lebih baik di berbagai mikroarsitektur, jadi perbandingan di sisi numpy kemungkinan akan membaik

  • Tulisannya juga bagus dan keputusan untuk membuat benchmark-nya mudah direproduksi sangat patut diapresiasi. Pada Xeon W-2245 16-core 3.90GHz saya, matmul.c menjalankan perkalian matriks 8192x8192 dalam 1,41 detik dengan gcc -O3, 1,47 detik dengan clang -O2, sedangkan NumPy mencatat 1,07 detik.
    Menurut saya kernel AVX-512 akan jauh lebih cepat. Alasan lain performanya kurang maksimal mungkin OpenMP; berdasarkan pengalaman saya, mengelola thread pool secara eksplisit dengan pthreads bisa mengurangi overhead. Juga lebih baik memakai sysconf(_SC_NPROCESSORS_ONLN) daripada hardcode jumlah CPU

  • Tidak ada alasan memberi beban yang berbeda jika yang satu Python dan yang lain C. Keduanya bisa saja ditulis dalam C, satu memanggil library BLAS dan yang lain memanggil implementasi ini, sehingga perbandingannya benar-benar apple-to-apple

    • Di sini memang tepat untuk membandingkan dengan Python. Itu karena cara paling populer saat ini untuk melakukan komputasi seperti ini adalah Python dengan numpy.
      Overhead-nya memang tidak terlalu besar, tetapi seperti juga disebut orang lain di thread ini, yang penting adalah memanggilnya dengan benar. Mempertemukan kode numpy yang naif dengan kode C yang sudah dituning jelas bukan perbandingan yang adil

  • Ini bukan jalur panas, tetapi inefisiensi pembuatan mask, yaitu penggunaan bit_mask, cukup mengganggu. Cara yang lebih efisien adalah membuat array konstanta global berbentuk {-1,-1,...,0,0,...} lalu memuatnya pada offset elemen 16-m, 8-m, atau membandingkan vektor konstanta {0,1,2,3,4,...} dengan m yang dibroadcast serta m-8
    Namun ini hanya berlaku untuk satu kolom matriks, dan loop maskload/maskstore sesudahnya memakan waktu jauh lebih lama, jadi ini cuma kritik kecil. Terutama penyimpanan masih lambat bahkan di Zen 4[1], dan instruksi AVX-512 6 kali lebih cepat meskipun perbedaannya hanya menerima mask dari register mask. clang toh akan mengauto-vektorisasi shift, jadi kemungkinan hanya sekitar 2~3 kali lebih lambat daripada usulan saya
    [1]: https://uops.info/table.html?search=vmaskmovps&cb_lat=on&cb_...

    • Saya penulisnya. Optimisasi kode C dan penggunaan intrinsic benar-benar masih baru bagi saya, jadi saya bukan ahli di bidang ini, tetapi saya ingin belajar lebih banyak
      Saya sangat menghargai masukan yang memberi sudut pandang baru. Untuk “membuat dan memuat array konstanta global”, kalau saya ingat saat diuji hasilnya sedikit lebih lambat daripada shift bit mask, tetapi untuk memastikannya saya akan mengujinya lagi. Metode “membandingkan vektor konstanta {0, 1, 2, 3, 4, ...} dengan m yang dibroadcast dan m-8” adalah ide bagus, jadi akan saya coba
    • Saat membuat array konstanta global, elemennya bisa dibuat sebagai int8_t, lalu saat memuat byte-nya bisa di-sign-extend menjadi int32_t. Kombinasi _mm_loadu_si64 / _mm256_cvtepi8_epi32 akan dikompilasi menjadi satu instruksi vpmovsxbd yang menggunakan operan memori
      Dengan begitu, jika disejajarkan dengan benar memakai alignas(32), seluruh array konstanta akan muat dalam satu cache line. Pada kasus penggunaan di artikel asli diperlukan dua mask, jadi instruksi vpmovsxbd kedua pasti menjadi cache hit L1D sehingga cocok sekali

  • Bagaimana dengan tinyBLAS buatan jart
    https://hacks.mozilla.org/2024/04/llamafiles-progress-four-m...
    dan https://justine.lol/matmul/

    • Kemarin saya sempat berdiskusi intens dengan Justine, dan di workstation itu implementasi ini tampaknya setidaknya 2 kali lebih cepat daripada tinyBLAS. Diskusi lengkapnya ada di Mozilla AI Discord: https://discord.com/invite/NSnjHmT5xY

  • Selain untuk benchmark, apa alasan memultithread perkalian matriks itu sendiri. Dalam praktik nyata, bukankah lebih menguntungkan jika algoritme yang memakai perkalian itu yang menggunakan multithreading

    • Di HPC memang biasanya begitu. Namun, hanya dengan mengganti ke BLAS paralel saja sudah bisa membantu jenis kode R tertentu dengan mudah
      Tetapi kode HPC biasanya GEMM bukan bottleneck-nya

  • Saya baru sempat membaca sekilas, tetapi tulisan ini penuh detail dan penjelasan. Kelihatannya ini artikel yang cukup bagus dalam menjelaskan bagaimana perkalian matriks cepat diimplementasikan dengan mempertimbangkan aspek arsitektur, jadi saya masukkan ke daftar bacaan