2^51 Tabanı Hilesi (2017)

 (chosenplaintext.ca)
1 puan yazan GN⁺ 2025-05-31 | 1 yorum | WhatsApp'ta paylaş
  • Büyük tamsayı işlemlerinde ortaya çıkan carry (elde) problemi, işlemlerin paralelleştirilmesini zorlaştıran başlıca nedenlerden biridir
  • x86 mimarisinde, carry işleme için kullanılan adc komutu, normal add komutundan daha yavaştır ve art arda carry işlemleri paralel yürütmeyi kısıtlar
  • Radix 2^51 gösterimi kullanılırsa carry yayılımı geciktirilerek daha fazla toplama işlemi daha hızlı yapılabilir
  • Her limb'e (parça değer) yalnızca 51 veya 52 bit ayrılır; kalan üst bit alanı geçici carry deposu olarak kullanılır
  • Bu teknik, ek kayıtçı kullanımı ve dönüşüm maliyetine rağmen, pratikte 2^64 tabanından daha iyi performans sağlar

Hızlı toplama ve çıkarma: carry problemi

  • Büyük tamsayı toplamalarında, insanların eldeyi basamak basamak elle taşımasına benzer şekilde, bilgisayarlar da carry nedeniyle toplama algoritmasını paralelleştirmekte zorlanır
  • Temelde sağdan (düşük basamak) başlayıp tek tek toplar, her basamakta oluşan carry'yi sola (yüksek basamak) taşırız
  • Eğer toplamaya soldan başlanırsa, önceki carry bir sonraki basamaktaki işlemi etkiler; bu yüzden işlem sırası paralelleştirilemez

Bilgisayarda carry işleme

  • Bilgisayarlar toplama işlemlerini 64 bit tamsayılar üzerinden yapar
  • 256 bitlik bir tamsayıyı 64 bitlik 4 limb'e bölüp toplamayı paralel yürütmek mümkünmüş gibi görünse de, gerçekte doğru sonucu üretmek için overflow (carry) işlenmelidir
  • x86'da carry işlemeyi otomatik yapan adc (add with carry) komutu bulunur

Performans düşüşünün nedeni

  • adc komutu, carry flag adlı ek bir girdiye ihtiyaç duyduğu için, basit add komutuna kıyasla daha düşük performans verir
  • Haswell mimarisinde add birden fazla portta paralel çalışabilirken, adc için seri (ardışık) yürütme kaçınılmazdır
  • Özellikle SIMD komutları (vpaddq vb.) kullanıldığında, carry içermeyen paralel toplama çok daha hızlıdır

Carry'yi geciktirme fikri (kâğıt üzerindeki örnek)

  • Carry'yi azaltmak için, basamak aralığı genişletilerek (örneğin 0-9 yerine 0-9, A-Z ve * ile toplam 37 basamak) geçici olarak carry olmadan birden çok sayı toplanabilir
  • Böylece carry yayılımı olmadan birden fazla toplama yapılır ve en sonda carry tek seferde temizlenir (normalization)
  • Bu kavram, carry birikimi ile yayılımını ayırarak carry işlemenin yalnızca son aşamada yapılmasını sağlar
  • Gerçek hesaplamada, bir basamağın değeri taban değerini aşarsa carry sağdan başlayarak sırayla biriktirilip yansıtılır

Carry geciktirmenin bilgisayardaki uygulaması (Radix 2^51 hilesi)

  • Bilgisayarda carry yayılımını azaltmak için radix 2^51 gösterimi kullanılır
  • 256 bit, 64 bitlik 4 limb yerine 51~52 bitlik 5 limb'e bölünür
    • Her limb'in üstteki 12~13 biti geçici carry deposu olarak işlev görür
  • Bu yöntemde her limb 2^64 değer aralığını korurken, gerçek işlem sırasında carry kolay kolay oluşmaz; bu nedenle birçok işlem carry olmadan paralel biçimde yürütülebilir
  • Yaklaşık 2^13 ardışık işlemden sonra tek seferlik normalization (normalleştirme) gerekir
  • Haswell CPU'da radix 2^51 uygulandıktan sonra, carry'siz basit toplama işlemleri art arda yürütülerek genel radix 2^64 yaklaşımına göre performans ciddi biçimde artar
  • Normalization için gereken carry propagation en sonda yalnızca bir kez yapılır

Kod örneği

  • Değer 5 kayıtçıya bölünerek yerleştirilir ve carry'siz toplama yapılabilir
  • Normalization, her limb'in üst bitlerini çıkarıp yanındaki limb'e ekleyerek ve kendi carry değerini sıfırlayarak tekrarlanır

Çıkarmaya genişletme

  • Çıkarma işlemi de benzer şekilde uygulanabilir
  • Bu durumda carry negatif de olabileceğinden, limb'ler signed integer olarak ele alınır
  • Limb'in en yüksek biti işaret biti olarak ayrıldığından, toplamaya kıyasla bir seferde yapılabilecek işlem sayısı bir miktar azalır

