Tam sayı karekök komutunu uygulayan bir işlemci var mıydı?

 (retrocomputing.stackexchange.com)
1 puan yazan GN⁺ 2024-04-08 | 1 yorum | WhatsApp'ta paylaş
  • Tartışmanın odağı, yaygın kayan nokta sqrt değil, tam sayı karekökünün CPU komutu ya da donanım özelliği olarak sunulup sunulmadığı; Nintendo DS’in divider/square-rooter birimi buna benzer olsa da yerel bir komut değil
  • Harris RTX 2000 Forth CPU ve askeri sınıf RTX 2010, çok aşamalı square root komutu sunan örnekler arasında gösteriliyor; RTX 2000’de sonuç, 1 kez setup ve 15 kez step ile elde ediliyordu
  • Daha eski bir örnek olan ENIAC, 1946’da decimal integer accumulator’ları denetleyen bir divider/square-rooter unit ile saniyede en fazla 40 bölme veya 3 karekök işlemi yapabiliyordu
  • Tam sayı karekökü, hızlı bir tam sayı çarpanı ve yeterli hassasiyet gerektirdiği için tarihsel CPU’lar açısından maliyetliydi; ARMv8’teki frsqrte/frsqrts gibi kestirim ve yinelemeyi ayıran yaklaşımlar da doğruluk-hız dengesini ayarlamaya yarıyor
  • Quake tarzı inverse square root, modern donanımda artık genel bir performans üstünlüğü sunmuyor; tablo arama, enterpolasyon, Halley türü yinelemeler ve sabit noktalı böl-ve-yönet yöntemleri, uygulama ortamına göre değişen seçenekler olarak öne çıkıyor

Sorunun kapsamı ve Nintendo DS örneği

  • Soru, tam sayı karekök komutunu gerçekten uygulayan işlemciler olup olmadığını ele alıyor
  • Kayan noktalı square root komutları yaygın olsa da, yalnızca tam sayıya yönelik square root komutlarının soru sahibinin hiç görmediği varsayımıyla başlıyor
  • Nintendo DS’te bellek eşlemeli bir integer divider/square rooter vardı
    • ARM işlemcisinde FPU veya donanımsal divider bulunmadığından 3D hesaplamalara yardımcı oluyordu
    • Ancak bunun yerel işlemci komutu olmaması, sorudaki temel ayrım noktası

Harris RTX 2000 ve RTX 2010

  • Harris RTX 2000 Forth CPU, çok aşamalı square root komutu sunan bir örnek olarak anılıyor
  • Askeri sınıf kardeşi RTX 2010 da aynı aileden işlevler sunuyor
  • İlgili kaynak olarak Stack Computers: RTX 2000 bağlantısı veriliyor
  • RTX2000 Family Programmer’s Reference Manual belgesine göre bu özellik, yinelemeli bir square root işlemine daha yakın ve son değeri almak için 1 setup komutu ile 15 step komutu çalıştırılıyor
  • Ken Lyons’ın “A Fast Method for Finding an Integer Square Root” çalışması da RTX2000 ailesinin donanım uygulaması ve programlama örneklerini ele alan bir kaynak olarak anılıyor

ENIAC’ın divider/square-rooter unit’i

  • 1946 tarihli ENIAC da tam sayı karekökü donanımına örnek sayılıyor
  • Aktarılan açıklamaya göre ENIAC, 4 accumulator’ı özel bir multiplier unit ile denetleyerek saniyede en fazla 385 çarpma yapabiliyordu
  • 5 accumulator ise özel divider/square-rooter unit tarafından denetleniyor ve saniyede en fazla 40 bölme veya 3 karekök işlemi gerçekleştiriyordu
  • ENIAC’taki accumulator’lar decimal integer olarak çalışıyordu

Tam sayı karekökü uygulamanın neden zor olduğu

  • Bir yanıt, Newton-Raphson yinelemesiyle ters karekök bulup sonra bunu asıl değerle çarpma yöntemini, square root hesabı için verimli bir yaklaşım olarak açıklıyor
  • Bu yöntem “Quake yöntemi” olarak biliniyor ve modern CPU ile GPU’larda başlangıç kestirimi komutu ile yineleme komutunun ayrıldığı daha genel örnekleri bulunuyor
  • Bu yaklaşımın temel kısıtı, hızlı bir multiplier gerektirmesi
    • Kayan noktalı sqrt için hızlı bir FP multiplier gerekir ve FPU bunu içerir
    • Tam sayı sqrt için hızlı bir integer multiplier gerekir; ancak tarihsel olarak çoğu CPU’da böyle bir donanım bulunmadığı belirtiliyor
    • Yeterli hassasiyet elde etmek için, giriş genişliğinin iki katı genişlikte hızlı bir multiplier gerekliliği de ekleniyor
  • Hassasiyet gereksinimi her zaman aynı olmadığından, frsqrte ve frsqrts gibi kestirim ile yinelemeyi ayıran yaklaşımlar, istenen hız-doğruluk dengesi için yineleme sayısını ayarlamaya imkân veriyor

