SIMD algoritmalarını sıfırdan tasarlamak

 (mcyoung.xyz)
2 puan yazan GN⁺ 2023-11-29 | 1 yorum | WhatsApp'ta paylaş
  • Rust’ın std::simd ile yapılan vb64 base64 codec’i, prosedürel döngüleri olduğu gibi vektörleştirmek yerine veri yerleşimini ve işlem akışını bir devre gibi yeniden tasarlayınca hızlı ve taşınabilir SIMD koduna dönüşür
  • Temel optimizasyon, dallanma ve bellek erişiminden kaynaklanan stall’ları azaltmaktır; compare, mask, select ve shuffle ile girdiden bağımsız olarak aynı işlemleri yapan branchless bir yapı kurulur
  • base64 çözmede ASCII karakterleri sextet’e çevirmek için byte >> 4 ve / düzeltmesini kullanan bir perfect hash oluşturulur; offset, SIMD vektörü içindeki lookup table ve shuffle ile bulunur
  • Dört adet 6 bitlik sextet üç bayta paketlenirken lane’ler u16’ya büyütülüp shift edilir; ardından low/high byte ayrılır ve komşu lane’deki bayt parçaları rotate_lanes_left ile OR kullanılarak birleştirilir
  • Benchmark’larda -Zbuild-std, -Ctarget-cpu=native, N = 32 kombinasyonu ve remainder yükleme optimizasyonundan sonra crates.io’daki baseline base64 uygulamasına kıyasla neredeyse tüm aralıklarda yaklaşık 2 kat performans gösterir

SIMD’yi gerekli kılan fiziksel arka plan

  • Bilgisayar performansındaki artış yalnızca kuramsal bilgisayar bilimiyle değil, fiziksel kısıtlarla da doğrudan bağlantılıdır
  • Moore yasası 2023 itibarıyla hâlâ geçerli görünüyor, ancak son 15 yılda Dennard scaling etkisi çöktüğü için daha yoğun transistörler güç tüketimi yoğunluğunun artmasına yol açtı
  • Saat frekansını sürekli artırmak zorlaştıktan sonra, 2000’lerin başından itibaren performans artışının ana yönü daha fazla çekirdek kullanmaya kaydı
  • Multithreading, çekirdekler arasında işbirliği gerektirdiğinden senkronizasyon maliyeti doğurur; jump, sanal çağrı ve senkronizasyon gibi kontrol akışları stall’a neden olur
  • Stall’ın başlıca iki nedeni vardır
    • Dallanma: if, döngüler, fonksiyon çağrıları, fonksiyon dönüşleri, C’deki switch gibi kontrol akışları
    • Bellek işlemleri: load/store, özellikle cache dostu olmayan erişimler

Prosedürel kod ve komut düzeyinde paralellik

  • Modern CPU çekirdekleri kodu satır satır çalıştırmaz; birbirine bağımlı olmayan işlemleri aynı anda yayınlar
  • a = x + y ve b = x ^ y gibi birbirine bağımlı olmayan işlemler, add ve xor devrelerini aynı anda kullanabilir
  • Bu yaklaşım komut düzeyinde paralelliktir; bunu engelleyen bağımlılıklara data hazard denir
  • CPU functional unit’leri ne kadar iyi doldurabilirse birim zamanda o kadar çok işlem işler
  • Dallanmalarda koşul hesaplanmadan sonraki komutun getirilmesi beklenir; bellek işlemlerinde ise verinin fiziksel olarak CPU’ya ulaşması gerektiğinden stall oluşur
  • GPU’lar görüntüleri vektör biçimindeki pikseller olarak ele alır ve yerelliği yüksek işlemleri sıkça gerçekleştirir; bu nedenle batch işlemlere ve sınırlı kontrol akışına göre tasarlanmış SIMD makinelerine yakındır
  • SIMD, single instruction, multiple data anlamına gelir; tek bir komutun birden çok veri lane’i üzerinde paralel işlem yapmasıdır

Lane bazlı düşünme biçimi

  • SIMD ve vector çoğu zaman aynı anlamda kullanılır; SIMD komutunun temel birimi sabit boyutlu sayı dizisi olan vector’dür
  • Vector’ün her bileşenine lane denir
  • SIMD vektörü register’a sığmak zorunda olduğundan genellikle küçüktür
    • Örnek ortamdaki en büyük vektör genişliği 256 bittir
    • Bu, u8x32 için 32 bayta veya f64x8 için 4 adet double’a karşılık gelir
  • Küçük bir vektör bile pipeline’ı doldurma yükünü 4 kat azaltabiliyorsa, bu ölçüde latency iyileşmesi sağlayabilir

