150 satırlık C koduyla NumPy matris çarpımını geçmek

 (salykova.github.io)
1 puan yazan GN⁺ 2024-07-05 | 1 yorum | WhatsApp'ta paylaş
  • NumPy’nin matris çarpımı dış BLAS kütüphanelerine dayanırken, bu uygulama yalnızca saf C ile FMA3 ve AVX2 kullanarak tek iş parçacıklı ve çok iş parçacıklı performansı BLAS seviyesine çıkarmayı hedefliyor
  • Performansın merkezinde, $C$ matrisini küçük bloklara bölmek ve 16×6 mikroçekirdeğin YMM yazmaçları içinde rank-1 update işlemlerini tekrarlayarak bellek erişimini azaltması yer alıyor
  • Rastgele boyutlu matrislerde sınır işleme kolayca darboğaz olabilir; bunu önlemek için maskeli depolama ile 0 dolgulu tamponlar birleştirilerek maskeli yüklemenin performans kaybından kaçınılıyor
  • Önbellek yeniden kullanımı k_c, m_c, n_c bloklamasıyla sağlanıyor ve gerçek tepe performans büyük ölçüde iş parçacığı sayısı, çekirdek boyutu ve tile boyutu ayarlarına bağlı oluyor
  • Daha geniş CPU desteği için AVX-512 dışarıda bırakıldığı için AVX-512 destekli CPU’larda BLAS daha hızlı olabilir; OpenBLAS karşılaştırması da AVX-512 kapalı koşulda yapılıyor

Uygulamanın hedefi ve karşılaştırma noktaları

  • Uygulama kodu sgemm.c içinde yayımlanmış durumda ve modern işlemcilerde çok iş parçacıklı FP32 matris çarpımını optimize ediyor
  • NumPy, matris çarpımı gibi doğrusal cebir işlemlerinde harici BLAS kütüphanelerine bağımlı
    • Örnek olarak Intel MKL, Accelerate, BLIS, GotoBLAS ve OpenBLAS veriliyor
    • OpenBLAS, GotoBLAS ve BLIS; C/FORTRAN/Assembly ile yazılıyor ve CPU mikro mimarisine göre elle optimize edilmiş matris çarpımı uygulamaları içeriyor
  • Amaç, düşük seviyeli assembly kullanmadan saf C ile yazılmış ama yine de şu koşulları sağlayan bir matris çarpımı uygulaması oluşturmak
    • Rastgele matris boyutlarında çalışması
    • Modern x86-64 işlemcilerde çalışması
    • Mevcut BLAS kütüphaneleriyle rekabet etmesi
    • Kodun basit ve genişletmeye uygun olması
  • Başvuru kaynakları arasında Simon Boehm’in Fast Multidimensional Matrix Multiplication on CPU from Scratch, Sergey Slotin’in Matrix Multiplication, Geohot’un Can you multiply a matrix? ve GotoBLAS·BLIS ile ilgili makaleler yer alıyor

Benchmark koşulları ve FLOPS hesabı

  • Test ortamı AMD Ryzen 7 9700X, 32GB DDR5 6000 MHz CL36, OpenBLAS 0.3.26, GCC 13.3 ve Ubuntu 24.04.1 LTS’ten oluşuyor
  • Derleme bayrakları olarak -O3 -march=native -mno-avx512f -fopenmp kullanılıyor
  • Adil bir karşılaştırma için OpenBLAS kurulurken uygun TARGET ayarlanmalı ve AVX-512 komutları devre dışı bırakılmalı
    • Zen4/5 işlemciler için make TARGET=ZEN ile derleniyor
    • Aksi halde OpenBLAS varsayılan olarak AVX-512 komutlarını kullanıyor
  • OpenBLAS FP32 matris çarpımı cblas_sgemm API’si üzerinden çalıştırılıyor
  • Benchmark kare matrisler üzerinde yapılıyor
    • m=n=k=200 değerinden m=n=k=10000 değerine kadar 200 adımlarla ölçüm yapılıyor
    • Matris çarpımı n_iter kez tekrarlanıyor ve performans ölçümü için medyan çalışma süresi kullanılıyor
  • $M \times K$ boyutlu $A$ matrisi ile $K \times N$ boyutlu $B$ matrisi çarpıldığında toplam işlem miktarı $2MNK$ FLOP oluyor
    • Performans FLOPS=(2*m*n*k)/exec_time ile hesaplanıyor