Sonuç

  • Carry'ye dayanıklı (geciktirici) teknik, limb sayısının artmasına ve ek dönüşüm işlemlerine rağmen toplam işlem performansını pratikte belirgin biçimde artırır
  • Radix 2^51 hilesi, büyük ölçekli tamsayı işlemleri, kriptografi ve yüksek performans gerektiren alanlarda yaygın olarak kullanılır
  • Bu teknik, gerçek donanım ve algoritma performansını optimize etmek için önemli bir fikirdir

İlgili okumalar

1 yorum

 
GN⁺ 2025-05-31
Hacker News görüşleri

  • 2^51 sayısını görünce ilk başta bunun double türünde tamsayı saklama meselesi olduğunu sandım; ama aslında bir Integer’ın double içinde tam olarak temsil edilebildiği üst sınırın 2^53-1 olduğunu fark ettim

  • AVX512 (ve bir ölçüde AVX2), 256 bit toplama işlemlerini oldukça verimli biçimde uygulayabilecek bir ortam sunuyor; ayrıca daha fazla sayıyı register’larda tutabilme avantajı da var
    Doğrudan bir örnek aşağıdaki kod gibi çalışıyor

__m256i s = _mm256_add_epi64(a, b);
const __m256i all_ones = _mm256_set1_epi64x(~0);
int g = _mm256_cmpgt_epu64_mask(a, s);
int p = _mm256_cmpeq_epu64_mask(s, all_ones);
int carries = ((g << 1) + p) ^ p;

__m256i ret = _mm256_mask_sub_epi64(s, carries, s, all_ones);

Bunun throughput’u da iyileştirdiği görülüyor; gerçek kod örneğine godbolt.org üzerinde bakılabilir
Bu mantığı 512 bit toplama işlemlerine genişletmek de oldukça basit

  • Özellikle bazı Intel CPU mimarilerinde, yalnızca AVX512 komutlarını kullanmak bile tüm işlemcinin clock hızını düşürüp toplam performansın tutarsızlaşmasına ya da hatta kötüleşmesine yol açabilir
    İlgili referans stackoverflow bağlantısında görülebilir

  • “13 bit yerine 12 bit kullanılamaz mı?” sorusuna karşılık burada en üst bitin (limb’in) carry işlemi yok sayılıyor; böylece overflow durumunda wraparound biçiminde çalışıyor
    Bunun sonucu olarak en üst limb’e 52 bit ayrılıyor; bu da diğer limb’lere göre daha çabuk dolması gibi bir dezavantaj getirse de, C dilindeki unsigned integer toplamasına benzer davranıyor
    O halde en üst limb’e 64 bit, kalan dört limb’e de 48’er bit ayırmak nasıl olur diye öneriliyor
    Bu durumda normalize etmeden önce daha fazla işlem biriktirmek mümkün olur ve word alignment gibi avantajlar sağlanır
    Overflow işleme özelliği de aynı kalır

    • En üst limb’e tek başına 64 bit ayırırsanız, iki sayının limb’lerini topladığınızda overflow çok hızlı oluşur
      Örneğin ikisi de 2^63 ise hemen overflow olur
      Wraparound aritmetiğinde bu sorun değildir ama genel durumda uygun olmaz

    • Böyle bir yapıda, OP’deki gibi 5 değil 6 word gerekir
      Komut sayısı da daha fazla olur

    • Amaç, 256 bit matematiği 5 adet 64 bit register ile çözmek
      Yani her word için ideal dağılım 256/5 = 51.2 bittir
      Bu, yalnızca 256 bit içinse sorun değil ama genel amaçlı bir big-int kütüphanesi için en iyi seçenek değil
      Eskiden tek bir carry için tam 1 byte ayırmaya çalışma gibi bir arka plan vardı ve barrel shifter’ın olmadığı dönemlerde hizalama uğruna 64 bitin sadece 56 bitini kullanmak tercih edilirdi
      RISC-V’de donanımsal flag olmadığı için bu tür tartışmalar daha da önemli

  • Modern x86 CPU’larda (ör. Intel Broadwell, AMD Ryzen), Intel ADX komutları kullanılarak 2^51 radix gösterimi, geleneksel olarak güçlü olduğu durumlarda bile (ör. Curve25519) daha hızlı olabilir

  • İlgili tartışma bağlantıları

  • Asıl ders şu: işlemler birbirinden bağımsızsa, daha fazla işlemi paralel yürütmek çoğu zaman daha hızlı olabilir
    Buna karşılık bağımlılıklar nedeniyle sırayla yürütülmeleri gerekiyorsa, işlem sayısı az olsa bile daha yavaş olabilirler
    Bu fikir yalnızca uzun tamsayı aritmetiğinde değil, pek çok alana uygulanabilir

    • 64 bit chunk’lara bölüp carry oluşup oluşmamasına göre iki olası durumu önceden paralel biçimde hesaplamak ve ardından gerçek carry sonucuna göre doğru hesabı seçmek öneriliyor
      Bu yöntemde toplama sayısı iki katına çıkıyor ama yayılma hızı doğrusal değil log(bits) seviyesine iniyor

    • Bu teknikte anlamakta zorlandığım nokta, özünde ripple carry’nin N değeri toplarken N-1 kez çalışmasını tek seferlik bir işleme indirgemesi
      Carry işlemenin kendisi daha karmaşık hale geliyor ama toplama paralelleştirilebiliyor
      Yine de tüm verimin anlamlı olabilmesi için giriş sayılarını 5 register’lık parçalara ayırma işinin de paralelleştirilmesi gerekir

    • Bu kural, on binlerce node içeren süper bilgisayarlardan bulut ölçeğine kadar genişletilebilir
      Yeterince çok çekirdek kullanılabiliyorsa ek yük ihmal edilebilir düzeyde kalır

    • NVidia da bu fikirle ilgileniyor ve birçok alanda iyi sonuçlar elde ediyor

  • HN yönergelerinde başlığa görüş eklenmemesi gerektiği yazsa da, aşırı abartılı clickbait başlıkları sevmiyorum
    “Bazı x86 mimarilerinde carry bağımlılığı olmadan 64 bit tamsayı paralel toplamasını mümkün kılan radix 2^51 hilesi” gibi daha sınırlı bir başlık daha doğru olurdu diye düşünüyorum

  • Bu yazıyı birkaç ay daha erken okumuş olsaydım işime yarardı diye hayıflanıyorum
    Bir buffer’ı keyfi bir radix ile encode/decode ederken carry’nin tüm buffer boyunca yayılması yüzünden algoritmanın ciddi biçimde yavaşladığını yaşamıştım
    Sonunda chunk’lara ayırıp “boş alan” bırakarak carry’leri işledim; bu da bu hileye benzer görünüyor
    Pratikte bazı bitleri feda edip işlem miktarından ya da ağ bant genişliğinden tasarruf etmeyi seçmiştim
    Böyle carry işlemlerinin de sonradan topluca ele alınıp alınamayacağını merak ediyorum
    Neredeyse tüm avantajları bir araya getiren bir yapı olmasını umuyorum

  • Yalnızca x86_64 ortamında çalışmış biri olarak, RISC-V’de carry flag olmamasının mutlaka yanlış bir yaklaşım olmadığını bunun gayet net gösterdiğini düşünüyorum

    • Bunun dışında, 64 bit limb’leri koruyup her şeyi uint64_t değişkenlerle carry-safe şekilde toplamanın bir yolu da anlatılıyor
      Akış kabaca şöyle
    s0 += a0;