popcnt üzerinden böl ve fethet

  • En basit vektör işlemleri bitwise and/or/xor’dur
  • Sıradan tamsayılar da bitwise işlem açısından 1 bitlik lane’lerden oluşan bir vektör olarak görülebilir
    • i32 bu bakış açısıyla i1x32 ile aynıdır
  • popcnt, bir tamsayının içindeki 1 bitlerinin sayısını sayan işlemdir; i32’yi i1x32 olarak görürsek bir reduce işlemidir
  • 32 biti dizi olarak çıkarıp toplamak şeklindeki basit uygulama kötü kod üretebilir
  • Daha iyi yöntem, komşu bit çiftlerini toplamak ve ardından çiftlerin çiftlerini toplayarak lane genişliğini büyüte büyüte ilerlemektir
    • 0x55555555, 0xaaaaaaaa maskeleriyle çift/tek bitler ayrılır
    • shift ile lane’ler hizalanır ve sonra toplanır
    • Ardından 2 bit, 4 bit, 8 bit ve 16 bit birimleriyle tekrarlanır
  • Bu uygulama popcnt komutuna optimize edilmez, ancak böyle bir komutun olmadığı sistemlerde küçük ve hızlı kod sağlar
  • u64 için de yalnızca bir reduction aşaması daha eklenerek uygulanabilir; tüm u64 toplamına gerek yoktur
  • Bu tür böl ve fethet yaklaşımı SIMD programlamanın temel örüntülerindendir

SIMD komut kümelerinin başlıca araçları

  • Gerçek SIMD vektörleri skalerlere göre daha karmaşık anlamlar sunar; yavaş kontrol akışını ikame eden özellikler özellikle önemlidir
  • Kullanılabilen komutlar mimariye büyük ölçüde bağlıdır
    • x86’daki birçok yüksek performanslı çekirdek AVX2’yi uygular
    • AVX2, 256 bitlik ymm vektörleri sağlar
    • Register’ın kendisinde lane sayısı yoktur; lane’lerin nasıl yorumlanacağını komut belirler
    • Örneğin vpaddb, ymm’yi i8x32 olarak yorumlar
  • Genel olarak kullanılabilen işlemler şunlardır
    • bitwise işlemler: lane genişliği her zaman örtük olarak 1 bittir
    • lane-wise aritmetik: toplama, çıkarma, çarpma, bölme, tamsayı shift, min/max vb.
    • lane-wise karşılaştırma: m[i] = a[i] < b[i] gibi mask vector üretir
    • select: mask kullanarak iki vektörden lane bazında değer seçer
    • shuffle/swizzle: bir vektörü lookup table gibi görüp index vektörüyle lane’leri yeniden düzenler
  • Mask vector’de true/false genellikle all-ones veya all-zeros bit desenlerini kullanır
  • Karşılaştırma ve select, SIMD kodunun branchless kalmasına yardımcı olan temel araçlardır
  • Branchless kod, girdiden bağımsız olarak aynı işlemleri yapar ve gereksiz sonuçları x * 0 = 0, a ^ b ^ a = b gibi özelliklerle atar

shuffle ile verinin konumunu hizalama

  • Shuffle, SIMD’de verinin “doğru konuma” gelmesini sağlayan temel araçtır
  • Broadcast veya splat, tüm lane’leri aynı scalar’a sahip bir vektör oluşturur; [0, 0, ...] index shuffle’ı olarak ifade edilebilir
  • Interleave veya zip/pack, iki vektör a, b’nin lane’lerini sırayla yerleştirir
    • c = [a[0], b[0], a[1], b[1], ...]
    • shuffle2 ile uygulanabilir
  • Deinterleave veya unzip/unpack, interleave’in tersidir
  • Rotate, lane’leri b[i] = a[(i + j) % n] biçiminde döndürür; bu da bir shuffle’dır
  • SIMD programlamada tamsayılardan daha büyük veri bloklarını farklı boyutlardaki küçük bloklar olarak yeniden yorumlamak ve yeniden yerleştirmek sık yapılan bir iştir

