CORDIC algoritmasının zihnimde kalıcı olarak yer etmesinin nedeni

 (github.com/francisrstokes)
3 puan yazan GN⁺ 2024-05-12 | 1 yorum | WhatsApp'ta paylaş
  • CORDIC, FPU ya da büyük lookup tabloları olmadan sin, cos, tan gibi trigonometrik fonksiyonları hesaplamak için karmaşık işlemleri toplama ve bit kaydırma ağırlıklı hale getiren bir algoritmadır
  • Bu yaklaşım, yüksek performanslı sistemlerden çok gömülü ortamlarda, özellikle düşük performanslı mikrodenetleyiciler ve FPGA'lerde kullanışlıdır; değerini yalnızca hızla değerlendirmek zordur
  • Kayan nokta yerine sabit nokta kullanılırsa int32_t içindeki üst 16 bit tam sayı kısmı, alt 16 bit kesir kısmı olarak ayrılabilir ve yaklaşık -32768.99997 ile 32767.99997 arası temsil edilebilir
  • Vektörü hedef açıya doğru giderek küçülen açılarla döndürüp atan(2**-i) tablosundaki 16 değeri ve başlangıç değeri olarak x=39796 kullanırsanız, her yinelemede çarpma işlemini bit kaydırma ile değiştirebilirsiniz
  • Örnek açı 0.9152 için 16 yineleme yapıldığında sin(0.9152) mutlak hatası 0.00000956, cos(0.9152) mutlak hatası ise 0.0000434 seviyesine iner

CORDIC'in uygun olduğu hesaplama ortamı

  • CORDIC, sin, cos, tan gibi trigonometrik fonksiyonları düşük güç tüketimli donanımlarda hesaplamak için kullanılan bir algoritmadır
  • FPU, yani kayan nokta işlem birimi olmayan ya da büyük lookup tabloları kullanmanın zor olduğu ortamlarda da çalışır
  • Gerçek hesaplama, basit toplama ve bit kaydırma işlemleri etrafında şekillenir
  • Vektör matematiği, trigonometri, yakınsama ve bilgisayar bilimi fikirlerini birleştirerek karmaşık fonksiyonları basit işlemlerle yaklaşıklar
  • Yüksek performanslı donanımlarda bu tekniğe mutlaka ihtiyaç olmayabilir
    • Başlıca kullanım alanı gömülü ortamlardır
    • Özellikle düşük performanslı mikrodenetleyiciler ve FPGA'ler için uygundur
    • Daha hızlı donanımlar veya çevre birimleri bulunabilir, ancak kullanışlılığın tek ölçütü hız değildir

Kayan noktadan kaçınan sabit nokta gösterimi

  • sin(x) gibi -1.0 ile 1.0 arasında değer üreten bir fonksiyonun mutlaka kayan nokta ile gösterilmesi gerekmez
  • Sabit nokta, ondalık noktanın yerini tamsayı tipi içinde sabitleyerek rasyonel sayıları ifade eder
  • Örnekte int32_t, üst 16 bit tam sayı kısmı ve alt 16 bit kesir kısmı olacak şekilde bölünür
    • Bu durumda aralık yaklaşık -32768.99997 ile 32767.99997 olur
    • Ondalık noktanın yeri değiştikçe tam sayı aralığı ile kesir hassasiyeti arasında takas yapılabilir
  • Değerin kendisi yine int32_t olarak kalır; ek anlamı bit düzenine programcı yükler

Sabit noktaya dönüştürme ve temel işlemler

  • Kesir hassasiyeti 16 bitse 42.01 gibi bir float değeri (1 << 16) ile çarparak sabit nokta değerine dönüştürebilirsiniz
    • 42.01 * (1 << 16) değeri int32_t'ye cast edildiğinde 2753167 olur
    • Tekrar float'a çevirmek için 2753167 / (1 << 16) hesaplanır ve yaklaşık 42.0099945 elde edilir
  • Hiç kayan nokta kullanmadan 1.5 gibi bir değeri doğrudan encode etmek de mümkündür
    • Tam sayı kısmı 1, (1 << 16) ile yukarı taşınır
    • Kesir kısmının yarısı, 0x0000 ile 0xffff arasındaki orta değer olan 0x7fff olarak alınabilir
    • Bu yöntemin sonucu ondalık olarak 98303 olur
  • Aynı ölçekleme katsayısını kullanan değerler arasında toplama ve çıkarma doğrudan çalışır
  • Çarpma için iki sabit nokta değeri çarpılır, ardından sonuç ölçekleme katsayısı kadar sağa kaydırılır
  • Bölme için bölünen, önce ölçekleme katsayısı kadar sola kaydırılır; ardından bölenle bölünerek ek hassasiyet kazanılır

