SIMD Algoritmalarını Sıfırdan Tasarlamak

SIMD algoritması tasarımı

• SIMD optimizasyonuna dair açıklama: SIMD, tek komut çoklu veri anlamına gelir ve devre tasarımcısı gibi düşünmeyi gerektirir.
• SIMD, performans ve HPC (yüksek performanslı hesaplama) alanında sıkça anılır, ancak yeni başlayanlar için tanıdık bir konu değildir.
• Çoğu programlama dilinde SIMD programlama API'lerini kullanmak zordur.
• SIMD algoritmalarını prosedürel programlama düşünce yapısıyla anlamak zordur; fonksiyonel programlama yardımcı olur.
• Metin, Rust'un std::simd kütüphanesini kullanarak bir base64 codec'i uygulayan vb64 hakkındadır.

Fiziksel sınırlar

• Bilgisayarlar gerçek dünyada var olur ve fizik yasalarına tabidir.
• Bilgisayarların ilk döneminde, yeni bir bilgisayar satın alarak performans artırılabiliyordu.
• Dennard ölçekleme etkisinin çökmesiyle, daha küçük transistörler daha fazla güç tüketimi anlamına gelmeye başladı.
• Çekirdek sayısını artırmak yeni eğilim haline geldi. Çok iş parçacıklılığıyla CPU performansı artırılabilir, ancak senkronizasyon ek yükü ortaya çıkar.

Prosedürel kodun yavaşlığı

• Modern bilgisayar çekirdekleri kodu satır satır yürütmez.
• Komut düzeyi paralellik sayesinde, veri bağımlılığı yoksa birden fazla işlem aynı anda yürütülür.
• Derleyici veri tehlikelerini çözebildiğinde paralellik artar.
• Dallanma ve bellek işlemleri duraksamalara yol açar ve bu da kodu yavaşlatır.

SIMD ve lane'ler

• SIMD ve vektör sözcükleri çoğu zaman eş anlamlı kullanılır.
• SIMD komutları, sabit boyutlu sayı dizileri olan vektörleri temel birim olarak kullanır.
• Vektördeki her öğeye lane denir ve SIMD vektörleri genellikle küçük boyutludur.

Gerçek vektörler üzerinde işlemler

• SIMD vektörleri, sıradan yazmaçlara göre daha karmaşık işlemler sunar.
• Vektör yazmaçları bit işlemleri, lane bazlı aritmetik, lane bazlı karşılaştırma, shuffle gibi çeşitli işlemleri destekler.
• Shuffle, SIMD programlamada veriyi uygun konuma taşımak için kritik önemdedir.

Intrinsic'ler ve komut seçimi

• SIMD kodu yazarken kullanılabilecek işlemler mimariye göre değişir.
• Derleyici, kullanıcının istediği işlemin hangi komutla gerçekleştirileceğine karar verme şeklindeki komut seçimi sorununu çözer.
• Taşınabilir SIMD kodu yazmak karmaşıktır, ancak çalışma zamanı özellik algılamasıyla farklı işlemciler için en uygun kod üretilebilir.

SIMD ile ayrıştırma

• SIMD kullanılarak metin ayrıştırma yapılabilir ve bu çok hızlı olabilir.
• Buna örnek olarak base64 çözmeyi SIMD ile uygulamak verilebilir.
• Tüm dallanmaları ortadan kaldırmak, SIMD sürümünü oluşturma sürecinin özüdür.

GN⁺ görüşü

Bu yazıdaki en önemli nokta, SIMD programlamanın geleneksel prosedürel programlama yaklaşımından farklı olarak veriyi paralel işleyip performansı artırabilmesidir. SIMD, yüksek performanslı hesaplama alanında çok önemlidir; özellikle Rust gibi modern programlama dillerinde SIMD'yi etkili kullanma yöntemlerini anlamak, yazılım mühendisleri için oldukça ilgi çekici bir konu olabilir. Bunun nedeni, SIMD aracılığıyla karmaşık algoritmaları optimize etmeyi ve gerçek donanım sınırlarını aşmanın yollarını öğrenebilmenizdir.

[GN⁺]

Hacker News görüşleri

• Taşınabilir SIMD kullanım örneklerini gösteren harika bir yazı. Benchmark'ları Zen 3 sistemimde yeniden çalıştırdım ve aynı hız artışını gördüm. M1 mbp'de giriş uzunluğu 110 bayt olduğunda performans artışı kademeli olarak en fazla 2 kata çıkıyor. x86_64'e kıyasla kazanç daha az, ama hedefe ulaşıldığı söylenebilir. Ancak Rust'ın SIMD ve pointer ile ilgili işler ile genel performans mühendisliği açısından biraz zahmetli olabildiğini de doğruladım.
• Bazen C++ ile elinden gelenin en iyisini yaparak program yazsan bile, SIMD kullanan sürümün 10 kattan fazla daha hızlı olması şaşırtıcı. Kodun taşınabilirliği azalıyor, ama keşke derleyici otomatik vektörleştirmeyi daha iyi yapabilse. Belirli işlemlerin sırasını annotation'larla yeniden düzenlemeye izin veren dil desteği eklenmesi güzel olurdu.
• Derleyicinin belirli bir popcount uygulamasını tek bir komuta optimize edemediği, ancak başka bir uygulama için bunun mümkün olabildiği belirtiliyor.
• _mm256_cvtps_epu32, AVX2 komutu değil AVX-512 komutudur; AVX1'de tamsayılar signed biçimdedir ve ilgili komut _mm256_cvtps_epi32 olur.
• Sağdaki küçük minimap'i gerçekten çok beğendim.
• ISPC'nin C++ ya da Rust'a SIMD eklemekten daha iyi olduğu düşünülüyor. Ayrıca dinamik dispatch'i destekliyor; bunu elle uygulamak epey zor bir özellik.
• fastbase64 ile karşılaştırıldığında nasıl olduğu soruluyor ve taşınabilir SIMD kütüphaneleri konusunda yazarın iyimser yaklaşımını paylaşmak istediğini belirten bir yorum var.
• Harika bir yazı; insanın kendi başına asla bu kadar akıllı olamayacağını düşündürüyor.
• Vektörleştirilmemiş popcnt uygulamasının ilk örneği için "dürüst olmak gerekirse gülünç bir kod" ürettiği söylenmişti, ancak release modunda yerel hedef CPU için derlendiğinde fonksiyonun aslında oldukça iyi vektörleştirildiği görülüyor.
• Rust Simd için oldukça iyi bir deneme. Üretilen kodu incelerken en şaşırtıcı tuhaflığın ne olduğu soruluyor.