Intrinsics, target feature, portable SIMD

  • SIMD’de kullanılabilecek işlemler mimariye ve instruction set extension’a göre değişir
  • x86’da ARM’de olmayan işlemler bulunabilir; Intel AVX-512 gibi aynı üretici içinde bile yalnızca üst düzey sunucu çiplerinde sunulan genişletmeler de vardır
  • Toolchain’ler bu genişletmeleri target feature olarak genelleştirir
    • Linux’taki lscpu, CPU’nun tanıdığı feature’ları gösterir
    • LLVM, feature ayarlarına göre komut seçimini farklı yapar
    • LLVM’in ymm kullanan kod üretebilmesi için +avx2 gerekir
  • -march=native veya -Ctarget-cpu=native, derlemenin yapıldığı makineye uygun iyi kod üretebilir; ancak başka işlemcilere taşınabilirliği düşürebilir
  • Runtime feature detection, CPU’nun desteklediği özellikleri kontrol ederek hangi fonksiyon sürümünün çağrılacağına karar verme yöntemidir; şifreleme kütüphaneleri gibi çok çeşitli cihazlara dağıtılan kodlarda kullanılır
  • C++’taki SIMD kodu genellikle _mm256_cvtps_epu32 gibi intrinsics kullanır
    • Belirli bir instruction set’in düşük seviyeli işlemlerini temsil eder
    • Mutlaka tek bir komuta eşlenmez
    • Derleyici birleştirme, yinelenenleri kaldırma ve komut seçimi optimizasyonları yapabilir
  • Birden fazla instruction set için benzer kodu tekrar tekrar yazmak gerekirse, assembly’ye kıyasla bakım avantajı çok büyük olmayabilir
  • Portable SIMD kütüphaneleri, bazı komut seçimlerini kütüphane düzeyinde ele alıp geri kalanını derleyiciye bırakan bir yaklaşımdır
  • vb64 implementasyonu, Rust’ın portable SIMD’inin rekabetçi kod üretip üretmediğini kontrol etmeye yönelik bir deneydir

Base64 çözmeyi SIMD’ye dönüştürmek

  • base64, rastgele ikili veriyi ASCII olarak kodlama yöntemidir
  • Girdi byte dizisini bir bit vektörü olarak görür ve 6 bitlik chunk’lar olan sextet’lere böler
  • Sextet değerleri şu karakterlere eşlenir
    • 0..25 → 'A'..'Z'
    • 26..51 → 'a'..'z'
    • 52..61 → '0'..'9'
    • 62 → +
    • 63 → /
  • base64’ün çeşitli varyantları vardır, ancak karmaşıklığın büyük kısmı ortaktır
  • Dikkat edilmesi gereken iki nokta vardır
    • base64, byte içindeki bitlerin big endian olduğu bir formattır
    • Girdi uzunluğu 4’e tam bölünmeyebilir; prensipte = padding ile 4’ün katına tamamlanır, ancak padding’i doğru olmayan mesajlar da işlenebilir
  • Decoded length, input / 4 * 3 üzerine input % 4 değerine bağlı kalan uzunluk eklenerek hesaplanır

Branchless’a doğru temel refactoring

  • Basit bir base64 decoder’da birden çok branch bulunur
    • Girdiyi chunk’lar halinde dolaşan döngü
    • Chunk içindeki byte döngüsü
    • ASCII karakterlere göre match
    • Hata durumunda return Err
    • decoded_len içindeki match
    • Vec::extend_from_slice ve allocator çağrısı olasılığı
  • Optimizasyon yönergesi tüm branch’leri kaldırmaktır
  • decoded_len içindeki match, input % 4 değeri olan 0, 1, 2, 3ü 0, 1, 1, 2ye eşler
  • Bunu mod4 - mod4 / 2 ile değiştirmek branchless sürüm sağlar
  • LLVM normalde matchi switch table’a indirgeyebilir; ancak bu bölgede gereksiz bellek erişimi performansı düşürür

