Neden Her Geliştirici SIMD'yi Bilmelidir

 (mitchellh.com)
1 puan yazan GN⁺ 2 시간 전 | 1 yorum | WhatsApp'ta paylaş
  • SIMD, yalnızca en yüksek performanslı yazılımlar için kullanılan karmaşık bir teknik değil; ardışık verileri aynı anda birden çok değer halinde işleyerek sıradan döngüleri hızlandıran günlük bir optimizasyon aracıdır
  • Tipik SIMD kodu 5 aşamalı bir yapıyı izler: sabit yayınlama, vektör genişliği kadar ilerleme, paralel işlem, sonucu indirgeme/kaydetme ve skaler kuyruk işleme
  • Ghostty'nin kod noktası arama döngüsü, bir seferde 4, 8 veya 16 u32 karşılaştırır; teoride bu, işlem hacmini ARM NEON'da 4 kata, AVX2'de 8 kata, AVX-512'de 16 kata kadar artırabilir
  • AVX2'li bir Intel masaüstünde terminalin uçtan uca işlem hacmi yaklaşık 5 kat arttı; desteklenen bir vektör genişliği yoksa veya giriş artarsa, mevcut skaler döngü tüm girdiyi ya da kalanı işler
  • Derleyicinin otomatik vektörleştirmesi, basit döngülerde bile fırsatları kaçırabilir; bu yüzden önce optimize edilmiş çıktıyı kontrol etmek gerekir, ancak kritik sıcak döngülerde açık SIMD kullanmak davranışı ve performansı öngörülebilir tutabilir

SIMD ne yapar?

  • SIMD, CPU'nun tek bir komutla birden çok değeri paralel işlemesini sağlar
    • Baytları tek tek karşılaştırmak yerine, aynı anda 4, 8 veya daha fazlasını karşılaştırabilirsiniz
    • for (byte in bytes), for (character in string), for (value in array) gibi döngülerde vektör genişliği kadar işleme geçme fırsatı vardır
  • Veri yüzlerce, binlerce ya da milyonlarca baytsa, paralellik genişliğine bağlı olarak yerel olarak 4 kat, 8 kat veya daha fazla hızlanma elde edilebilir
  • Veri sadece birkaç ya da birkaç düzine öğeden oluşuyorsa SIMD uygulamaya değmez
  • simdutf ve simdjson karmaşık SIMD teknikleri kullanır, ancak günlük SIMD'nin bu kadar karmaşık olması gerekmez
  • Örnekler Zig kullanıyor, ancak 5 aşamalı yapı diğer dillere de uygulanabilir; her dil SIMD komutlarını farklı biçimde destekler

Tekrarlanan 5 aşamalı yapı

  1. Gerekli sabitleri tüm lane'lere yayınlayın ve gerekiyorsa vektör biriktiricilerini başlatın
  2. Girdiyi her seferinde vektör genişliği kadar ilerleyerek dolaşın
  3. Tüm lane'lerde karşılaştırma veya aritmetik işlemleri paralel yürütün
  4. Algoritmaya uygun şekilde vektör sonucunu indirgemeyi veya kaydetmeyi yapın
  5. Tam bir vektöre sığmayan kalanı mevcut döngü olan skaler kuyruk (scalar tail) ile işleyin
  • Bu yapıya alışınca, normal bir döngüyü de aynı 5 aşamaya ayırabilir ve SIMD yazmayı skaler döngü kadar basit hale getirebilirsiniz
  • Eğer bir işlem bu yapıyla kolayca ifade edilemiyorsa, şimdilik SIMD uygulamayı atlamak daha uygundur

Ghostty'deki gerçek arama döngüsü

  • Ghostty, çözümlenmiş kod noktası dizisinde 0xF veya daha küçük bir değerle karşılaşana kadar veriyi tüketir
    • Terminal verisinin çoğu yazdırılacak normal karakterler olduğu için bunları toplu işler
    • Döngü, bir sonraki yazdırılabilir bölümün sonunu mümkün olduğunca hızlı bulur
  • Orijinal skaler uygulama kod noktalarını tek tek kontrol eder