Teorik sınırlar ve SIMD temeli

  • Modern x86-64 CPU’lar, birden fazla veriyi paralel işlemek için SIMD genişletmelerini kullanıyor
  • Başlıca komutlar AVX2 ve FMA
    • Her ikisi de 256 bitlik YMM yazmaçlarını kullanıyor
    • Her YMM yazmacı 32 bitlik 8 adet float tutabiliyor
  • FMA komutu VFMADD231PS, YMM1 = YMM2 * YMM3 + YMM1 biçiminde packed single işlemi yapıyor
  • Ryzen 9700X’te fused multiply-add throughput değeri 0.5 cycles/instruction, yani çevrim başına 2 komut
  • Teorik olarak Ryzen 9700X tek çekirdekte çevrim başına 32 FLOP gerçekleştirebiliyor
    • Hesap 8 floats × 2(add+mul) × 2(1/TP) şeklinde
    • 8 çekirdekte 4.7GHz sürdürülen saat hızı varsayılırsa çok iş parçacıklı teorik tepe değer 1203 FLOPS olarak tahmin ediliyor

Temel uygulama ve mikroçekirdek

  • Matrisler column-major sırayla saklanıyor
    • A[row][col], C işaretçisinde ptr[col*M + row] ile erişiliyor
  • En basit uygulama, $C$’nin tüm satır ve sütunlarını dolaşıp her eleman için $A$’nın satırı ile $B$’nin sütununun iç çarpımını hesaplıyor
  • Yüksek performanslı uygulamanın özü, $C$’yi $m_R \times n_R$ alt matrislere bölmek ve her alt matrisi verimli biçimde hesaplayan mikroçekirdek yapısı
  • Çekirdek, $\bar{C}$’yi yazmaçlarda sıfırla başlatıp ardından $K$ boyutu boyunca yineleme yapıyor
    • $\bar{A}$’nın sütun vektörünü ve $\bar{B}$’nin satır vektörünü yazmaçlara alıyor
    • İki vektörün dış çarpımını hesaplayıp $\bar{C}$ akümülatörlerine ekliyor
    • Her adım bir rank-1 update
  • Bu yaklaşım, naive yöntemdeki $2K m_R n_R$ bellek erişimine kıyasla, yazmaçlara alınan eleman sayısını $(m_R+n_R)K$ seviyesine indiriyor
  • AVX tabanlı CPU’larda 16 adet YMM yazmacı bulunduğu için çekirdek boyutu şu kısıtı sağlamalı
    • $(m_R/8) \cdot n_R + m_R/8 + 1 \le 16$
    • $m_R$ değeri 8’in katı olmalı
  • Teorik olarak $m_R$ ve $n_R$ değerleri ne kadar büyük ve birbirine yakınsa bellek erişimindeki azalma o kadar fazla olsa da, pratikte Ryzen 9700X üzerinde 16×6 çekirdek en iyi performansı veriyor
  • Uygulama immintrin.h içindeki intrinsic’leri kullanıyor
    • __m256, 256 bitlik vektör tipi ve YMM yazmacı içeriğini temsil ediyor
    • _mm256_loadu_ps ile A sütun vektörü yükleniyor
    • _mm256_broadcast_ss ile B içindeki skaler değer 8 float’lık vektöre broadcast ediliyor
    • _mm256_fmadd_ps ile akümülatör güncelleniyor
    • _mm256_storeu_ps ile sonuç belleğe yazılıyor
  • Üretilen assembly içinde vfmadd231ps ve vbroadcastss gibi SIMD FMA komutları yer alıyor