En sıcak döngüyü ayırmak

  • SIMD’nin gücü, tek seferde çok veri işleyerek döngüyü güçlü biçimde unroll etmekte ve branchless’a yakın hale getirmektedir
  • Hot loop’un hedefi en fazla 4 byte okuyup en fazla 3 byte’lık decode sonucu üretmek ve sözdizimi hatası olup olmadığını da bildirmektir
  • Yararlanılabilecek üç olgu vardır
    • Çıkış uzunluğu branchless decoded_len() ile hesaplanabilir
    • Geçersiz base64 çok nadir bir yol olarak görülebilir; hata konumu gerekirse sonradan tekrar taranabilir
    • base64’te A 0 olduğundan, truncated chunk’ı A ile pad etmek değeri değiştirmez
  • decode_hot(), dört giriş byte’ını işleyip decode sonucu ve başarı durumunu gösteren bool döndürecek şekilde ayrılır
  • Option<[u8; 3]> yerine bool’u ayrı döndürmek, daha sonra if !ok branch’ini kaldırmayı kolaylaştırır
  • SIMD sürümünde giriş olarak Simd<u8, 4> alınır; çıkış da power-of-two lane sayısına uyması için Simd<u8, 4> olarak tutulur
    • Gerçekte gereken çıkış 3 byte’tır
    • Son lane kullanılmaz

ASCII’yi sextet’e dönüştürme yöntemi

  • ASCII karakterleri sextet’e dönüştüren matchin büyük kısmı byte - C biçiminde ifade edilebilir
    • 'A'..'Z' → byte - 'A'
    • 'a'..'z' → byte - 'a' + 26
    • '0'..'9' → byte - '0' + 52
    • '+' → byte - '+' + 62
    • '/' → byte - '/' + 63
  • Lane başına offset vektörü oluşturup ascii - offsets yapmak yeterlidir
  • İlk yaklaşım compare-and-select’tir
    • A-Z, a-z, 0-9, +, / için maskeler oluşturulur
    • Hiçbir maskenin seçmediği lane invalid kabul edilir
    • Her maskeye karşılık gelen offset splat edilir ve OR ile birleştirilir
  • Bu yöntem zarif ve rekabetçi kod üretebilir; ancak toplam 8 karşılaştırma gerekir ve canlı değer sayısı fazla olduğundan register pressure oluşabilir

SIMD hash table ve perfect hash

  • A-Z, a-z, 0-9 byte aralıkları sırasıyla 0x41..0x5b, 0x61..0x7b, 0x30..0x3adır ve high nibble’ları farklıdır
  • + ve /, 0x2b, 0x2f olduğundan yalnızca byte >> 4 ile büyük ölçüde ayırt edilebilir
  • / durumunda bir çıkarılırsa aralık için perfect hash elde edilir
  • (byte >> 4) - (byte == '/') eşlemesi şöyledir
    • A-Z → 4 veya 5
    • a-z → 6 veya 7
    • 0-9 → 3
    • + → 2
    • / → 1
  • Bu değer küçük olduğundan offset lookup table bir SIMD vektörünün içine konabilir ve lookup shuffle ile yapılabilir
  • Bu perfect hash fikri GitHub issue’daki anonim bir kullanıcı tarafından önerildi
  • Simd::swizzle_dyn() için index dizisi ile lookup table uzunluğunun aynı olması kısıtı vardır
  • Perfect hash yönteminde sextet hesaplama sırasında yan etki olarak validation elde edilmediğinden, byte geçerliliğini kontrol etmek için aynı GitHub issue’daki exact bloom filter kullanılır
  • Implementasyon örneği vb64’ün simd.rs dosyasında bulunur

Dört sextet’i üç byte’a paketlemek

  • Dört adet 6 bitlik sextet’i üç byte’ta birleştirme adımı daha zordur
  • Belirli bir giriş sextet’ini all-ones yapıp çıkışta bitlerin nereye taşındığını kontrol ederek yerleşim ilişkisi izlenebilir
  • Yalnızca byte düzeyinde shuffle yeterli değildir
    • Taşınması gereken hedef byte parçalarıdır
    • Shift tek başına da yetersizdir
    • Overshift edilen bitlerin komşu lane’e taşınması gerekir
  • Çözüm, lane’leri daha büyük yapmaktır
  • sextets, u16 vektörüne cast edildikten sonra lane başına shift edilir
    • input[0] 2 bit shift edilir
    • input[1] 4 bit shift edilir
    • input[2] 6 bit shift edilir
    • input[3] 8 bit shift ile ayarlanır
  • Shift sonucundan low byte ve high byte vektörleri ayrılır
  • hi.rotate_lanes_left::<1>() ile high byte tarafındaki parçalar komşu lane’e hizalanır, ardından lo | hi_rotated ile birleştirilir
  • Bu yöntem hardware primitive’lerini etkin biçimde kullandığı için kod küçük ve verimlidir