Vektör döndürerek trigonometrik fonksiyonları yaklaşık hesaplamak

  • CORDIC, “co-ordinate rotation digital computer” ifadesinin kısaltmasıdır ve 1950'lerin ortasında geliştirilmiştir
  • Temel fikir, birim çember üzerindeki bir vektörü giderek küçülen açılarla döndürerek hedef açıya ulaşıldığında vektör bileşenlerinin sinüs ve kosinüs değerlerine karşılık gelmesini sağlamaktır
  • Bu süreç ikili aramaya benzer biçimde ilerler
    • Hedef açı yönünde büyük bir açıyla hareket edilir
    • Hedefin aşılıp aşılmadığı kontrol edilir
    • Ardından saat yönünde veya saat yönünün tersine, daha küçük açılarla döndürme tekrarlanır
  • Örneğin sin(0.7) hesaplanırken başlangıç vektörü (1, 0) ve hedef açı 0.7 radyandır
    • İlk olarak 0.7853 radyan, yani 45˚, saat yönünün tersine döndürülür
    • Kalan hedef 0.7 - 0.7853 = -0.0853 olur
    • Değer negatif olduğu için sonraki adımda 0.3926 radyan, yani 22.5˚, saat yönünde döndürülür
    • Sonrasında kalan hedefin işaretine göre 0.1963 radyan gibi daha küçük açılarla yön değiştirilerek döndürme sürer
  • 16 yineleme sonunda vektör neredeyse tam hedef açıya hizalanır; y, sin(a) için, x ise cos(a) için bir yaklaşım olur

Dönüş matrisindeki pahalı işlemleri azaltmak

  • Normal bir vektör dönüşü, sinüs ve kosinüs içeren matris çarpımını kullanır
  • CORDIC, trigonometrik özdeşliklerden yararlanarak dönüş matrisini tan(a) merkezli hale getirir
  • Başlangıçta 45˚, 22.5˚, 11.25˚ gibi sabit dönüş açıları kullanıldığı için tan(a) değerleri önceden hesaplanmış bir tabloda tutulabilir
  • Bu tablo yalnızca 16 adet uint32_t gerektirir; yani 64 bayttır
    • Karşılaştırma için, -1 ile 1 arasındaki 4096 değeri tutan optimize edilmemiş bir sin(x) tablosu 16KiB gerektirir ve hassasiyeti de daha düşüktür
  • Her dönüşte önde gelen cos(a) terimi her yinelemede oluşur, ancak hepsinin çarpımı bir sabite yakınsar
    • 45˚, 22.5˚, 11.25˚ gibi açılar kullanıldığında bu çarpım yaklaşık 0.6366 olur
    • Bu sabiti tüm yinelemelerden sonra bir kez çarpmak yeterlidir

Yalnızca kaydırma ve toplama bırakacak açı seçimi

  • Çarpmayı ortadan kaldırmak için tan(a) sonucunun her zaman 2'nin negatif kuvveti olması sağlanacak açılar seçilir
  • Bunun için her yineleme i=0 ile 15 arasında atan(2**-i) değerlerini içeren 16 girişli bir tablo oluşturulur
  • Gerçek dönüş açıları 45˚, 26.565˚, 14.036˚, 7.125˚ gibi olur
  • Açılar tam olarak yarıya inmese de bu açıları kullanmak süreç için doğru sonuca yakınsamayı sağlar
  • tan(a) ile çarpma işlemi, yineleme numarası i kadar bit kaydırmaya dönüşür
  • cos(a) terimlerinin çarpımı da bu yeni açı seçimine göre yeniden hesaplanır
    • Değer yaklaşık 0.60725'tir
    • 16 bit sabit noktada bu 39796 değerine karşılık gelir
    • Sonda çarpmak yerine başlangıç vektöründeki x değerini 1 değil 39796 yapmak yeterlidir

Algoritma adımları

  • Ön hesaplama aşamasında, her girdisi atan(2**-i) olan bir tablo oluşturulur ve her değer sabit nokta biçimine çevrilir
    • Dönüşüm formülü atan(2**-i) * (1 << 16) şeklindedir
  • sin veya cos hesaplanırken giriş açısı da sabit nokta biçimine dönüştürülür
    • Örnekte 0.9152, 0.9152 * (1 << 16) = 59978 olur
  • Başlangıç durumu şöyledir