Rastgele boyutlu matrisler için dolgu

  • Temel 16×6 çekirdeği, $M$ ve $N$ sırasıyla 16 ve 6’nın katı olduğunda doğrudan çalışıyor
  • Sınır bölgede sütun sayısı $n$, 6’dan küçükse depolama döngüsü yalnızca j < n olana kadar yürütülüyor
  • Satır sayısı $m$, 16’dan küçük olduğunda _mm256_storeu_ps aynı anda 8 eleman yazdığı için maskeli depolama gerekiyor
    • _mm256_maskstore_ps, yalnızca maske biti açık olan elemanları belleğe yazıyor
    • Maske, çakışan satır sayısı $m$’ye göre üretiliyor
  • Sınırda yükleme işlemini de _mm256_maskload_ps ile yapmak çekirdek performansını ciddi biçimde düşürebiliyor
    • Ek maske hesaplama komutları ek yük oluşturuyor
    • $n$ derleme zamanında sabit olmadığı için derleyici döngüyü verimli biçimde unroll etmekte zorlanıyor
  • Bunun yerine $m \neq m_R$ ise $\bar{A}$ bir tampona kopyalanıp 0 ile dolduruluyor; $n \neq n_R$ ise $\bar{B}$ de bir tampona kopyalanıp 0 ile dolduruluyor
  • İlgili uygulama matmul_pad.h içinde bulunuyor

Önbellek bloklama ve veri yeniden kullanımı

  • Yazmaçlar ile DRAM arasında CPU önbelleği katmanları bulunuyor ve modern masaüstü CPU’lar genelde L1, L2 ve L3 önbellek kullanıyor
  • Önbellek DRAM’den hızlı ama kapasitesi sınırlı; bu yüzden tüm $A$, $B$, $C$ matrislerini bütünüyle önbelleğe sığdırmak mümkün değil
  • Matrisleri küçük bloklara ayırıp önbelleğe alarak aynı veriyi birden çok rank-1 update içinde tekrar kullanma yaklaşımına önbellek bloklama ya da tiling deniyor
  • Tek iş parçacıklı önbellek bloklama, BLIS yapısına benzeyen 5 katmanlı döngü düzeni kullanıyor
    • En dıştaki döngü, $N$ boyutu boyunca $C_j$ ve $B_j$ bloklarını oluşturuyor
    • Sonraki döngü, $K$ boyutu boyunca $A_j$ ve $B_p$ bloklarını oluşturuyor
    • $B_p$ paketlenerek $\tilde{B}_p$ haline getiriliyor ve gerekirse 0 ile doldurularak L3 önbellek yeniden kullanımına odaklanılıyor
    • Ardından gelen döngü, $M$ boyutu boyunca $C_i$ ve $A_j$ bloklarını oluşturuyor; $A_j$ de paketlenerek $\tilde{A}_j$ haline getiriliyor
    • Son iki döngü ise önbellek bloklarını $m_R \times k_c$ ve $k_c \times n_R$ panellere bölüp çekirdeğe iletiyor
  • Paketlenmiş $\tilde{A}_j$ ve $\tilde{B}_p$ farklı biçimde saklanıyor
    • $\tilde{A}_j$ içindeki paneller column-major olarak saklanıyor
    • $\tilde{B}_p$ içindeki paneller row-major olarak saklanıyor
  • Önbellek bloklama parametreleri, CPU modeline göre önbellek boyutlarına uygun şekilde ayarlanmalı
    • $k_c \times n_c$, L3 önbelleğini doldurmak için başlangıç noktası oluyor
    • $m_c \times k_c$, L2 önbelleğini doldurmak için başlangıç noktası oluyor
    • $k_c \times n_R$, L1 önbelleğini doldurmak için başlangıç noktası oluyor
  • Pratikte teorik değerden büyük parametreler daha iyi performans verebiliyor ve CPU önbellek yerleşimini otomatik yönettiği için algoritma düzeyinde döngü ve erişim desenini tasarlamak gerekiyor
  • Uygulama matmul_cache.h içinde yer alıyor