s1 += a1;
s2 += a2;
s3 += a3;
c0 = s0 < a0; // RISC-V sltu
c1 = s1 < a1;
c2 = s2 < a2;
if (s1 == -1) goto propagate0;
check_s2:
if (s2 == -1) goto propagate1;
add_carries:
s1 += c0;
s2 += c1;
s3 += c2;
goto done;
propagate0: c1 = c0; goto check_s2;
propagate1: c2 = c1; goto add_carries;
done:

    Kilit nokta şu: toplama sonucu olan limb tümüyle 1 olmadıkça, o limb’in carry-out’u carry-in’e bağlı değildir; yalnızca eklenen özgün değerlere bağlıdır
    Buna karşılık değer tümüyle 1 ise, carry-out = carry-in olur
    Tahmin gereksinimi neredeyse olmayan bir branch yapısı varsa tamamen paralel yürütme mümkün
    Olasılıksal olarak yalnızca 2^64te 1 oranında yavaşlıyor ama 4-wide makinelerde büyük kazanç sağlamıyor
    8-wide makinelerde veya 8-limb yapılarında anlamlı performans artışı olabilir
    x86_64’e pek uygun değil ama Apple M* serisi gibi 8-wide makinelerde işe yarayabilir
    Tenstorrent’in 8-wide RISC-V Ascalon işlemcisi, Ventana, Rivos, XiangShan gibi tasarımlarda gelecek vaat ediyor
    SIMD yapılarında ve hızlı 1-lane shift (slideup) komutu olan mimarilerde etkisi en üst düzeye çıkabilir

    • Carry-save toplama her zaman add-with-carry’den daha iyi değildir
      Bu iki tür multi-word toplama algoritması birbirinin yerine geçmez; her birinin kendi artı ve eksileri vardır
      Bu yüzden ADC/SBB komutları ISA içinde temel olarak yer almalı; register tabanlı flag saklama da mümkün olabilir
      RISC-V’de daha ciddi eksik, integer overflow flag’in olmamasıdır
      Overflow tespiti için yazılımsal dolambaçlar gerektiğinde performans kaybı, carry bitini yazılımla taklit etmenin maliyetinden çok daha büyüktür

    • RISC-V’de carry flag bulunmaması, C dilinin ikili carry flag’i göz ardı etmesinden türemiştir
      Uygulamada carry flag kullanımı gerçekten de oldukça daha seyrektir

    • “Madem carry flag zaten yavaşsa, risc5 gmp tartışması neden çıkmıştı?” diye düşünen tek kişi ben değilmişim

  • 'Radix trick' veri yapılarında da uygulanabilir
    Okasaki’nin 'Purely Functional Data Structures' kitabında da ilginç bir örnek var