Lane sayısını artırma ve garbage lane’leri kaldırma

  • Simd<u8, 4>, x86’nın en küçük 128 bit vektör register’ından bile küçük olduğu için decode_hot() lane sayısı N için generic hâle getirildi
  • LaneCount<N>: SupportedLaneCount kısıtıyla küçük power-of-two lane sayıları garanti edilir
  • Lookup table ve shift table, tekrar eden desen vektörlerini oluşturmak için tiled() helper’ını kullanır
  • N = 4 için son lane’deki garbage değeri yok saymak yeterliydi; ancak N büyüdüğünde her dördüncü lane’e garbage karışır
  • Bunu kaldırmak için shuffle kullanılır
    • İstenen ilişki shuffled[i] = output[i + i / 3]
    • Her dördüncü indeksi atlayarak garbage lane silinir
    • Overflow olan kısım, nihai çıktı vektörünün üst 1/4’ü olduğundan yok sayılır
  • Böylece decode_hot::<32>() ile 32 base64 byte paralel olarak decode edilebilir

Outer loop optimizasyonu

  • decode() da iç lane sayısı N için generic hâle getirildi
  • Geriye kalan maliyetler şunlardır
    • for chunks in ... içindeki uzunluk karşılaştırma branch’i
    • [T]::copy_from_slice içindeki variable-length memcpy
    • Her loop iteration’daki ok branch’i
    • Vec::extend_from_slice için allocator çağrısı olasılığı ve bir başka memcpy
  • Çıktı uzunluğu bilindiğinden out.reserve(final_len + N / 4) ile alan önceden ayrılır
  • Ayrıca slop alanı bırakılarak variable-length memcpy yerine full SIMD store yapılır
  • Her iteration tüm SIMD vektörünü yazar; bir sonraki write 3/4 * N kadar ilerleyerek önceki garbage byte’ın üzerine yazar
  • Sondaki garbage byte, nihai Vec::set_len() içine dahil edilmediği için silinmiş gibi ele alınır
  • if !ok nedeniyle early return yapılsa bile set_len() ile commit edilmediğinden out değiştirilmemiş durumda kalır

Hata işlemeyi hot loop dışına ertelemek

  • Her iteration’da if !ok ile return etmek yerine error |= !ok ile biriktirilir
  • Nihai set_len() çağrısından hemen önce hata olup olmadığı yalnızca bir kez kontrol edilir
  • Çoğu base64 blob’unun valid olduğu varsayımıyla hata yolu hot loop dışına itilmiş olur
  • Sözdizimi hatası olsa bile sonraki SIMD işlemleri keyfî biçimde misbehave etmediğinden garbage write commit edilmeden kaybolur
  • Sonrasında Vec::push() gibi çağrılar aynı buffer alanının üzerine yazabilir

Unroll and jam ve remainder işleme

  • copy_from_slice içindeki variable-length memcpy’yi azaltmak için unroll and jam uygulanır
  • Döngü iki parçaya ayrılır
    • Hot vectorized loop: her zaman yalnızca uzunluğu N olan girdiyi işler
    • Cold remainder part: i < N girdiyi en fazla bir kez işler
  • Rust’ın Iterator::chunks_exact() API’si kullanılarak hand-rolled unroll-and-jam uygulanır
  • Hot loop’ta Simd::from_slice() çağrılarak tek bir vector-sized load yapılır
  • Bounds check’ler, compiler’ın kolayca kaldırabileceği bir biçime gelir