Çekirdek düzeyinde ince optimizasyon

  • Akümülatörleri __m256 C_buffer[6][2] gibi bir diziyle tanımlamak yerine, akümülatör değişkenleri açıkça açılarak tek tek tanımlanıyor
  • Bu yöntem GCC’nin kodu daha iyi optimize etmesine ve register spilling sorunundan kaçınmasına yardımcı oluyor
  • Maske hesabı da vektör komutları kullanacak şekilde değiştiriliyor
    • mask[32] adlı statik bir dizi tutuluyor ve _mm256_cvtepi8_epi32 ile _mm_loadu_si64 kullanılıyor
  • İlgili uygulama matmul_micro.h içinde bulunuyor

Çok iş parçacıklılığı stratejisi

  • Paralelleştirilen kısımlar hem aritmetik işlemler hem de paketleme adımları
  • Mikroçekirdeğin dışındaki 5., 4. ve 3. döngüler önbellek bloğu boyutunda tekrar ediyor
    • Tüm iş parçacıklarını meşgul tutmak için yineleme sayısının iş parçacığı sayısından büyük ya da eşit olması gerekiyor
    • Giriş matrisi boyutlarının kabaca iş parçacığı sayısı × önbellek blok boyutu kadar veya daha büyük olması gerekiyor
  • Ryzen 9700X’te tek iş parçacığında iyi performans veren önbellek blok boyutları $n_c=1535$, $m_c=1024$
    • 8 çekirdeğin tamamını kullanmak için en az $\max(m_c,n_c) \times 8 = 1535 \times 8 = 12280$ boyutlu bir eksen gerekiyor
  • Buna karşılık son iki döngü, küçük $m_R$ ve $n_R$ bloklarını yinelediği için paralelleştirmeye uygun
    • Genelde $m_R$ ve $n_R$ 20’den küçük oluyor
    • $m_c$ ve $n_c$ değerleri çekirdek sayısının katı seçilirse iş daha dengeli dağıtılabiliyor
  • Ryzen 9700X’te, iki iç döngüyü #pragma omp parallel for collapse(2) num_threads(NTHREADS) ile birlikte paralelleştirmek en iyi performansı veriyor
  • Çok sayıda çekirdeğe sahip işlemcilerde, özellikle 16 çekirdeğin üzerindeki ortamlarda, iç içe paralellik ve 2 ila 3 döngünün paralelleştirilmesi değerlendirilebilir
  • $\tilde{A}$ ve $\tilde{B}$ paketleme işlemleri de OpenMP ile paralelleştiriliyor
    • pack_blockA, mc boyunca MR birimiyle dolaşarak paralelleştiriliyor
    • pack_blockB, nc boyunca NR birimiyle dolaşarak paralelleştiriliyor
  • Çok iş parçacıklı uygulamada, Ryzen 9700X üzerinde iyi sonuç veren parametreler şöyle
    • $m_c = m_R \times \text{iş parçacığı sayısı} \times 5$
    • $n_c = n_R \times \text{iş parçacığı sayısı} \times 50$
  • Nihai çok iş parçacıklı uygulama matmul_parallel.h içinde yer alıyor

İlgili okumalar