x = 39796
y = 0
z = 59978
  • z, vektörün bir parçası değil, kalan hedef açıyı izleyen değerdir
  • z işaretine göre dönüş yönü belirlenir
    • z >= 0 ise saat yönünün tersine döndürülür ve z -= table[i] uygulanır
    • z < 0 ise saat yönünde döndürülür ve z += table[i] uygulanır
  • Her yineleme x ve y üzerinde yalnızca toplama, çıkarma ve >> i kaydırması kullanır
if z >= 0:
    x_next = x - (y >> i)
    y_next = y + (x >> i)
    z -= table[i]
else:
    x_next = x + (y >> i)
    y_next = y - (x >> i)
    z += table[i]
x = x_next
y = y_next

Örnek yakınsama sonuçları ve kalan konular

  • 0.9152 radyan örneğinde ilk yinelemede z pozitif olduğu için yaklaşık 0.785 radyan kadar saat yönünün tersine döndürülür
  • İkinci yinelemede de z pozitif kaldığından yaklaşık 0.436 radyan saat yönünün tersine döndürülür, ancak hedef aşılır
  • Üçüncü yinelemede z negatif olur ve yaklaşık 0.244 radyan saat yönünde döndürülür
  • Dördüncü yinelemede de z negatif kaldığı için yaklaşık 0.124 radyan saat yönünde döndürülür
  • Açı değişimleri küçüldükçe vektör gerçek sonucun çevresinde ileri geri hareket ederek yakınsar
  • 16 yineleme sonunda y, sin(0.9152) için son derece yakın bir yaklaşım verir
    • Sinüs için mutlak hata 0.00000956'dır
    • x için kosinüs mutlak hatası 0.0000434'tür
  • Ele alınmayan konular da vardır
    • İlgilenilen açı, birim çemberin 1. veya 4. çeyreği dışında olduğunda gereken özel işlemler
    • CORDIC türevleriyle hesaplanabilen tan, atan, asin, acos, sinh, cosh, tanh, sqrt, ln, e^x
    • Logaritma ve üstel hesaplama için tasarlanmış ilişkili algoritma BKM
  • İlgili konuların Low Byte Productions YouTube channel üzerinde daha ayrıntılı ele alınması planlanıyor

İlgili okumalar

