Intel 8087'nin tanjant sırrı: yarısı CORDIC, yarısı polinom

Bu ayrıntı, 46 yıllık bir çipin meraklısını aşan bir sorunun cevabı: hızlı çarpma devresi olmayan bir donanım, sinüs ve tanjant gibi fonksiyonları nasıl hesaplar? Cevap hâlâ kullanılıyor; bugün de saat sayısı kısıtlı gömülü sistemlerde ve programlanabilir devrelerde aynı numara iş görüyor.

CORDIC nereden çıktı: uçakta yer bulan bir hesap yöntemi

CORDIC, "COordinate Rotation DIgital Computer" sözcüklerinin kısaltması. Shirriff'in anlattığına göre yöntemi 1950'lerde mühendis Jack Volder geliştirdi; görevi, Convair'in B-58 Hustler adlı uçağının navigasyon bilgisayarındaki analog hesaplama düzeneğinin yerine dijital bir çözüm koymaktı. B-58, Shirriff'in notuna göre Mach 2 hızına çıkabilen kendi sınıfının ilk uçağıydı ve konumunu sürekli hesaplaması gerekiyordu.

Volder'ın bulduğu yolun püf noktası şu: çarpma ve bölme yapmadan trigonometri. CORDIC yalnız toplama, çıkarma, bit kaydırma (bir sayıyı ikiye bölmek ya da ikiyle çarpmak demek) ve küçük bir tablo okuması kullanıyor. Yöntem sonradan bilimsel hesap makinelerine de girdi; Shirriff'in belirttiğine göre oralarda ikilik değil ondalık sürümü tercih edildi.

Kaydır ve topla: yöntemin mantığı

CORDIC'i anlamanın en kolay yolu eski bir terazi düşünmek. Elinizde standart ağırlıklar var; tartacağınız şeyi, o ağırlıkların bir alt kümesini kefeye koyarak dengelemeye çalışırsınız. Her ağırlık için kararınız iki seçenekli: koydum ya da koymadım.

CORDIC'in "standart ağırlıkları" açılardır: arctan(1), arctan(1/2), arctan(1/4), arctan(1/8)... yani arctan(2⁻ⁿ) dizisi. Hesaplanacak açı, bu özel açıların toplamı olarak parçalanır. Her adımda kalan açı bir sonraki özel açıdan büyükse o açı çıkarılır ve karar olarak 1 yazılır, değilse 0 yazılır. Bu özel açıların her biri çipin içine sabit olarak kazınmıştır; işlem sırasında hesaplanmaz, okunur.

Sonra dönüş aşaması gelir: kararlar boyunca bir koordinat çifti, yalnız kaydırma ve toplamayla adım adım döndürülür. Shirriff'in vurguladığı gibi her CORDIC adımı sonuca bir bit daha doğruluk ekler, bu yüzden yöntem hızlı yakınsar. On altı adım, kabaca on altı bit demek.

"Melez" ne demek: CORDIC'in bıraktığı yerden polinom

8087'nin tanjant için istediği doğruluk 64 bit. Bunu saf CORDIC ile elde etmek 64 adım gerektirir. Shirriff'in mikrokoddan okuduğu şey ise farklı: çip yalnız 16 CORDIC adımı çalıştırıyor, sonra duruyor. Geriye kalan, artık çok küçülmüş açı için formüle başvuruyor.

Kullanılan formül basit: 3x / (3 − x²). Bu, adını matematikçi Henri Padé'den alan "Padé yaklaşımı" ailesinden bir ifade; kısaca iki polinomun oranı biçiminde yazılan yaklaşık değer demek. Shirriff'in hesabına göre bu formülün hatası x'in dördüncü kuvvetiyle orantılı. Kalan açı 2⁻¹⁶'dan küçük olduğu için toplam hata 2⁻⁶⁴'ün altında kalıyor, yani istenen 64 bit tutuyor.

Melezliğin mantığı burada: CORDIC büyük payı ucuza alıyor, polinom ise küçük kalıntıyı tek hamlede bitiriyor. Shirriff'in ifadesiyle 8087, CORDIC ile bir rasyonel polinomu birleştirmesi bakımından alışılmadık bir tasarım.

Sözde-bölme, sözde-çarpma ve 16 bitlik not defteri

8087'yi tasarlayanlar bu iki aşamaya CORDIC demek yerine kendi adlarını koymuşlar: sözde-bölme (pseudo-division) ve sözde-çarpma (pseudo-multiplication). İlki yukarıdaki karar aşaması, ikincisi dönüş aşaması.

Shirriff'in kalıp fotoğrafında bulduğu ayrıntı hoş: 16 karar biti, çipin sağ kenarındaki 16 bitlik bir kaydırma yazmacına yazılıyor. İkinci aşamada bu bitler ters sırada geri okunuyor, yani dönüşler önce en küçüğünden başlayarak uygulanıyor. Sebebi hız değil, doğruluk — küçük katkılar önce toplanınca yuvarlama hatası azalıyor.