Benchmark ve manuel yükleme optimizasyonu

  • Benchmark, uzunluğu 0’dan yaklaşık 200 veya 500 byte’a kadar olan mesajları decode eder ve crates.io’daki baseline base64 implementasyonuyla karşılaştırır
  • Derleme seçenekleri olarak -Zbuild-std ve -Ctarget-cpu=native kullanılır
  • Tuning sonucunda N = 32 en iyi sonucu verdi ve her hot loop iteration’ında bir YMM register kullanıldı
  • Başta baseline’ı geçti, ancak data.len() % 32 ile güçlü biçimde ilişkili heartbeat tarzı performans dalgalanmaları görüldü
  • Assembly incelendikten sonra copy_from_slice’ın byte bazlı bir load loop olarak inline/unroll edilmiş gibi göründüğü değerlendirildi
  • Simd::gather_or() da denendi, fakat daha kötü assembly ürettiği için kullanılmadı
  • Bunun yerine variable-length veri için manuel bir loading fonksiyonu yazıldı
    • Hot part, mümkün olan en büyük scalar load olan u128 load’u döngü içinde yapar
    • LLVM, 16 byte’lık chunk’ı XMM load’a indirger
    • Remainder, çakışan u64, u32, u8 load’ları kullanır
  • 15 byte okunurken p konumundan bir u64, p + 7 konumundan bir u64 okunarak 1 byte çakıştırılır ve OR ile birleştirilir
  • 4~7 byte için çakışan u32 load’ları kullanılır
  • 1~3 byte için p, p + len/2, p + len - 1 konumlarından okunur; bazı byte’lar tekrar load edilebilir, ancak branch sayısı azaltılır
  • Yeni loading code uygulandıktan sonra variance çok küçüldü ve baseline’a kıyasla neredeyse tüm aralıkta 2 kat performans gösterdi

Encoding ve web-safe base64

  • Encoding fonksiyonu, decode_hot() işlemlerini tersine yapan encode_hot() uygulanarak yazılabilir
  • Decoding’de kullanılan perfect hash encoding’e uygun olmadığından yeni bir hash gerekir
  • Encoder çevresindeki loading/storing code da decoder’dan biraz farklıdır
  • vb64, verimli bir encoding routine de uygular
  • Web-safe base64, + ve / karakterlerini - ve _ ile değiştiren bir varyanttır
  • Web-safe base64 için perfect hash oluşturmak daha zordur; örnek olarak (byte >> 4) - (byte == '_' ? '_' : 0) gibi bir yöntem gerekebilir
  • vb64 henüz web-safe base64 desteklemiyor

Sonuç

  • vb64’ın önemli bir darboğazı çözmeyi amaçlayan bir kütüphane olmadığı ve base64 decoding’in gerçekten darboğaz olduğu bir yer bilinmediği belirtiliyor
  • Branchless kod çoğu zaman abartılı olabilir, ancak compiler’ın neyi yapıp neyi yapamayacağını anlamaya yardımcı olur
  • Rust’ın std::simd’i genel olarak iyi ve kaliteli kod üretiyor
  • SIMD kodunu daha sade hâle getirmek için düzeltilmesi istenen bazı rough edge’ler olsa da mevcut çalışma sonucundan memnun olunduğu değerlendiriliyor
  • SIMD ve performans optimizasyonu, çok sayıda trick ve donanım bilgisi gerektiren karmaşık konulardır; bunların önemli bir kısmı belgelenmiş değildir

İlgili okumalar