1 yorum

 
GN⁺ 2024-05-12
Hacker News yorumları

  • Yazar bunun çoğunlukla FPGA gibi yerlerde uygulandığını söylemiş olsa da oyun geliştirmede ya da dağıtık fizik simülasyonlarında da kullanılabilir.
    Kayan nokta hesaplamalarda platformlar arası determinizm sağlamak zordur; çözümlerden biri kayan noktadan tamamen kaçınıp sabit noktalı bir fizik motoru uygulamaktır.
    Trigonometrik fonksiyonları uygulamak için CORDIC gibi bir şey gerekir.
    Birkaç yıl önce eğlence olsun diye böyle bir şey yapmaya başlamıştım ama bitiremedim; bir gün tekrar denemek isterim.
    https://randomascii.wordpress.com/2013/07/16/floating-point-...

    • O yazı artık 10 yıllık ama önemli bir alıntı içeriyor: “IEEE standardı bazı şeyleri garanti eder. Kayan nokta matematiğini mistisizm gibi gören insanların bildiğinden fazlasını, ama bazı programcıların sandığından daha azını garanti eder.”
      Özetle x87'nin tuhaf yanları vardı; yuvarlama modu ve sıfıra flush etme gibi ayarların tutarlı biçimde eşlenmesi gerekir; eski işlemcilerde FMA yoktur; mmsqrtps gibi yaklaşık komutların tutarlı bir belirtimi yoktur ve derleyici ifadeleri yeniden ilişkilendirebilir.
      Küçük rutinler ya da kendi yazdığınız bir kütüphane söz konusuysa, zahmetli olsa da bunlardan kaçınıldığını garanti etmek mümkündür.
      IEEE-754 2008 belirtimi daha net hâle getirdi ve fiilen x87'nin ölümünü varsaydı; 2024'te x87'den kesin biçimde kaçınmak mümkün.
      FMA da IEEE-754 2008 belirtiminin bir parçasıdır ve Intel Haswell sonrası dâhil modern işlemcilerde bulunur.
      Yine de 8-wide AVX2 ile 4-wide NEON gibi mimari farklar sorun çıkarabilir; ancak assembly ya da intrinsic'ler kullanarak, ya da Compiler Explorer veya objdump ile denetlenen C yazarak çıktıya bakıp “bu tutarlı olur” diye karar verebilirsiniz.
    • Yazar da kayan noktanın donanım performansındaki artışla yaygınlaşmasından önce sabit noktanın oyun geliştirmede çok yaygın olduğunu ve CORDIC'in de muhtemelen birlikte kullanıldığını söylüyordu.
      “Aslında IEEE 754 bugünkü kadar popüler bir standart hâline gelmeden önce sabit nokta her zaman kullanılıyordu. 1980 ile yaklaşık 2000 arasında çalışmış bir oyun geliştiricisine sorarsanız ayrıntıları anlatacaktır.”
    • Oyun geliştirmeye yönelik fizik simülasyonu kütüphanesi nphysics, platformlar arası determinizm gerektiğinde CORDIC ile birlikte sabit noktalı matematik kullanma yolunu seçmişti; ancak artık kullanımdan kaldırıldı.
      nphysics'in yeniden yazılmış hâli olan yeni kütüphane Rapier ise bunun yerine IEEE-754 2008'in garantilerine dayanarak platformlar arası determinizm sağlıyor.
      Bu yüzden eski platformlarda çalışmıyor, ancak wasm dâhil modern platformlarda deterministik.
      Elbette her platformun sunduğu sin, cos gibi transandantal fonksiyon rutinlerine güvenemezsiniz; her yerde aynı şekilde çalışacak biçimde kendiniz uygulamanız gerekir.
      Ancak uyumsuz platformlarda çalıştırmazsanız uygulanabilir bir yaklaşım.
      https://www.rustsim.org/blog/2020/06/01/this-month-in-rustsi...
      https://rapier.rs/docs/user_guides/rust/determinism/

  • CORDIC, sinüs ve kosinüs hesaplama/üretmenin yanı sıra logaritma, üstel fonksiyon, karekök, vektör büyüklüğü, kutupsal-koordinat ile Kartezyen-koordinat dönüşümü, vektör döndürme gibi çeşitli işlemler için de kullanılabilir.
    Yazar da sonuç bölümünde bu olasılığa işaret ediyor.
    Mevcut ortonormal matrisler yerine kuaterniyon kullanılırsa CORDIC tabanlı işlemlerin daha verimli, yani daha az hesaplama döngüsü ve bellek kullanarak ve daha düşük hatayla yürütülebileceği hissine kapılıyorum.
    https://core.ac.uk/works/8439118

    • Yanlış hatırlamıyorsam keyfi Lie gruplarına da genişletilebiliyor.

  • Lisede analiz öncesi dersinde Taylor serilerini öğrenmiştim ve öğretmenim hesap makinelerindeki trigonometrik fonksiyonların gerçekten böyle uygulandığını söylemişti.
    Araştırınca aslında CORDIC olduğunu gördüm ve TI Basic'te uygulayarak epey eğlendim.

    • Şaşırtıcı Sinclair scientific hesap makinesinin trigonometrik fonksiyonları, logaritmaları vb. nasıl hesapladığını okumak ilginç olabilir.
      CORDIC değildi ama algoritmasında benzer yanlar var.
      http://files.righto.com/calculator/sinclair_scientific_simul...
    • Taylor açılımı kullanan gerçekten tek bir hesap makinesi bile var mı?

  • Donanım uygulamalarıyla ilgili yazılar:
    https://arxiv.org/pdf/2211.04053
    https://hal.science/hal-01327460/document
    https://archive.ll.mit.edu/HPEC/agendas/proc05/Day_1/Abstrac...
    Farklı dönemlerdeki çeşitli donanımlarda, genel yazılım/donanım trigonometrik fonksiyon uygulamalarıyla nasıl karşılaştırıldığını görmek isterim

  • sin ve cos vektör döndürmede sık kullanılır
    Bu durumda CORDIC’in püf noktası, geleneksel sin/cos/çarpma hesabından kaçınmak ve döndürülecek vektörün kendisini CORDIC’in girdisi olarak vermektir
    Böylece CORDIC, sin/cos hesaplamadan ya da karmaşık sayı çarpımı yapmadan döndürülmüş vektörü doğrudan üretir
    CORDIC, gecikme süresinin çok kritik olmadığı durumlarda özellikle parlar
    Hesabın her adımı pipeline’a alınırsa ciddi bir throughput elde edilebilir; bu da kablosuz sistemlerde dijital mixing için uygundur

  • 2023 itibarıyla bazı modern MCU’lar düşük maliyetli olmasına rağmen FPU’ya sahip
    STM32G4 iyi bir örnek; M0 MCU gibi durumlardan farklı olarak sabit nokta kullanmak istemiyorsanız f32’yi serbestçe kullanabilirsiniz
    Bu tür çipler MCU başına yaklaşık 1–2 dolara bulunabiliyor
    Ancak G4’te sabit nokta amaçları için bu algoritmayı uygulayan bir donanımsal CORDIC çevre birimi de var
    Bunun esas olarak kayan nokta hassasiyet kaybından kaçınmak için mi kullanıldığını merak ediyorum
    Register’lar üzerinden programlanıyor ama CORDIC’i doğrudan CPU üzerinde uygulamıyor; IC içindeki özel donanım işliyor

  • Daha önce katkıda bulunduğum epey sevimli bir kod parçası aklıma geliyor
    Birim çemberdeki bir yayın oluşturduğu açının açıortay koordinatlarını bulmak gerekiyordu ve iki kolun (x,y) koordinatları zaten vardı
    Mevcut uygulama, (x,y) koordinatlarını kutupsal koordinatlara (r,θ) çeviren, hesaplanan θ’nın doğru çeyrekte olup olmadığını kontrol eden, sonra θ’yı ikiye bölüp yeniden (x,y)’ye dönüştüren bir trigonometrik fonksiyon yığınıydı
    Sonuçta çok sayıda trigonometrik ve ters fonksiyon çağrısı yapıyordu
    Python’da karmaşık sayılar birinci sınıf değerler olarak kullanılabildiği için, (x1,y1)’den z1, (x2,y2)’den z2 adlı iki karmaşık sayı tanımlayıp çarpımın geometrik ortalamasını √(z1*z2) almak yeterliydi
    Yeni kodda ne açık bir trigonometrik fonksiyon vardı ne de açık dönüştürme ve ters dönüştürme

  • “22,75˚ döndürmek, 45˚ döndürüp ardından -22,5˚ döndürmekle aynıdır; bu oldukça açık” denmiş, ama bu durumda 22,5° döndürme olmuyor mu?
    Yazıdaki bir hata mı, yoksa ben mi yanlış anladım, merak ediyorum

    • Yazıdaki hata

  • Meagher’ın octree sistemi, tamsayı çarpma ve bölme olmadan yalnızca tamsayı aritmetiği kullanmasıyla bilinir.
    “Boolean işlemleri (birleşim, kesişim, fark), geometrik işlemler (taşıma, ölçekleme, döndürme), N boyutlu çakışma tespiti ve uzayın rastgele bir noktasında gizli yüzey kaldırmayı içeren gösterim için verimli doğrusal zamanlı algoritmalar geliştirilmiştir. Bu algoritmalar kayan nokta işlemleri, tamsayı çarpma ve tamsayı bölme gerektirmez.”
    https://doi.org/10.1016/0146-664X(82)90104-6
    Bu sayede octree gösterimi için hızlı, özel amaçlı VLSI grafik hızlandırma donanımı yapmak kolaylaştı.

  • CORDIC’in küçük tablolar kullanan 3. derece interpolasyon ya da diğer polinom interpolasyonlarıyla karşılaştırıldığında nasıl bir performans verdiğini merak ediyorum.
    Kaynakları sınırlı synthesizer’ların zaman zaman 3. derece interpolasyon kullandığını öğrenmiştim; muhtemelen CORDIC’in nispeten yeni olduğu bir dönemdi.
    Kabaca bakınca CORDIC her yinelemede 1 bit hassasiyet kazandığı için hesaplama açısından daha pahalı, ama alan açısından polinomlardan daha az yer kullanacak gibi görünüyor.
    Yine de alan açısından, yazıda sin(x) için sunulan 4096 girişli arama tablosundan daha ucuza gelebileceğini vurgulamak gerekir.
    Simetri sayesinde tam çemberin yalnızca 1/4’ü gerekir.

    • Eski oyun geliştiricileri ve demoscene geliştiricileri sin ve cos için yalnızca 256 girişli arama tablosu kullanırdı.
      Bayt boyutunda açılar kullanınca otomatik olarak döngüsel olması kullanışlıydı ve 2D oyunlarda döndürme için 2^8 oldukça yeterliydi.
      Ancak akıcı hareket istiyorsanız 3D’de bununla çok fazla ilerleyemezsiniz.