Bir tuhaflık daha var. FPTAN komutu tanjantı doğrudan vermiyor; "kısmi tanjant" adı altında X ve Y olmak üzere iki koordinat değeri döndürüyor, bölme işini programa bırakıyor. Shirriff'in 0,95 radyanlık örneğinde çip X ≈ 2,4884 ve Y ≈ 3,4797 üretiyor; bölünce tan(0,95) ≈ 1,398 çıkıyor. Belgelerde komutun geçerli aralığı 0 < θ < π/4 olarak yazılmış, ama Shirriff mikrokodun bu aralığın dışını da işlediğini, sınırın mikrokodu basitleştirmek için konmuş bir tercih olduğunu söylüyor.

Çipin içine kazınmış 42 sabit

CORDIC'in tablosu çipin içinde bir "sabit ROM"unda duruyor. Shirriff bu ROM'u 2020'de ayrı bir çalışmada okumuştu: 134 satır, 21 sütun ve toplam 42 sabit. İlk 12'si genel amaçlı sabitler (1, π, ln2, √2, log değerleri gibi) ve 64 bit uzunluğunda. Geri kalanlar 67 bit, yani üç bit fazla — Shirriff'in yorumuna göre CORDIC sabitleri, ara adımlarda biriken hatayı tolere edebilmek için bu ek basamaklara ihtiyaç duyuyor; genel sabitler duymuyor.

CORDIC'e ayrılan sabitler iki küme: 16 tane arctan(2⁻ⁿ) değeri ve 14 tane log₂(1+2⁻ⁿ) değeri. İkinci küme logaritma ve üs komutları için; aynı mantık tanjanttan başka fonksiyonlarda da yeniden kullanılıyor.

8087'nin künyesi

Aşağıdaki tabloda mikrokod, sabit ROM ve zamanlama satırları Shirriff'in çalışmalarından; üretim süreci, transistör sayısı ve fiyat satırları çipin İngilizce Vikipedi künyesinden alındı. İkinci grubun birincil kaynağını doğrulayamadım, oradaki rakamları temkinli okuyun.

Zaman nereye gidiyor

Shirriff, 0,95 radyanlık örnek için çevrimlerin nereye harcandığını da çıkarmış: yüzde 33 sözde-bölme, yüzde 47 sözde-çarpma, yüzde 15 rasyonel polinom, yüzde 5 kadarı da diğer işler. Yani "melez"in polinom yarısı, sürenin altıda birinden azını yiyor.

O yüzde 15'in büyük kısmı tek bir işlem: 64 bitlik bir sayının karesinin alınması. Shirriff'in aktardığına göre 8087 bunun için Booth algoritmasının iki biti birden işleyen (radix-4) sürümünü kullanıyor; böylece sıradan ikilik çarpmanın iki katı hızda çalışıyor ve döngü donanımda gerçekleşiyor.

Bugünün işlemcilerinde bu iş nasıl yapılıyor

Shirriff'in verdiği cevap net: Pentium'la birlikte Intel CORDIC'i bırakıp polinom yaklaşımlarına geçti, çünkü Pentium'un hızlı çarpma devresi polinomları uygulanabilir kıldı. Bugün trigonometri çoğunlukla özel donanımda değil, MKL ve SVML gibi matematik kütüphanelerinde çözülüyor; bu kütüphaneler polinom yaklaşımlarını SIMD komutlarıyla, yani aynı anda birden çok sayı üzerinde çalıştırıyor. Shirriff'in ifadesiyle x87 komutları ve 80 bitlik ondalıklı sayı biçimi artık büyük ölçüde geride kalmış durumda.

CORDIC'in kendisi ise emekli olmadı. Çarpma devresinin pahalı olduğu her yerde — programlanabilir devreler, küçük gömülü denetleyiciler, hesap makineleri — bir açıyı standart açıların toplamına parçalayıp kaydırmayla dönmek hâlâ en ucuz yol.

Bulgunun sınırı ve açık kalan kısım

Bu okumanın nasıl yapıldığını hatırlamakta fayda var: mikrokod, kalıp fotoğrafındaki ROM hücrelerinin makine öğrenmesiyle sınıflandırılmasıyla çıkarıldı. Shirriff, ROM görüntülerini mikrokod verisine çeviren ve içeriği ayrıntılı inceleyen kişiler olarak "Smartest Blob" ve "Gloriouscow" takma adlı iki araştırmacıyı anıyor. Yöntem tek bir çip örneğine dayanıyor ve doğrulaması, çıkarılan mikrokodun gerçek çipin davranışıyla tutarlı olmasından geçiyor; bu bir belge değil, yeniden inşa.

Shirriff yazının sonunda 8087 mikrokodunu çözmeye devam edeceğini söylüyor. Tanjant çözüldü, ama aynı sabit ROM'u paylaşan logaritma, üs ve arktanjant komutlarının kaç adım CORDIC, kaç adım polinom kullandığı henüz aynı ayrıntıda yayımlanmadı. 46 yıllık bir çipin sırları, bir tane açı fonksiyonuyla bitmiyor.

Fotoğraf: Pauli Rautakorpi, CC BY 3.0, Wikimedia Commons