2^51 Tabanı Hilesi (2017)

 (chosenplaintext.ca)
1 puan yazan GN⁺ 2025-05-31 | 1 yorum | WhatsApp'ta paylaş
  • Büyük tamsayı toplama genellikle sayıyı 64 bitlik limb’lere bölerek yapılır; ancak elde aktarımı yayılımı oluştuğunda modern CPU’ların paralel yürütme avantajından tam yararlanmak zorlaşır
  • x86’daki adc, önceki işlemin carry flag’ine bağlı olduğundan komut zincirini serileştirir; bu da Intel Haswell gibi birden çok add komutunu paralel çalıştırabilen yapılarda bile darboğaz olur
  • radix 2^51 gösterimi, 256 bitlik bir değeri dört adet 2^64 basamak yerine beş adet 2^51 basamağa ayırır ve her limb’in boştaki üst bitlerini ara elde aktarımı depolama alanı olarak kullanır
  • Bu, elde aktarımını ortadan kaldıran bir yöntem değildir; birden çok toplama boyunca yayılımı geciktirir ve sonunda normalleştirme aşamasında hepsini birden işler
  • Haswell üzerindeki basit bir benchmark’ta, dönüştürme maliyeti dahil edildiğinde bile üç toplamadan itibaren radix 2^64 yönteminden daha hızlıydı; yineleme sayısı arttıkça avantaj da büyüdü

Büyük tamsayı toplamalarında elde aktarımının neden darboğaz olduğu

  • Kâğıt üzerinde yapılan uzun toplama, birler basamağından başlayarak sağdan sola ilerler
    • Çünkü her basamağın sonucu, sağındaki basamaktan gelen elde aktarımına bağlıdır
    • Soldan başlarsanız, daha sonra oluşan elde aktarımı nedeniyle önceden hesaplanmış üst basamak sonuçlarını yeniden düzeltmeniz gerekir
  • Büyük tamsayı toplama da aynı kısıta sahiptir
    • 256 bitlik x ve y tamsayılarını dört adet 64 bitlik limb’e bölerseniz, aynı konumdaki limb’leri birbirleriyle toplayabilirsiniz
    • Düşük limb’de taşma olursa, bu 1’in daha yüksek limb’e aktarılması gerekir
  • x86’daki adc bu yayılımı işleyen komuttur
    • Önceki işlemin taşma yapıp yapmadığına bakar ve gerekirse 1 ekler
    • Doğru bir 256 bitlik toplama, en düşük limb’den başlayarak add, adc, adc, adc sırasıyla ilerler

adc’nin modern CPU’larda yavaşlamasına yol açan yapı

  • adc genelde sıradan add’den daha yüksek yürütme maliyetine sahiptir
    • adc, carry flag adlı üçüncü bir girdi kullandığı için add’den daha karmaşıktır
    • add’den daha seyrek kullanıldığı için CPU tasarımcılarının adc performansını optimize etmeye yonga alanı ayırma motivasyonu daha düşüktür
  • Daha büyük sorun komut bağımlılığıdır
    • Intel Haswell’de tek bir add komutunun yürütülmesi 1 çevrim sürer
    • İdeal koşullarda Haswell, bir çevrimde en fazla 4 add çalıştırabilir
    • Haswell’de 8 yürütme portu vardır ve bunların 4’ü tamsayı add çalıştırabilir
  • Bağımsız dört add kolayca paralel yürütülebilir
    • Buna karşılık bir adc zincirinde her komut, önceki komutun carry flag çıktısına bağlıdır
    • CPU bu komutları paralelleştiremez; sırayla yürütmek zorundadır
  • SIMD’de kayıp daha da büyür
    • vpaddq, dört adet 64 bitlik toplamayı aynı anda yapar
    • Haswell bir çevrimde iki vpaddq çalıştırabilir
    • Elde aktarımını işlemek için bu paralellikten vazgeçilirse performans avantajı azalır