Quake tekniği ve modern sqrt uygulamaları tartışması

  • Başka bir yanıt, Quake numarasının en verimli yöntem olduğu iddiasının uzun süredir geçerli olmadığını ve bunun yalnızca belirli donanımlarda düşük kaliteli float sonuçlar üretmek için anlamlı olduğunu savunuyor
  • Modern çiplerde yerel sqrt komutunun çok daha hızlı olduğu, hatta sık sık birkaç saat çevrimi düzeyinde çalıştığı belirtiliyor
  • Daha hızlı bir yöntem olarak, eşit aralıklı olmayan değerlerden oluşan bir tabloyu saklayıp iki değeri hızlıca getirerek enterpolasyon yapmak, ardından base-2 exponent’i shift etmek ve gerekirse Newton-Raphson’dan daha iyi bir yinelemeyi bir kez uygulamak öneriliyor
  • Halley türü yöntemler ve çeşitli yinelemeler, Newton-Raphson’dan daha hızlı yakınsama sağlayabiliyor; ancak gerçek hız, her işlemin maliyetine bağlı
  • Yalnızca tam sayı aralığı, örneğin 2^32, için aynı fikirler sabit nokta biçiminde uygulanabiliyor
    • Donanım için basit bir yöntem olarak divide and conquer öneriliyor
    • Her 8 bitin, 256 sabit nokta değerinden oluşan bir tabloya eşlenmesi; ardından paralel sorgulama yapılıp 3 çarpmanın 2’si paralel yürütülerek 32 bitlik bir değer elde edilmesi ve sonucun truncate edilmesi mümkün
  • sqrt optimizasyonu üzerine araştırmalar sürüyor ve INRIA HAL çalışması buna örnek olarak veriliyor

İlgili okumalar