1 yorum

 
GN⁺ 2024-07-05
Hacker News yorumları

  • Bu yazının ana fikri genelde performans için hâlâ pay kaldığı ise, hatta iyileştirme aralığını olduğundan küçük göstermiş sayılır. Üstelik matris çarpımı kütüphanelerine harcanan emek çoğu yazılımdakinden çok daha büyüktür.
    Zaten güçlü biçimde optimize edilmiş kod değilse, büyük bir çaba harcamadan mevcut kodda 10 ila 1000 kat ve üzeri iyileşme görmek yaygındır. Kabaca önem sırasına göre bakarsak, algoritma seçiminin uygun olup olmadığı ve işin kendisinin tamamen ortadan kaldırılıp kaldırılamayacağı en önemlileridir; kernel’e gidip gelmeleri veya malloc gibi ağır işlemleri azaltabilmek de büyük etki yapar.
    Vektörleştirmede açık vektör intrinsic’leri de iyidir ama veriyi yapı dizisi yerine dizi/yapıların dizisi biçiminde yeniden düzenlemek bile çoğu zaman aynı makine kodunu üretebilir. Önbellek verimliliği de önemlidir; paralel kodda ise yanlış paylaşım gibi iş parçacığı başına veri yalıtımının sağlanamadığı durumlarda işler daha karmaşık hâle gelir. Son olarak intrinsic’ler veya elle yazılmış assembly gibi donanıma özgü optimizasyonlar da mümkündür.

    • Ağ etkisi de atlanmamalı. Bir keresinde dağıtık bir sorgunun ağ üzerinden yaklaşık 1 milyon satır getirip sonra join yaparak geriye yalnızca 5–10 satır bıraktığını fark ettim; bu sayede yüzlerce kat performans iyileştirmesi sağlandı.
      Join işlemi uzak sunucuda gerçekleşecek ve ağ üzerinden sadece 5–10 satır gönderilecek şekilde sorguyu değiştirince hemen hızlandı. Sabit ek yük ve gecikme her zaman vardır ama ihtiyacınız olandan çok daha fazla veriyi ağ bağlantısından geçirirseniz eninde sonunda performansı mahvedersiniz. Gecikmenin etkisini ele alan “It's the latency, stupid” da okunmaya değer: http://www.stuartcheshire.org/rants/latency.html
      Genel olarak yukarıdaki değerlendirmelere ve yaklaşık sıralamaya katılıyorum.
    • “Algoritma seçimi uygun mu?” meselesi pratikte bir ölçüde cargo cult hâline gelmiş durumda. “Daha hızlı” algoritmanın gerçek sabit terimleri berbat olabiliyor; bu yüzden daha fazla iş yapan yaklaşımın aslında daha iyi performans verdiği çok olur.
      Birçok mülakat, bir uygulamanın neden yavaş olduğunu akıl yürütüp benchmark ederek ve düzelterek görmeye çalışmak yerine, “Google böyle yapıyor” tarzı obscure algoritma ezberleme sınavına dönüşmüş durumda.

  • Yaygın kodlama kalıpları donanıma yeterince özelleşmediği için performansın büyük kısmını masada bırakır. Bu yazı ilginç bir örnek; bir başka klasik gösterim de “There's plenty of room at the top”.
    https://www.science.org/doi/10.1126/science.aam9744

  • Bunu anlamak için BLIS deposundaki makaleler kanonik kaynaklara yakın. Optimize edilmiş BLAS’ın performans veremeyeceğini neden düşündüklerini bilmiyorum; yeterince büyük matrislerde CPU tepe performansının %90’ından fazlasını beklemek gerekir.
    Son baktığımda seri OpenBLAS genel olarak MKL’ye benziyordu ve BLAS, temel doğrusal cebir bloğu olarak matmul değil GEMM uygular. Genelde benchmark framework’ü yerine numpy kullanılmasını da anlamıyorum; Zen’de AMD’nin BLAS’ı, yani BLIS tabanlı uygulamayla karşılaştırmak gerekir diye düşünüyorum. BLIS’in eskiden OpenBLAS’a göre paralelleştirme tarafındaki hikâyesi daha iyiydi; AMD BLIS’te “küçük” boyutlar için uygulama değiştirme de var, bunun şu an OpenBLAS’ta olup olmadığını bilmiyorum.
    Mikro kernel vektörleştirmesi için SIMD intrinsic’leri şart değildir; düzgün bir C derleyicisi tamamen vektörleştirir ve döngüleri de açar. BLIS’in saf C mikro kerneli, uygun blok boyutlarında Haswell’in elle optimize edilmiş uygulamasına göre %80’den fazla performans verir. Fark muhtemelen prefetch yüzündendir ama tam olarak anlamış değilim.

    • SIMD intrinsic’leri ve manuel döngü açma kesinlikle gereklidir. Tüm BLAS kütüphanelerinin döngüleri elle vektörleştirip açmasının nedeni budur.
      Modern derleyiciler de otomatik vektörleştirme ve döngü açmayı %100 başarı oranıyla doğru düzgün yapamaz.

  • Yazı ve uygulama iyi görünüyor ama “sır”ın ne olduğunu merak ediyorum. OpenBLAS bu tam problem için onlarca yıldır assembly+C ile optimize ediliyor; nasıl geçilebiliyor?
    Önbellekleme vb. konuları ayrıntılı ele alıyor, BLAS bunlardan yararlanmıyor mu, yoksa belirli bir işlemciye daha iyi mi uyarlanmış, merak ediyorum

    • OpenBLAS belirli yeni mimarilere o kadar da optimize edilmiş değil. Matrisler de o kadar büyük değildi ve numpy’de cffi ek yükü var.
      Performans farkı ortalama iş hacminden çok tepe iş hacminde daha belirgindi; tepe performansın önemli olduğu uygulama sayısı ise çok az. Gösterilen benchmark kodunda numpy tarafı Python ayırıcıdan geçiyor, C uygulaması ise ayırıcıdan geçmiyor gibi görünüyor; bu yüzden mikrobenchmark hatası veya tutarsızlığı için ilk bakılacak yer burası. Birçok numpy rutini yerinde işlem destekliyor, dolayısıyla her iki taraf için de yerinde sürümlerin benchmark’ını açıkça görmek gerekir gibi.
      numpy’de alt uygulamadan bağımsız olarak çalışan sınır denetimleri ve hata işleme de var; küçük matrislerde saf Python listelerinden bile çok yavaş olmasının nedeni bu. Birkaç bin çevrimlik saf ek yük eklenince hızlı yapmak zorlaşıyor.
      Bu uygulama ilgili önbellekleri doyurmaya yönelik oldukça ilkeli bir yaklaşım ve bir bakıma bariz olsa da, net mühendislik iyileştirmeleri bu tür tartışmalarda vurgulanmaya değer. OpenBLAS için de çok emek harcandı ama her şeyi düşünmüş olma ihtimali düşük. Bunu düzgün açıklamak için iki taraftaki kodun da derinlemesine analiz edilmesi gerekir.
    • OpenBLAS’ı geçmek şaşırtıcı da değil, emsalsiz de değil. Örneğin D dilinin doğrusal cebir kütüphanesi Mir de birkaç yıl önce bunu yapmıştı [1]
      C++ ve C uygulamaları için metaprogramlama yaklaşımlarına [2], [3] bakılabilir. Asıl şaşırtıcı olan, Matlab, Julia, Mojo gibi birçok modern dilin hâlâ OpenBLAS’a dayanması; elbette her birinin kendi gerekçeleri vardır.
      [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 tam CPU modeline göre derlediği için avantaj sağlayabilir. numpy’nin daha genel ve eski bir x86-64 hedefi için derlenmiş olması çok olası.
      Ryzen CPU’larda -march=native muhtemelen v4 kullanır; numpy ise v1 ya da v2’yi hedefliyor olabilir.
      https://en.wikipedia.org/wiki/X86-64#Microarchitecture_level...
    • numpy 2.0, birden fazla mikro mimaride SIMD’yi daha iyi kullanmak için Google highway’i entegre ediyor; bu yüzden numpy tarafındaki karşılaştırma daha iyi hale gelecek.

  • Yazı da iyi, benchmark’ı kolayca yeniden üretilebilir hale getirmesi de harika. Benim 16 çekirdekli Xeon W-2245 3.90GHz sistemimde matmul.c, 8192x8192 matris çarpımını gcc -O3 ile 1,41 saniyede, clang -O2 ile 1,47 saniyede yaptı; NumPy ise 1,07 saniyeydi.
    AVX-512 çekirdeği ile çok daha hızlı olacağını düşünüyorum. Performansın düşük kalmasının bir başka nedeni OpenMP olabilir; deneyimlerime göre pthreads ile thread pool’u açıkça yönetmek ek yükü azaltabiliyor. CPU sayısını sabit kodlamak yerine sysconf(_SC_NPROCESSORS_ONLN) kullanmak da daha iyi olur.

  • Bir taraf Python, diğer taraf C iken yükü farklılaştırmaya gerek yok. İkisi de C ile yazılıp, biri BLAS kütüphanesini, diğeri de bu uygulamayı çağıracak şekilde elma elma bir karşılaştırma yapılabilirdi.

    • Burada Python ile karşılaştırmak doğru. Çünkü günümüzde bu tür hesaplamaları yapmanın en yaygın yolu numpy kullanan Python.
      Ek yük çok büyük değil ama bu başlığın başka yerlerinde de söylendiği gibi, doğru şekilde çağırmak önemli. Safça yazılmış numpy kodunu ayarlanmış C koduyla karşı karşıya getirmek kesinlikle adil bir karşılaştırma değil.

  • Sıcak yol değil ama maske üretimindeki verimsizlik, yani bit_mask kullanımı gözüme batıyor. Daha verimli bir yöntem olarak {-1,-1,...,0,0,...} biçiminde global bir sabit dizi oluşturup eleman ofseti 16-m, 8-m üzerinden yüklemek ya da sabit vektör {0,1,2,3,4,...} ile broadcast edilmiş m ve m-8 değerlerini karşılaştırmak mümkün
    Gerçi bu yalnızca matrisin tek bir sütunu için geçerli ve ardından gelen maskload/maskstore döngüsü çok daha uzun sürdüğü için epey küçük bir kusur arama sayılır. Özellikle store, Zen 4’te bile hâlâ yavaş[1]; AVX-512 komutu ise maskeyi maske register’ından alması dışında fark olmamasına rağmen 6 kat daha hızlı. clang zaten shift’i otomatik vektörleştirdiği için, muhtemelen benim önerimden yalnızca 2-3 kat daha yavaştır
    [1]: https://uops.info/table.html?search=vmaskmovps&cb_lat=on&cb_...

    • Yazarıyım. C kodu optimizasyonu ve intrinsic kullanımı konusunda gerçekten yeniyim; bu alanın uzmanı değilim ama daha fazla öğrenmek istiyorum
      Yeni bir bakış açısı sunan geri bildirimin için gerçekten teşekkür ederim. “Sabit global dizi oluşturup yükleme” yöntemini hatırladığım kadarıyla test ettiğimde bit mask shift’inden biraz daha yavaş gibiydi; emin olmak için tekrar test edeceğim. “Sabit vektör {0, 1, 2, 3, 4, ...} ile broadcast edilmiş m ve m-8 değerlerini karşılaştırma” yöntemi iyi bir fikir, deneyeceğim
    • Global sabit diziyi oluştururken elemanları int8_t yapıp, yükleme sırasında byte’ları int32_t’ye işaret genişletmesiyle dönüştürebilirsin. _mm_loadu_si64 / _mm256_cvtepi8_epi32 kombinasyonu, bellek operandı kullanan tek bir vpmovsxbd komutuna derlenecektir
      Böylece alignas(32) ile düzgün hizalandığında tüm sabit dizi tek bir cache line’a sığar. Özgün kullanım senaryosunda iki maske gerektiğinden, ikinci vpmovsxbd komutu kesin bir L1D cache hit olur ve iyi uyar

  • jart’ın tinyBLAS’ı nasıl olur?
    https://hacks.mozilla.org/2024/04/llamafiles-progress-four-m...
    Bir de https://justine.lol/matmul/

    • Dün Justine ile kapsamlı biçimde konuştum; o workstation’da bu implementasyon tinyBLAS’tan en az 2 kat daha hızlı görünüyor. Tartışmanın tamamı Mozilla AI Discord’da: https://discord.com/invite/NSnjHmT5xY

  • Benchmark dışında matris çarpımının kendisini çok iş parçacıklı yapmanın nedeni ne olabilir? Pratikte çarpımı kullanan algoritma tarafında çok iş parçacığı kullanmak daha avantajlı olmaz mı?

    • HPC’de aslında genelde böyle yapılır. Yine de paralel BLAS’a geçmek tek başına belirli türde R kodlarına kolayca fayda sağlayabilir
      Ancak HPC kodlarında genellikle darboğaz GEMM değildir

  • Henüz yalnızca göz attım ama bu yazıda çok sayıda ayrıntı ve açıklama var. Hızlı matris çarpımının mimariyle ilgili hususlar dikkate alınarak nasıl implemente edildiğini oldukça iyi anlatan bir yazı gibi görünüyor; okuma listeme ekledim