1 yorum

 
GN⁺ 2023-11-29
Hacker News yorumları

  • portable SIMD’in gerçekten kullanıldığını görmek ilginçti; Zen 3 sistemde benchmark’ı yeniden çalıştırdığımda aynı hız artışı ortaya çıktı
    M1 MacBook Pro’da giriş uzunluğu 110 baytta performans artışı 1,4x ile başlayıp kademeli olarak 2x’e kadar çıktı; x86_64’ten düşük olsa da hedefe ulaşılmış görünüyor
    Ancak koda bakınca, Rust’ın SIMD ve pointer ile ilgili işlerde, daha genel olarak da performans mühendisliğinde ergonomisinin epey kötü olduğu yönündeki deneyimimi doğruluyor

    • Bir Rust mühendisi olarak buna belli ölçüde katılıyorum, ama pointer ve ham bellek işleri güvenlik nedeniyle kasıtlı olarak çok kısıtlı ve dilin ne yaptığını gerçekten düşünmenizi isteme tarafı var
      Yine de Rust’ın portable SIMD hikâyesi C++ ile kıyaslandığında hâlâ pek iyi değil ve ham byte alanı, pointer ve buffer manipülasyonuna inmek için Pin, MaybeUninit gibi şeylere alışmak gerekiyor
      portable_simd ve allocator_api yıllardır unstable durumda; giriş eşiği yüksek ve daha hantal, ama bu büyük ölçüde bilinçli bir tasarım
      Yine de kendi programınız içinde bunu daha kullanışlı hâle getirecek soyutlamaları kendiniz yazmanızı veya üçüncü taraf crate’ler kullanmanızı engelleyen bir şey yok
    • Ergonomisinin kötü olduğuna katılmıyorum
      C++ SSE intrinsic’leri alt çizgileriyle daha çirkin ve isimleri de hatırlaması daha zor, yani çok daha kötü

  • Klasik C++ ile elinizden gelenin en iyisini yazıp sonra birinin SIMD sürümüyle gelip bunu 10 kattan fazla hızlandırdığını görmek bazen gerçekten şaşırtıcı oluyor
    Buna karşılık bu kod daha az taşınabilir
    Keşke derleyicilerin otomatik vektörleştirmesi daha iyi olsa ve bazı işlemleri yerel olarak yeniden sıralamaya izin veren, dil düzeyinde açıklama benzeri destekler bulunsa

    • İyi SIMD kodu, verinin belleğe nasıl yerleştirildiğini dikkatle düşünmeyi gerektirir
      Derleyici çok yerel bağlamın dışında veriyi sizin yerinize yeniden düzenleyemez, bu yüzden otomatik vektörleştirme gerçekten zorlaşır
    • Derleyici kusursuz optimize edebilse bile kaçınılmaz birçok seri garanti vardır
      Örneğin for(double v: vec) sum+=v ifadesinde kayan noktalı toplama birleşme özelliğine sahip değildir; dolayısıyla değerleri sırayla toplamak ile 8’er aralıkla toplayıp sonra kalanları birleştiren SIMD yöntemi aynı şey değildir
      Derleyici açısından bu bariz bir optimizasyon gibi görünse de, belirli garantilerin gevşetilebileceği söylenmedikçe optimizasyondan önce seri anlam garantisini korur
      Bu yüzden işler dağınık hâle geliyor ve janwas’ın dediği gibi sıcak yol için bir kütüphane, özellikle Google Highway veya Intel ISPC gibi şeyler kullanmak daha mantıklı bence
    • Bu, sistem programlama dili olarak C++’ın ana amaçlarından biri
      Mümkün olduğunca taşınabilir biçimde verimli olmaya çalışırken, gerektiğinde hedefe özgü programlamayı da kolaylaştırıyor
      Otomatik vektörleştirme konusunda FORTRAN derleyicileri kesinlikle daha iyi; çünkü aliasing’e izin verilmiyor
      C++ ise C’nin bellek modelini takip etmek zorunda kaldığı için bunun bedelini ödüyor
    • Doğrudan CUDA da kullanabilirsiniz
      CUDA, günümüzün nihai SIMD makinesi olan GPU için tasarlanmış C++ ve ROCm de fiilen AMD için bir CUDA’ya yakın
      Ben şahsen Microsoft’un C++AMP’sini seviyordum; başlangıç için en kolay yaklaşımın o olduğunu düşünüyordum
      Ama sonuçta tutunamaması üzücü
    • Benim deneyimimde bu tür şeyler sık olur
      Ayrıca SIMD wrapper kütüphaneleri kullanırsanız bunu pratikte oldukça taşınabilir de yapabilirsiniz

  • Küçük bir not: derleyici ilgili popcount uygulamasını tek bir komuta optimize edemedi, ama başka bir uygulamada bu mümkün
    Tabii oldukça hassas bir mesele: https://godbolt.org/z/T69KxWWW8

  • _mm256_cvtps_epu32’nin belirli bir komut setinin düşük seviyeli işlemini temsil ettiği ve AVX2’nin float-to-int cast’i olduğu söylenmişti, ancak bu komut AVX-512’ye ait
    AVX2’de float-to-int cast yok; AVX1’de ise tamsayı sonucu signed’dır ve komut _mm256_cvtps_epi32 olur

  • fastbase64[0] ile karşılaştırması nasıl olurdu merak ediyorum
    Yazı harika ve bu tür içerikleri çevrimiçi görmek sevindirici, ama yazarın portable SIMD kütüphanesi konusundaki iyimserliğini paylaşmak zor
    [0]: https://github.com/lemire/fastbase64

  • SIMD’yi C++ veya Rust’a sonradan eklemektense ISPC’nin düpedüz daha iyi olduğunu düşünüyorum
    Dinamik dispatch’i de destekliyor; bunu kendiniz uygulamaya kalkarsanız acı veren bir özellik

    • İnsanların SIMD’yi daha çok kullanmasını sağlayan bir araçsa genel olarak iyi bir şeydir, ama ben şahsen SIMD’nin aynı toolchain içine entegre olmasını tercih ediyorum
      Böylece inline çağrıları tekrar C++’a geri gönderebilir, SIMD kodunda template ve class kullanabilir, birden çok SIMD kod bölgesini birlikte inline edebilirsiniz
      Dinamik dispatch uygulamasının zor olduğuna katılıyorum, ama Highway bu kısmı hallediyor
    • Metindeki gibi küçük bir alt yordamda C++ veya Rust’ın ISPC çağırmasının ne kadar kolay olduğunu merak ediyorum

  • Harika bir yazı; insanda güçlü bir “ben asla bu kadar zeki olamam” hissi bırakıyor

    • Sadece sizin çalışma alanınız değil
      Nasıl sıradan bir insan yazılım mühendisi ya da fizikçi değilse, bu da öyle
      Birkaç ay odaklanıp çalışsanız benzer bir seviyeye gelebilirsiniz
    • Buna ihtiyaç duyan bir işverenle ya da projeyle karşılaşma şansınız olursa muhtemelen “bu kadar zeki” olabilirsiniz
      Sonuçta mesele ilgi ve ihtiyaç
      Ben de performans optimizasyonu ile sisteme daha yakın bare-metal mühendisliği arasında kişisel projelerde gidip geliyorum, ama işte buna daha çok ihtiyaç duyulmasını isterdim
      Yine de sektör işlerinin çoğu bunu gerektirmiyor
    • AoC '23’ü APL/j/k, BQN, Python/numpy, CUDA gibi şeylerle çözmeyi deneyin
      Yani deyimsel Python değil, her şeyi numpy ile çözmek gibi
      Eğlenceli oluyor, bu tür bir zekâyı öğrenebiliyorsunuz ve yazının büyük kısmı bu dillerde problem çözme zihniyetiyle bakınca son derece doğal geliyor
      Zamanla problemleri o biçimde görmeye başlıyorsunuz
    • https://fgiesen.wordpress.com/2016/02/05/smart/

  • İlginç bir yazı
    Baştaki ilk örnekte vektörleştirilmemiş popcnt uygulamasının “dürüst olmak gerekirse gülünç derecede kötü kod” ürettiği söyleniyor, ama release modunda yerel hedef CPU kullanıldığında bu fonksiyonun epey iyi vektörleştirildiği görülüyor
    https://godbolt.org/z/WE1Eq65jY

    • Aşağıdaki kod eşdeğer çıktı üretmelidir
      pub fn popcnt(mut x: u32) -> u32 { x.count_ones() }
      Bu, popcnt eax, edi; ret olarak derleniyor
      Büyük bit vektörlerinde AVX2 uygulaması POPCNT'den daha hızlı olabilir
      “Faster Population Counts Using AVX2 Instructions”a bakın: https://academic.oup.com/comjnl/article/61/1/111/3852071
      32 bit yeterince büyük değil ve Rust'ın ürettiği kod gerçekten gülünç derecede kötü
    • İdeal olarak bunun popcnt komutuna indirgenmesi gerekir gibi görünüyor
    • Otomatik vektörleştirme bazen oluyor, bazen olmuyor
      Kısa süre önce vektör işlemi sonucundaki maskenin bit sayısını saymak gereken bir kod yazdım; bu, popcnt'ye gayet iyi dönüştürülüyor
      https://godbolt.org/z/zT9Whcnco

  • “Bu biraz tuzak soru gibi… sadece add değil mi?” gibi kısımlar yüzünden, genelde ara vektör gösterimini hedeflemek ve ayrıntıları derleyicinin belirlemesine izin vermek istiyorsunuz
    Örneğin Haswell çiplerinde çekirdek başına birden fazla kayan nokta yürütme birimi vardı ve CPU, boru hatlı kayan nokta işlemlerinden iki veya daha fazlasını aynı anda çalıştırabiliyordu, ancak bunlar arasında add komutundan yalnızca bir tane çalışabiliyordu
    Önceki sonuca bağlı olmayan çok sayıda toplama işlemi varsa ve bu sayede gecikmeden kaçınılabiliyorsa, çarpan terimi 1 olan fused multiply-add komutu da birlikte gönderilerek toplama throughput'u iki katına çıkarılabiliyordu
    Bu komut, normal vektör kayan nokta toplamasıyla aynı anda çalıştırılabiliyordu