Kâğıt üstü toplamayla elde aktarımını geciktirmeyi anlamak

  • 10’luk basamak değerlerini koruyup her basamağa girebilecek karakter kümesini genişletirseniz elde aktarımını geciktirebilirsiniz
    • Normal 0-9 yerine A-Z ve * da eklenerek toplam 37 karakter kullanılır
    • Ancak tabanın kendisi 37 değildir; hâlâ 10’luk basamak değerleri korunur
  • Bir basamak 9’u aşsa bile hemen elde aktarmak gerekmez
    • 29 + 1, 30 olarak yazılabileceği gibi 2A, 1K veya U gibi de temsil edilebilir
    • İki sayının her basamağı 9 veya daha küçük olacak şekilde normalleştirilmişse, toplama sırasında elde aktarımı ertelenebilir
  • Bu her girdiye her zaman uygulanamaz
    • 9 + W gibi zaten büyük bir basamak değeri varsa elde aktarımı gerekir
    • Normalleştirilmiş sayılarda en fazla dört sayı, elde aktarımı yapmadan toplanabilir
  • Sonunda yeniden standart 10’luk gösterime normalleştirmek gerekir
    • Sağdan başlayarak her basamakta kaç tane 10 bulunduğu hesaplanır
    • Bu miktar mevcut basamaktan çıkarılır ve sonraki basamağa aktarılır
  • Temel fikir elde aktarımı yayılımını yok etmek değil, onu ara hesaplamalar sırasında depolayıp sonunda bir kez yaymaktır

Bilgisayarda radix 2^51 gösterimi

  • 256 bitlik bir değeri dört adet 2^64 limb’e bölerseniz, her limb 0 ile 2^64−1 arasında değer alabilir
    • Bu, her limb’i 2^64 tabanındaki bir basamak olarak görmektir
  • Donanımın 64 bitlik tamsayı aralığı genişletilemeyeceği için tabanın boyutu küçültülür
    • 256 bitlik değer, dört adet 2^64 basamak yerine beş adet 2^51 basamağa bölünür
    • Her limb hâlâ 64 bitlik tamsayı olarak saklanır; ancak gerçek değer yalnızca 51 veya 52 bit kullanır
  • Boştaki üst bitler ara elde aktarımı depolama alanı olur
    • Her limb’de özgün sayının 51 veya 52 biti bulunur
    • Kalan 12 veya 13 bit, hesaplama sırasında oluşan elde aktarımlarını tutar
  • Bu teknik kriptografi literatüründe radix 2^51 representation olarak adlandırılır
  • Normalleştirilmiş sayılarda, 2^64 olası limb değeri içinde üst 13 bitin taşmasından endişe etmeden en fazla 2^13 tanesini toplayabilirsiniz

52 bitlik en üst limb ve normalleştirme

  • En üst limb’e 52 bit ayrılır
    • Diğer limb’ler 51 bit kullanır
    • En üst limb’in elde aktarımı yok sayılır; böylece 2^256−1’i aşan durumlar saracak şekilde işlenir
    • Bu, C’deki normal boyutlu unsigned tamsayı toplamalarının taşma durumunda sarmasıyla aynıdır
  • radix 2^51 toplama kodu adc zinciri kullanmaz; beş add komutunu bağımsız olarak çalıştırır
    • Dört adet 2^64 limb yöntemine göre add sayısı 4’ten 5’e çıkar
    • Buna karşılık carry flag bağımlılığı olmadığı için paralel yürütme mümkündür
  • Normalleştirme aşamasında her limb’in üst bitleri çıkarılıp bir sonraki üst limb’e eklenir
    • shr 51 ile carry kısmı çıkarılır
    • and 0x0007FFFFFFFFFFFF ile yalnızca alttaki 51 bit bırakılır
    • En üst limb and 0x000FFFFFFFFFFFFF ile temizlenir
  • Normalleştirme, geciktirilmiş elde aktarımı yayılımının sonunda gerçekleştirildiği aşamadır
    • Ara toplamalarda carry flag bağımlılığı oluşturulmaz
    • Son olarak her limb yeniden izin verilen aralığa getirilir

Performans sonuçları ve çıkarmaya genişletme

  • Basit bir benchmark’ta radix 2^51 toplama, Haswell CPU’da daha hızlı sonuç verdi
    • radix 2^51 gösterimine dönüştürme ve geri dönme maliyetleri de buna dahildir
    • Yalnızca üç toplama ile bile radix 2^64 toplamadan daha hızlıydı
    • Toplama sayısı arttıkça tasarruf etkisi de büyüdü
  • Aynı fikir çıkarmaya da genişletilebilir
    • Çıkarmada elde aktarımı negatif carry olur
  • Çıkarmayı desteklemek için limb’ler unsigned değil, signed tamsayılar gibi ele alınır
    • Her basamak değeri pozitif veya negatif olabilir
    • Her limb hem pozitif carry hem de negatif carry saklayabilir
  • Bu değişikliğin bir maliyeti vardır
    • Her limb’in en üst biti işaret biti olarak ayrılır
    • Normalleştirmeler arasında yapılabilecek işlem sayısı 2^13’ten 2^12’ye düşer
  • Verileri daha fazla register’a bölmek ve işlem sayısını artırmak gerekse bile, elde aktarımı bağımlılığını azaltmak genel performansı iyileştirebilir