1 yorum

 
GN⁺ 2024-04-08
Hacker News yorumları

  • AArch64 NEON’da URSQRTE komutu var; bu da aslında ilk soruya sanılandan daha yakın
    32 bitlik bir değeri kesir kısmı 32 bit olan sabit noktalı bir tam sayı olarak görürseniz, temsil aralığı 0’dan 1-ε’ye kadar eşit aralıklıdır ve ε=2^-32’dir
    URSQRTE yaklaşık ters karekökü hesaplar, ardından ikiye böler ve sonucu 0 ile 1-ε aralığına sınırlar
    Sabit noktalı tam sayı tam anlamıyla bir tam sayı değildir ve yaklaşık ters karekök de karekök değildir; ama epey yakın bir noktaya kadar gidilebilir
    İlgili FRSQRTE ise çok daha genel bir komuttur ve 32 bit kayan nokta için yaklaşık ters karekök sağlar

    • Böyle karmaşık bir komutun, daha basit komutlara kolayca ayrılabilecek olmasına rağmen AArch64’e girecek kadar fayda sağladığı işin ne olduğunu merak ediyorum

  • Tek bir saat çevriminde mümkün mü derseniz, çok büyük bir arama tablosu varsa mümkün
    Bir saat çevrimi içinde seri mantık kapılarından ne kadarını çalıştırabildiğinize bağlı olarak boyutu küçültmek de mümkün olabilir
    Örneğin 10000’in ikili karekökü, 100’ün kareköküne oldukça benzer; sadece sıfır sayısı farklı sayılabilir

    • Kayan nokta ters karekök tahmini komutu (frsqrte) genellikle bu tür bir tablo aramasıyla uygulanır; mantisin bazı bitleri ve üssün en düşük anlamlı bitiyle indekslenir
      Hassasiyet genelde bf16 (ARM, RISC-V) ya da fp16 (x86) seviyesine yakındır; daha yüksek hassasiyet gerekiyorsa sonrasında birkaç Newton-Raphson yinelemesi yapılır
    • Girdinin bit sayısı n olduğunda, tam sayı karekökü yalnızca kaydırma ve toplama ile n/2 yinelemede hesaplanabilir
      Her adımda sonuç n_old üzerinde yeni bitin ayarlanıp ayarlanmayacağı n2_new = (n_old + (1 << bit))^2 = n2_old + (n_old << (bit + 1)) + (1 << (bit*2)) ile hesaplanır
      Ardından asıl operand ile karşılaştırılır; büyük ya da eşitse 1) sonuçta bit ayarlanır ve 2) n2_old, n2_new olarak güncellenir
      Uygun bir mikrokod komut kümesi ve ALU varsa n/2 ya da belki n saat çevriminde yapılabilir; daha da optimize edilirse n, operandda soldan açık olan en yüksek bitin indeksine kadar azaltılabilir
    • Aptalca bir soru olabilir ama büyük bir tablo aramasının gerçekten de tek saat çevriminde bittiği durumlar var mı?
      Büyük bir arama tablosuysa bellekten getirilmesi gerekir; o zaman önbellek ve bellek hiyerarşisi gecikmesi olmaz mı diye düşünüyorum
    • Böyle bakınca dünyadaki herhangi bir algoritma 1 saat çevriminde çalıştırılabilirmiş gibi geliyor
    • Tam sayı karekökü sanıldığından fena değildir; büyük/küçük arama tablosunda yalnızca N^0.5 adet giriş saklamak yeterli
      Her cevap N için N^2’yi saklamak gibi
      16 bit tam sayılar için uygulanabilir, 32 bit için belki mümkün; ama 64 bit için zor

  • “İşlemci” tanımını elektromekanik cihazlara kadar genişletirsek, Friden SRQ motor dışında tek bir elektronik parça olmadan, yalnızca toplama ve kaydırma ile karekök hesaplayabiliyordu
    Ondalık noktanın konumunu elle ayarlamak gerekiyordu; bu yüzden teknik olarak tam sayı işlemi de sayılabilir
    Video: https://youtu.be/o44a1ao5h8w

  • 1 + 3 + 5 + ... + 2k + 1 dizisini kullanarak herhangi bir tam sayının tam sayı karekökü bulunamaz mı?
    Temelde bu dizide kendi sayımdan küçük ya da ona eşit en yakın terimin k değerini bulmak

    • Fikri açıklayabilir misin?
      Tanım gereği bu bir algoritma, ama safça uygulanırsa 32 bit sayılarda bile çok yavaş
      Bu noktada doğrudan ikili arama yapmak çok daha hızlı olur
    • Daha iyi yöntem, (x+y)^2=x^2+2xy+y^2 açılımını, herhangi bir tabanda 2n basamaklı bir sayının karekökünün en fazla n basamaklı olduğu gözlemiyle birlikte kullanmak olabilir
      Kalem kâğıtla karekökü elle hesaplamanın yaygın yöntemiyle aynı
      Bunu 8 bitlik parçalar halinde işlersek yalnızca 8 bitlik sayıların karekökü için bir arama tablosu yeterli olur
    • O diziyi baştan sona yinelemeyi kastediyorsan, girdi bit uzunluğuna göre üstel zaman alır
    • Bu, klasik utandırıcı derecede kolay paralelleştirilebilir işlerden biri

  • Aşağıdaki yanıttaki şu kısım güldürdü:

    My implementation of square root using binary search, that doesn't depend on a multiplier. Only basic ALU instructions are used. It is vigorously undocumented. I have no idea what I wrote but it seems to work.
    Akıllı kod yazınca sonradan o kodun nasıl çalıştığını hatırlamama ihtimalinin yüksek olduğuna dair iyi bir hatırlatma

  • Biraz aşağı inip okumak gerekiyor ama cevabın ENIAC olması gerçekten komik

    • Birçok insan, kendisi okula başlamadan önceki her şeyin ilkel olduğunu ve zar zor çalıştığını düşünüyor :)
      Biraz okursanız bunun tam tersi olduğunu görürsünüz
      Bugünün akıllıca fikirlerinin çoğu 1940-60’ların bilgisayarlarında zaten kullanılıyordu ve yeni yarı iletken çiplerde yeniden kullanılıyor
      Ardışık düzenleme, sırasız yürütme, çok çekirdek gibi şeyler buna dahil
      Eski donanım biraz “kaba” olabilir, ama mimarilerde çok zeki teknikler kullanılmıştı

  • 2 ^ (1/2 * Log2(X)) = sqrt(X)
    Log2(x) yerine öndeki sıfırları sayma kullanılırsa gerçekten kaba bir yaklaşık değer elde edilebilir
    Log(2) daha iyi yaklaştırılırsa cevaba daha da yaklaşılabilir

  • En yakın tam sayıya kadar doğru cevap değil de çok kaba bir yaklaşık değer isteniyorsa, en baştaki 1 bitinin konumunun yarısı kadar sağa kaydırmak yeterli
    Neredeyse tüm işlemcilerde kaydırma komutları var; FLO (Find Leading One) veya FFS (Find First Set) gibi komutlar da ne kadar yok denecek kadar yaygın görünüyor
    Bazı kullanım alanlarında bu tür çok kaba bir yaklaşım, doğru cevap kadar faydalı olabilir
    Örneğin sonrasında Newton-Raphson yinelemesi için yalnızca uygun bir başlangıç değeri gerektiğinde böyle
    Elbette sağa kaydırma hilesi, daha doğru karekök hesaplamasının başlangıç değeri olarak da gayet iyi :P

    • Burada DOOM meselesi mi devreye giriyor?
      Artık epey ünlü bir internet hikâyesi; Carmack ve sihirli bir 32 bit sayı var
    • İlginç bir bilgi: FFS ve onun genellemesi FNS CUDA’da var: https://docs.nvidia.com/cuda/cuda-math-api/index.html#group_...
      Kişisel olarak sevdiğim bir diğer CUDA donanım yerleşik fonksiyonu log2

  • Hatırladığım kadarıyla çoğu, belki de tüm sabit noktalı DSP’lerde karekök komutu ya da yardımcı komutu var

  • 6502 hayranları için yarı ilgili ve ilginç olabilecek karekök algoritmaları tam analizi: https://github.com/TobyLobster/sqrt_test