while (end < cps.len and cps[end] > 0xF) end += 1;
  • Vektör uygulaması CPU'ya özel intrinsic'ler yerine genel vektörleri kullanır ve skaler sürümden sadece 12 satır daha uzundur
  • Beklenen işlem hacmi artışı vektör lane sayısıyla orantılıdır
    • ARM NEON ve Apple Silicon: en fazla 4 kat
    • Modern x86 CPU'ların çoğunun desteklediği AVX2: en fazla 8 kat
    • Bazı Intel CPU'ları ve AMD Zen 4+ tarafından desteklenen AVX-512: en fazla 16 kat
  • AVX2'li bir Intel masaüstünde, terminal programı girdisinden son terminal durumuna kadar ölçülen toplam işlem hacmi yaklaşık 5 kat hızlandı
    • SIMD çevresindeki ek işler yüzünden teorik hızlanmanın tamamı elde edilemez
  • C0 kontrol karakterleri 0xF sonrasında da vardır, ancak bu Ghostty kod yolunda eşik olarak 0xF kullanılır
    • ESC ve diğer kontrol dizileri ayrı bir yolda işlenir

1. aşama: sabit yayınlama

if (simd.lanes(u32)) |lanes| {
    const V = @Vector(lanes, u32);
    const threshold: V = @splat(0xF);
  • Ghostty'deki simd.lanes(u32), hedef CPU'nun aynı anda işleyebildiği u32 sayısını döndürür
    • Bu değerlerin her birine lane denir
    • ARM için 4, AVX2 için 8, AVX-512 için 16 döner
    • Kullanılabilir bir vektör boyutu yoksa null döndürür ve SIMD kodu atlanır
  • @Vector(lanes, u32), bu lane sayısına sahip bir vektör tipi oluşturur
    • lanes 8 ise bir V içinde paralel işlenebilecek 8 adet u32 bulunur
  • Vektör karşılaştırmasında her iki tarafın da vektör olması gerektiği için @splat(0xF), 0xF değerini tüm lane'lere kopyalar
{ 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF, 0xF }
  • Bu algoritmada vektör biriktiriciye gerek yoktur, ancak başka algoritmalar bu aşamada biriktirici başlatabilir

2. aşama: vektör vektör ilerleme

while (end + lanes <= cps.len) : (end += lanes) {
    const values: V = cps[end..][0..lanes].*;
  • lanes 8 ise, yalnızca en az 8 değer kaldığında döngüye girilir ve 8 değer values içine yüklenir
  • Her yinelemenin sonunda end, 1 değil lane sayısı kadar artırılır
  • Tam bir vektör yüklenebilmesi gerektiğinden, sadece 5 değer kalmışsa 8 lane'li vektör okunmaz
  • Vektöre sığmayan değerler 5. aşamadaki skaler kuyruk tarafından işlenir

3. aşama: tüm lane'lerde paralel karşılaştırma

const greater_than_threshold = values > threshold;
  • values ve threshold ikisi de vektör olduğu için >, karşılık gelen tüm lane'leri tek bir vektör işlemi ile karşılaştırır
  • 8 lane varsa, cps[end] > 0xF karşılaştırmasına denk gelen 8 işlem paralel yapılır
values:                 { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
threshold:              {  0xF,  0xF,  0xF,  0xF,  0xF,  0xF,  0xF,  0xF }
greater_than_threshold: { true, true, true, false, true, true, true, true }
  • Açık bir iç döngü yoktur; sonuç, lane başına boolean içeren bir vektördür
  • Aynı yapı sadece karşılaştırma için değil, toplama, çarpma, minimum, maksimum gibi vektör tipinin desteklediği işlemler için de geçerlidir
  • Karşılaştırmanın kendisi tek bir vektör işlemi olsa da vektör yükleme, sonuç indirgeme ve başarısız lane'i bulma için ek komutlar gerekir

4. aşama: vektör sonucunu indirgeme

if (@reduce(.And, greater_than_threshold)) continue;
  • @reduce(.And, ...), tüm boolean değerlerini and ile birleştirip tek bir boolean üretir
  • Tüm lane'ler true ise bir sonraki vektöre geçilir; en az biri false ise başarısız olan tam konum bulunur
const mask: std.meta.Int(.unsigned, lanes) = @bitCast(greater_than_threshold);
end += @ctz(~mask);
break;
  • @bitCast, boolean vektörünü lane başına 1 bitlik bir tamsayı maskesine dönüştürür
    • 1, değerin 0xF'ten büyük olduğunu gösterir
    • 0, karşılaştırmanın başarısız olduğunu gösterir
  • Maske ters çevrilince başarısız karşılaştırmalar 1 olur ve @ctz, ilk 1 bitinden önceki 0 bitlerinin sayısını verir
values:                 { 0x41, 0x42, 0x43, 0x0A, 0x44, 0x45, 0x46, 0x47 }
greater_than_threshold: { true, true, true, false, true, true, true, true }
mask:                   {    1,    1,    1,     0,    1,    1,    1,    1 }
~mask:                  {    0,    0,    0,     1,    0,    0,    0,    0 }
  • Bu örnekte @ctz(~mask) değeri 3 döndürür ve end değişkenini ilk kontrol karakteri olan 0x0A'nın bulunduğu 3. lane'e taşır
  • Sonuç indirgeme, 5 aşama içinde algoritmadan algoritmaya en çok değişen kısımdır
    • Toplam alma işlemleri vektör biriktiriciyi tek bir sayıya indirebilir
    • Dönüşümler tüm vektörü çıktı tamponuna yazabilir
    • Bu arama, bit maskesi üretip belirli bir lane'in konumunu bulur

5. aşama: skaler kuyruk işleme

while (end < cps.len and cps[end] > 0xF) end += 1;
  • Girdi uzunluğu vektör genişliğinin tam katı değilse, orijinal skaler döngü kalanı işler
  • 8 lane'li vektör döngüsünden sonra 0 ile 7 arasında değer kalabilir
  • simd.lanes(u32) değeri null olan CPU'larda SIMD bölümü atlanır ve tüm girdiyi skaler döngü işler
  • Orijinal uygulama aynı anda hem kalanı işleme hem de uyumluluk fallback'i görevini görür
  • Genel vektörler CPU'ya özgü sözdizimini ortadan kaldırır, ancak CPU'ya özgü kod üretimini ortadan kaldırmaz
    • Zig, vektör işlemlerini hedefte etkin olan komut kümesine dönüştürür

Otomatik vektörleştirmenin kaçırdıkları

  • Derleyiciler, karmaşık kontrol akışı içermeyen düzenli aritmetik döngüler gibi basit kodları otomatik vektörleştirebilir
  • Elle SIMD yazmadan önce skaler sürümü optimizasyon seçenekleriyle derleyip üretilen kodu incelemelisiniz
  • Üretim derleyicileri sık sık vektörleştirme fırsatlarını kaçırır; otomatik vektörleştirme onlarca yıldır araştırılıyor ve yakın tarihli çalışmalar da bu sorundan yola çıkıyor
  • Eğer bir döngü için 5 kat hızlanma önemliyse, davranışı öngörülebilir tutmak adına vektörleştirmeyi açıkça yazabilirsiniz
    • Böylece alakasız kod değişiklikleri veya derleyici güncellemelerinin vektör döngüsünü sessizce yeniden skaler döngüye çevirmesini önleyebilirsiniz

Geliştiricilerin bilmesi gereken SIMD düzeyi

  • Büyük miktarda ardışık veriyi arayan, karşılaştıran, sayan veya dönüştüren sıcak döngüler gördüğünüzde, vektör genişliği kadar işleme yaklaşımını düşünebilmelisiniz
  • Günlük SIMD, sabit hazırlama, vektör yükleme, paralel işlem, sonuç indirgeme ve skaler kuyruk şeklinde düzenli bir yapı izler
  • Dil SIMD'yi iyi destekliyorsa, assembly ya da CPU'ya özgü ayrıntıları doğrudan bilmeden de performansı artırabilirsiniz
  • Her geliştiricinin ihtiyaç duyduğu seviye, simdutf veya simdjson tarzı karmaşık teknikler değil; SIMD fırsatlarını fark edip ortak yapıyı kullanabilme düzeyidir

İlgili okumalar

1 yorum

 
GN⁺ 2 시간 전
Hacker News yorumları

  • İyi bir yazı; ancak SIMD’nin anlaşılmasının kolay ve for döngüsü yazmak kadar kolay olduğunu söyleyerek başlayıp daha ilk örnekte tek satırlık skaler kodu 12 satıra çevirmek pek ikna edici değil.
    Bunun yerine SIMD’nin zor olduğunu, ama sonucun buna değdiğini dürüstçe söylemek daha iyi olur. Hedef kitle yeni başlayanlarsa, 1. adımdan itibaren broadcast gibi SIMD’ye özgü terimler açıklamasız kullanılmamalı; skaler kuyruk işlemeyi açıklayan 5. adım ise iyi kurgulanmış

    • SIMD ve ilk örnek zor olmaktan çok, daha ziyade zahmetli bir iş gibi
      Donanımın tek seferde kaç öğe işleyebildiğini anlamak, işi o boyutta gruplamak, sonuçları tekrar açmak, kalan öğeleri ayrı işlemek ve sabitleri de çoğaltılmış vektörler hâline getirmek gerekiyor. Bunların her biri zor değil, ama iş miktarını artırıp süreci zahmetli kılıyor
    • 1990 civarındaki Transputer furyası sırasında ortaya çıkan Parallel-C’yi öğrenmiştim; paralel programlama özelliklerini C’ye ekleyen bir dildi
      En sevdiğim özellik, bazı sınır koşulları altında derleyicinin for döngülerini otomatik paralelleştirmesini sağlayan par(; ; ) idi
    • Tam hedef okura yakın biri olarak ilgiyle okudum, ama zorluk seviyesi çok hızlı yükseliyor; meşhur baykuş çizme memesine benzer hissettirdi
    • SIMD’nin kendisi basit; skaler bir dilde veri-paralel işlemler kullanma biçimi garip olan şey
    • Teknik eğitimdeki en büyük hatalardan biri, konuyla ilgili korkuyu azaltma bahanesiyle onun basit olduğunu ilan etmektir. Basit olduğunu söylemeyin, gerçekten gösterin
      Konu gerçekten karmaşıksa onu daha küçük ve basit parçalara bölmek, ardından dik öğrenme eğrisini tırmanmayı mümkün kılacak şekilde sırayı iyi kurmak ve buna değdiğine ikna etmek gerekir

  • Daha iyi tavsiye, herkesin dizi programlamayı bilmesi gerektiğidir. SIMD optimizasyonu genellikle bu düşünme biçimini gerektirir; yalnızca paketlenmiş SIMD’ye özgü teknikler ise şaşırtıcı derecede nadirdir
    Dizi programlama, derleyicinin otomatik vektörleştirme yapmasını kolaylaştırdığı için, SIMD’yi doğrudan kullanmasanız bile çoğu zaman performanslı kod üretir

    • Önce tüm karşılaştırmaları yapıp başarısız olan ilk öğeyi daha sonra bulmaya dayalı dizi programlama, çalışma aralığı kısa olduğunda pek yardımcı olmaz. Kendi başına erken çıkış sağlamadığı için gereksiz karşılaştırmalara çok zaman harcayabilir
    • Kapalı kaynak dilleri sevmem ve MATLAB’ın da çok kusuru var, ama üniversitede sayısal simülasyonlar için vektörleştirilmiş kodu verimli yazmak oldukça doğaldı
      Çok deneyimim yok ama Julia, benzer vektörleştirme yeteneklerine sahip daha modern ve ifade gücü yüksek bir dile en yakın seçenek gibi görünüyor

  • Son birkaç gündür bir biyoinformatik projesindeki matris işlemlerini AVX-512 ile optimize ettim ve sonuçtan çok memnunum
    Çoğu uygulamada darboğaz, büyük veri kümelerini bellekten okuma sürecidir; bu yüzden birden çok işlem için tekrar tekrar okumak yerine AVX register’ları ve birleştirilmiş kernel ile hepsini tek seferde işleyebilirsiniz. 5 kat hızlanma da yaygın; ben doğrudan intrinsic kullandım ama wide crate’i ile yaygın işlemler oldukça basitleşiyor: https://docs.rs/wide/latest/wide/

  • Geliştiricilerin ezici çoğunluğunun SIMD öğrenmesine hiç gerek yok. Neden tüm geliştiricilerin bunu bilmesi gerekiyormuş da ancak o zaman gerçek geliştirici sayılırlarmış gibi bir yanlış izlenim yaratılıyor, anlamıyorum

    • En azından SIMD’nin varlığını ve neler yapabileceğini bilmek değerli. Bir geliştiriciyseniz basit değerleri toplayan ya da karşılaştıran bir hot loop yazmışsınızdır; derleyicinin bunu hedef CPU mimarisine göre optimize edebileceğini bilmek birçok durumda işe yarar

  • Başlığı “Herkes SIMD’nin uygulanmadığı anı bilmeli” diye değiştirmek daha iyi olur
    Modern derleyiciler vektörleştirmede çok iyidir, ama tek bir varsayım ya da veriye bağımlı bir dallanma yüzünden aniden skaler koda geri düşebilirler. SIMD yazmayı öğrenmektense derleyicinin optimizasyon raporunu nasıl kontrol edeceğini öğrenmek daha değerli olabilir

    • Kötü otomatik vektörleştirmenin çözümü doğrudan SIMD kodu yazmaktır; optimizasyon raporuna bakmayı öğrenmenin gerçekten bundan daha değerli olup olmadığı şüpheli
      Yalnızca sorunu tespit edebiliyorsanız sonuçta “yazık olmuş” demekle kalırsınız
    • Gerçekten de tam olarak bu yaşandı: https://xcancel.com/mitchellh/status/2079672171321081908#m

  • Geçen yıl bir ses sentezleyici geliştirirken x86 ve ARM SIMD öğrenmeye başladım: https://github.com/seclorum/SIMDSynth
    Çoklu timbre ve polifonik sentezleyici yapısı, birden çok veri akışına aynı işlemi uyguladığı için SIMD ilkelerini öğrenmeye çok uygundu. Ancak hata ayıklama oldukça zordu; her işleme hattının durumunu anlayabileceğim bir simülatöre ciddi ihtiyaç duydum ve SIMD araçlarını araştırmak da ayrıca büyük bir yatırım gerektirecek gibi görünüyor

  • Yazı iyi ve daha fazla dilin SIMD’yi desteklemesi güzel olurdu; ancak en popüler iki dilin SIMD’yi yerel olarak desteklemediği bir durumda “tüm programcılar bilmeli” ifadesi biraz tuhaf

    • En popüler dillerin, böyle yazıların hedeflediği yazılım mühendisleri tarafından en çok kullanılan diller olduğunu varsaymak zor

  • Doğrudan SIMD yazmayacak ya da işi yapay zekaya bırakmayı planlayacak olsanız bile, hangi işlerin hangi donanımda SIMD ile hızlanabileceğini bilmelisiniz. Böylece algoritma ve kod yapısını SIMD uygulanabilecek şekilde tasarlayabilirsiniz
    Veri bağımlılığının etkisi, vektör öğe genişliğini artırmanın maliyeti ve bundan kaçınma yolları, koşul ve dallanmaları maskelere dönüştürme, “bölme komutu yoktur” gibi özellikler, SIMD’yi az da olsa doğrudan kullanınca çok daha kolay içselleştirilir

    • SIMD’nin ne zaman hızlandırdığı yeterince ele alınmıyor
      Büyük ve ardışık verileri tek seferde denetlerken ya da dönüştürürken iyi çalışır; ancak girdinin her birkaç baytında bir karar vermeniz gerekiyorsa skaler yöntemle aynı hızda, hatta daha yavaş olabilir. SIMD sihirli bir hızlandırma düğmesi değildir

  • The Witness geliştirme ekibinin gerçek bir performans sorununu SIMD ile çözme sürecini Casey Muratori’nin anlattığı faydalı bir video: https://www.youtube.com/watch?v=Ge3aKEmZcqY

    • Harika bir sunum, ama başkasına önermek için video çok uzun; keşke özüne odaklanan bir yazı sürümü olsaydı
      Performans için dikey entegrasyonun iyi bir örneği: genel soyutlamaların neden var olduğunu ve neden genel amaçlı olmaları gerektiğini anladıktan sonra, belirli bir kullanım senaryosunda problem tanımından SIMD’ye kadar dikey olarak entegre olup büyük kazanç elde etme sürecini gösteriyor

  • SIMD gibi mikro optimizasyonlara girmeden önce veri yapıları ve erişim desenleri ciddi biçimde gözden geçirilmeli
    Eskiden Zig koduna SIMD uygulamıştım, ama veri yapısı modeli optimizasyonun tam tersine olduğu için, bozuk motorlu bir hurda arabaya yüksek performanslı yarış lastikleri takmak gibiydi. Performansı ölçmeden ve bellek ayırmanın nerede yapıldığını dikkate almadan yapılan tipik bir acele optimizasyondu
    Artık veriye SQL tablosu gibi bakıyor, yapıyı potansiyel birincil anahtarlar ve erişim desenleri etrafında tasarlıyorum. Eskiden heap’teki başka struct’ları işaret eden bir ağaç kullanıyordum; bu da bağlı listelerin dezavantajlarını, çok sayıda heap vektörünün parçalanmasını ve yavaş oluşturma/serbest bırakma maliyetlerini birlikte getiriyordu; yalnızca Drop bile çalışma süresinin kayda değer bir kısmını tüketiyordu
    Ağaçlar her zaman lineerleştirilebildiğinden erişim/ekleme desenlerini, yapının gerçekten ağaç mı yoksa başka bir graph mı olduğunu, Vec ya da birden fazla Vec’ten oluşan bir struct olarak mı saklanacağını değerlendiriyorum. Sonuçta kod daha hızlı ve daha basit hale geldi; veriler homojen dizilerde toplandığı için derleyicinin SIMD optimizasyonlarından ve L1 cache’ten yararlanmak kolaylaşıyor, gerektiğinde doğrudan dallanmasız SIMD kodu da yazılabiliyor
    İlgili kaynak: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

    • Hot loop’ları SIMD ile hızlandırmak için veri yerleşimi ve cache dostu yapı kilit önemdedir
      Gerçek darboğaz bölgelerinde bellek ayırmadan, sanal fonksiyon tablosu aramalarından ve aşırı dolaylı erişimden kaçınmak gerekir. C++’ın vector’ü de beklenmedik ayırmalar çağırabiliyorsa her zaman en iyi seçenek değildir
    • Bir performans mühendisi olarak sürekli karşılaştığım bir sorun. Performans mimariden başlar; veri yerleşiminin kötü olduğu hot path’lerde sıkıştırıp çıkarılabilecek performansın bir sınırı vardır
      Buna karşılık veri odaklı kod neredeyse her zaman threading ve SIMD desteğini kolaylaştırır
    • Bundan daha temel olarak bellek erişim deseni önemlidir
      İlginçtir ki CPU kodu da eninde sonunda GPU tarzında yazılır; nesne dizileri yerine Parquet tarzı dizilerin struct’ı kullanmak bunun bir yoludur
    • Tablolar, genel amaçlı graph’ları verimli biçimde uygulamanın bir yoludur; graph’ı özelleştiremediğim sürece bildiğim en iyi temsildir