İlgili okumalar

1 yorum

 
GN⁺ 2025-05-31
Hacker News yorumları

  • En üst limb’i 64 bit, kalan dört limb’in her birini de 48 bit yapmak olmaz mı diye merak ediliyor
    Normalizasyondan önce daha fazla toplamayı biriktirebilir; komut kümesinde işe yarar özellikler varsa bölme/normalizasyon sırasında word hizalamasından da yararlanılabilir ve taşma özellikleri de aynı görünüyor

    • Hedeflerden biri 5 adet 64 bit register ile 256 bit işlem yapmaksa, her word için 256/5 = 51,2 bit kullanılmış oluyor; bu da bir ölçüde ideal bir yerleşim gibi görünüyor
      Genel amaçlı bir büyük tamsayı kütüphanesi için en iyisi olmayabilir; eskiden keyfi bit kaydırmalarını verimli yapan barrel shifter’lar olmadığı için, carry için tam 1 bayt bırakıp 64 bitin 56 bitini kullanmak gibi bir yaklaşım daha iyi olurdu
      RISC-V’de flag olmadığı için bu tartışma oldukça ilgili
    • İki kodlanmış sayının en üst limb’i toplanırsa çok hızlı taşma olur
      Örneğin ikisi de 2^63 ise hemen taşar; wrapping arithmetic için uygun olabilir ama genel durumda doğru değildir
    • Böyle yaparsanız 256 bitlik bir değeri tutmak için özgün yöntemdeki 5 word değil 6 word gerekir; dolayısıyla daha fazla toplama komutu da gerekir

  • AVX512 ile, hatta bir ölçüde AVX2 ile de 256 bit toplama oldukça verimli uygulanabilir; ayrıca register’da daha fazla sayı tutma avantajı da var
    _mm256_add_epi64, karşılaştırma maskesi ve carry maskesini birleştirmek gibi; throughput da daha iyi görünüyor: https://godbolt.org/z/e7zETe8xY
    Bunu 512 bit toplamaya çevirmek de basit; o durumda iyileşme daha büyük olacaktır

  • Yeterince yeni bir x86 CPU’da, örneğin Intel Broadwell ya da AMD Ryzen’de ADX de kullanılabilir; radix 2^51 temsilinin geleneksel olarak avantajlı olduğu Curve25519 gibi durumlarda bile bugün daha hızlı olabilir
    [1] https://en.wikipedia.org/wiki/Intel_ADX

  • İlgili yazılar olarak eski radix 2^51 trick başlıkları var
    The radix 2^51 trick - https://news.ycombinator.com/item?id=33706153 - Kasım 2022
    The radix 2^51 trick (2017) - https://news.ycombinator.com/item?id=23351007 - Mayıs 2020

  • Esas nokta şu: işlem sayısı daha fazla olsa bile, bunlar çoğunlukla bağımsızsa paralel yürütülebilir ve daha hızlı olabilir
    Tersine, işlem sayısı az olsa bile veri bağımlılığı yüzünden seri çalışması gerekiyorsa daha yavaş olabilir; bu fikir uzun tamsayı işlemlerinden çok daha geniş bir alana uygulanır

    • Başka bir yaklaşım, normal 64 bit parçalar kullanıp her toplamayı carry’li ve carry’siz durumlar için paralel olarak spekülatif çalıştırmak, ardından düşük basamaktaki toplamanın carry sonucuna göre doğru tarafı seçmek olabilir
      Toplama sayısı iki katına çıkar ama carry yayılma süresi doğrusal olmaktan çıkıp log(bits) düzeyine iner
    • İyi anlaşılmayan kısım şu: burada gösterilen tekniğin, N değeri toplarken ripple carry’nin N-1 kez değil yalnızca bir kez gerçekleşmesini sağlamaya odaklandığı anlaşılıyor
      Carry işlemi daha karmaşık ama asıl toplamalar paralelleştirilebiliyor
      Ancak en başta giriş sayısını 5 register’lık gruplara bölmek gerektiğine göre, toplamda kazanç sağlamak için o bölme işleminin de paralelleştirilebilir olması gerekmez mi diye düşünülüyor
    • Nvidia bu genel fikrin peşinden gidiyor ve bazı alanlarda oldukça umut verici sonuçlar üretiyor gibi görünüyor
    • Bu kural çok düğümlü süper bilgisayarlara veya buluta kadar ölçeklenir
      10.000 çekirdek kullanabiliyorsanız overhead ihmal edilebilir olur

  • Yalnızca x86_64 ile çalışmış biri, RISC-V’nin carry flag’i atlamasının yanlış olmadığını çok iyi gösteriyor

    • 64 bit limb’leri koruyarak da farklı bir şekilde yapılabilir
      Temel içgörü şu: belirli bir limb konumundaki toplamın tüm bitleri 1 değilse, o konumdan çıkan carry, gelen carry’ye bağlı değildir; yalnızca o konumdaki asıl toplamanın carry üretip üretmediğine bağlıdır
      Toplamın tüm bitleri 1 ise çıkan carry gelen carry ile aynıdır
      Bunu neredeyse her zaman not-taken tahmin edilen koşullu dallanmalarla ifade ederseniz, birden fazla koşullu dallanmanın aynı clock cycle içinde not-taken tahmin edilebildiği varsayımıyla her komut bloğu tamamen paralel yürütülebilir
      2^64 seferde bir çok yavaş çalışır
      4-wide bir makinede 4-limb sayı için adcye göre avantajı yoktur; fakat 8-wide bir makinede 8-limb sayı için kazanç büyümeye başlar
      Mevcut x86_64’te pek yardımcı olmayabilir; ancak M1 de 8-wide olduğundan Apple M serisinde potansiyeli var ve Arm ISA yüzünden etrafından dolaşmak zor olabilir
      Tenstorrent’in 8-wide RISC-V Ascalon’u bu yılın sonlarında veya 2026 başında çıktığında, Ventana, Rivos, XiangShan gibi örneklerle birlikte bunu pratikte görebileceğiz
      Hızlı 1-lane shift varsa geniş SIMD’de de daha iyi çalışır; RISC-V’de buna slideup denir
    • Carry-save addition’ın add-with-carry’den kötü olduğu yaygın durum hâlâ çok
      Bu iki çok word’lü toplama algoritması birbirinin yerine geçmez, kullanım alanları farklıdır; bu yüzden düzgün bir ISA’da ADC/SBB komutları bulunur ve ek maliyetleri de çok küçüktür
      Özel bir flag register’ı şart da değildir; bazı ISA’lar gerektiğinde carry/borrow flag’ini genel amaçlı register’da saklar
      RISC-V’de carry olmaması en kötü özellik değil; daha kötüsü tamsayı taşma flag’inin olmamasıdır
      Güvenli yazıldığı iddia edilen programlarda tamsayı taşmasını algılamak zorunludur; bunu yazılımla dolanmak, carry yokluğunu dolanmaya kıyasla ulaşılabilir performansı çok daha fazla düşürür
    • Bu akış eninde sonunda C’nin carry flag’i atlamasından gelen bir sonuç ve pratikte carry amacıyla neredeyse hiç kullanılmaz oldu
    • Carry flag zaten yavaşsa “RISC-V GMP tartışması da neydi?” diye düşünen tek kişi ben değildim

  • Bu radix trick veri yapıları için de geçerli
    Okasaki’nin 『Purely Functional Data Structures』 kitabında iyi bir örnek var

  • Bu yazıyı birkaç ay önce görmüş olsaydım iyi olurdu
    Bir buffer’ı keyfi bir tabanda encode/decode etmeye çalışırken, carry’nin buffer’ın sonuna kadar yayılabileceği ve bunun algoritmayı ciddi biçimde yavaşlatacağı sonucuna çok geç vardım
    Sonunda çözüm de bu trick’e benzer bir şey oldu: buffer’ı chunk’lara böldüm ve carry’yi işlemek için boş alan bıraktım
    Tam olarak aynı değil; biraz israf bit bırakarak depolama alanı veya ağ bant genişliğini çok az daha fazla kullanıp hesaplamayı azalttım
    Carry’leri bu şekilde biriktirip daha sonraki bir aşamada çözmenin iki işi birden sağlayıp sağlayamayacağını merak ediyorum; ama bu sadece temenni de olabilir

  • HN yönergelerine göre başlığı düzenlememek gerektiğini biliyorum; ama küçük bir iddiayı fazla genişleten clickbait başlıklar hoşuma gitmiyor
    Bu yazının başlığı “Bazı x86 mimarilerinde carry bağımlılığı yüzünden pipeline’ı yavaşlatmadan 64 bit tamsayıları paralel toplamak için radix 2^51 trick’i” gibi bir şey olmalıydı