Pentium’da 3 ile çarpmak için karmaşık bir özel devre vardı

 (righto.com)
3 puan yazan GN⁺ 2025-03-04 | 1 yorum | WhatsApp'ta paylaş
  • 1993 tarihli Intel Pentium, kayan nokta çarpma işlemini hızlı yapmak için 3 kat değer üreten özel bir ×3 devresi içeriyordu; yalnızca bu küçük devre bile binlerce transistör kullanıyordu
  • Pentium, 64 bit çarpmada toplanacak terim sayısını 64’ten 22’ye düşürmek için radix-8 çarpma kullanır; ancak bu yöntemde ×3 katının hızlı üretilmesi gerekir
  • ×3 hesabının kendisi x + 2x toplamasıdır, fakat çarpma işleminin geri kalan aşamaları bu sonucu beklediği için carry lookahead ve Kogge-Stone gibi hızlı toplayıcı teknikleri gerekir
  • Devre, sekiz adet 8 bit blok ile üst seviye lookahead’i birleştiren hiyerarşik bir yapıya sahiptir; taşma ve yuvarlama için gerçek çıkış 69 bit genişliğine çıkar
  • Tek bir ×3 devresinde yaklaşık 9000 transistör kullanılması, Pentium neslinde performans için ne kadar karmaşık donanım optimizasyonları yapıldığını gösterir

Pentium’un ayrı bir ×3 devresi bulundurmasının nedeni

  • Pentium’un kayan nokta çarpıcısı, iki 64 bit sayıyı radix-8 yöntemiyle çarpar
    • Sıradan ikili çarpma, her bit için 0 veya çarpılan sayıyı eklediğinden 64 bit çarpmada 64 terim gerekir
    • Radix-8 yöntemi, çarpanı 3 bitlik gruplara ayırıp 0~7 arasından bir değerle çarptığı için toplanacak terim sayısı 22’ye düşer
  • 0~7 katlarından bazıları donanımda görece basit üretilebilir
    • ×2, 1 bit sola kaydırma ile işlenir
    • ×4, 2 bit sola kaydırma ile işlenir
    • ×6 ve ×7, Booth çarpma algoritması ile bir sonraki radix-8 basamağının +1’i ve mevcut basamağın çıkarma işlemi birleştirilerek işlenebilir
    • ×5, ×8’den ×3 çıkarılarak elde edilebilir
  • Sonuçta zorlayıcı kat ×3’tür ve Pentium bunu kayan nokta çarpıcısının içindeki özel bir devreyle çözer

Basit toplamanın darboğaz olduğu nokta

  • 3 kat değer, giriş değerinin kendisi ile bir bit sola kaydırılmış halinin toplanmasıyla üretilebilir
    • Yapı olarak bakıldığında bu x + 2x toplamasıdır
  • Darboğaz, toplama sürecindeki carry yayılımında ortaya çıkar
    • Ripple-carry adder’da alt bitlerde oluşan carry’nin üst bitlere sırasıyla iletilmesi gerekir
    • ×3 sonucu hazır olmadan çarpma işleminin geri kalanı başlayamayacağı için gecikmenin azaltılması gerekir
  • Pentium, carry’yi sıralı olarak yaymak yerine paralel hesaplamak için carry-lookahead adder kullanır
    • Her bitte carry generate ve carry propagate sinyalleri üretilir
    • Generate, ilgili konumun carry oluşturduğu durumu ifade eder
    • Propagate, gelen carry’nin dışarı aktarıldığı durumu ifade eder
    • Carry paralel hesaplandığında sum bitleri de paralel hesaplanabilir

Kogge-Stone ve 2 aşamalı carry lookahead

  • Carry lookahead basitçe doğrudan uygulanırsa bit sayısı büyüdükçe devre ve kablolama yükü artar
    • Bit konumu yükseldikçe mantık karmaşıklaşır
    • Çok girişli kapılar elektriksel nedenlerle yavaşlar
  • Pentium, 8 bitlik birimler halinde Kogge-Stone paralel prefix toplayıcı kullanır
    • Kogge-Stone, propagate/generate sinyallerini aralıklar halinde birleştirerek carry’yi paralel hesaplar
    • Ara sonuçları yeniden kullanarak gecikmeyi ve devre miktarını yönetir
  • 64 bitin tamamını tek bir Kogge-Stone ile işlemek yerine 2 aşamalı hiyerarşik yapıya böler
    • Alt katman, her bloğun iç carry’sini hesaplamak için sekiz adet 8 bit Kogge-Stone devresi kullanır
    • Üst katman, her 8 bit bloğu tek bir birim gibi görüp bloklar arası carry’yi hesaplar
    • İki katman birleştirilerek 64 bit toplam için gereken carry hızla sağlanır
  • Devre 64 bitlik gibi görülebilir, ancak gerçekte taşmayı önleme ve yuvarlama için ek bitler de dahil edilerek 69 bit çıkış üretir

Carry-select ile bekleme süresini azaltma

  • Her 8 bit blokta bir carry-select adder bulunur
    • Carry-in’in 0 olduğu ve 1 olduğu durumların toplamı önceden ayrı ayrı hesaplanır
    • Üst seviye lookahead devresi gerçek carry-in’i bildirdiğinde multiplexer doğru sonucu seçer
  • Bu yöntem daha fazla donanım kullanma pahasına zamandan tasarruf eder
    • İki adder ve sonuç seçimi için bir multiplexer gerekir
    • Toplam hesaplaması ile carry hesaplaması örtüştürülerek toplam gecikme azaltılır
  • En düşük 8 bit blokta carry-in olmadığından carry-select devresine gerek yoktur
    • Bu bloğun çıkış bitleri XNOR kapısı ile hesaplanır

8 bit bloğun içinde olanlar

  • ×3 devresinin her 8 bit bloğu, giriş hatlarını soldaki adder’a ve sağdaki yola ayırır
    • Bu dallanma yapısı, giriş değeri ile bir bit sola kaydırılmış giriş değerini toplayarak ×3’ü gerçekleştirir
  • Bloğun üst kısmı, propagate/generate sinyallerini üreten devrelerden oluşur
    • Bu sinyaller 8 bit Kogge-Stone lookahead devresine girer
    • Kogge-Stone bölümü, her bit konumunda farklı karmaşıklığa sahip olduğundan tekrarlayan bloklar gibi değil, düzensiz görünür
  • Bloğun alt kısmı carry-select adder alanıdır
    • İki toplam önceden hesaplanır ve carry-in’e göre multiplexer seçim yapar
    • Carry-select adder bloğu, üst Kogge-Stone devresinin bir kısmına yer açmak için çevredeki devrelerden daha dar yerleştirilmiştir
  • Her blok, çıkış bitlerini bir sonraki çarpıcı devresine göndermeden önce sürücü devre ile güçlendirir

XNOR kapısı ve transistör düzeyinde uygulama

  • Düşük bit bölgesindeki XNOR kapısı Pentium’da multiplexer olarak uygulanmıştır
    • Intel 386, XOR’u AND-NOR kapılarıyla uygulamıştı; Z-80 ise pass transistor kullanmıştı, ancak Pentium’un yaklaşımı farklıdır
  • Söz konusu XNOR devresi dört inverter ve pass transistor multiplexer’dan oluşur
    • B girişi, multiplexer’ın iki girişinden A girişini veya A’nın terslenmiş halini seçer
    • Bunun sonucunda XNOR fonksiyonu oluşur
  • Çip fotoğrafı analizinde, alt metal katman M1’i ve katkılanmış silikon bölgeleri gözlemlemek için üstteki iki metal katman kaldırılır
    • Polisilikon hattın katkılanmış silikonu kestiği nokta transistör kapısı olur
    • CMOS devresi üstte NMOS ve altta PMOS transistörlerden oluşur

BiCMOS çıkış sürücüsü

  • ×3 devresinin çıkışı yüksek akım gerektirir
    • Her ×3 sinyali, kayan nokta çarpıcısı içinde en fazla 22 terimi sürebilir
    • Hedef devre ×3 devresinden uzakta bulunabilir
    • Uzun kablolar ve çok sayıda transistör kapısı nedeniyle kapasitans artar; sinyali hızlı değiştirmek için yüksek akım gerekir
  • Pentium, aynı çipte bipolar transistor ve CMOS’u birleştiren BiCMOS sürecini kullanır
    • Pentium, sinyal gecikmesini en fazla %35 azaltmak için BiCMOS devrelerini yaygın biçimde kullanmıştır
    • Intel, Pentium Pro, Pentium II, Pentium III ve Xeon’da da BiCMOS kullanmıştır
    • Çip voltajı düştükçe bipolar transistorun avantajları azaldı ve BiCMOS sonunda kullanılmaz hale geldi
  • ×3 devresinin sürücüsü, bir BiCMOS sürücünün ikinci bir BiCMOS sürücüyü sürdüğü bir yapıdır
    • Yüksek akımlı inverter’ın transistör kapısı büyük olduğundan onu sürmek için ara bir aşama gerekir
    • Küçük sinyali birkaç aşamada büyütmek toplam gecikmeyi azaltabilir
  • BiCMOS sürücüsünün NPN transistörü, normal MOS transistörlerden farklı olarak büyük bir kutu şeklinde görünür
    • Inverter, çıkışı yükseltmek için PMOS ve çıkışı düşürmek için NMOS kullanan standart CMOS yapısını kullanır
    • Bazı inverter’lar güçlü high veya güçlü low çıkışı verecek şekilde asimetrik akım özellikleriyle tasarlanmıştır

Çarpma donanımının gösterdiği karmaşıklık artışı

  • Bilgisayar çarpma donanımının tarihi 1950’lere kadar uzanır
    • Booth çarpma tekniği 1951’de açıklanmıştır
    • Paralel çarpıcılar 1960’ların ortasında Wallace ve Dadda tarafından önerilmiştir
  • İlk mikroişlemcilerde donanımsal çarpma desteği sınırlıydı
    • 6502 gibi işlemcilerde çarpma donanımı olmadığından kullanıcıların shift ve toplama ile yazılımsal uygulama yapması gerekiyordu
    • Intel 8086, mikro kodla yavaş bir shift-and-add döngüsü gerçekleştiriyordu
    • 386 bir multiply unit içeriyordu, ancak çarpma komutu en fazla 41 clock cycle sürüyordu
  • Pentium dönemine gelindiğinde milyonlarca transistör sığdırılabildiği için daha karmaşık performans optimizasyonları mümkün hale geldi
    • Pentium’un kayan nokta çarpması 3 clock cycle sürer ve çarpma devresi bunun 2 cycle’ı boyunca kullanılır
    • Tamsayı çarpması MUL ise 11 cycle ile çok daha yavaştır
    • 2008’deki Nehalem mikro mimarisi, kayan nokta çarpma süresini 1 cycle’a indirmiştir
  • Pentium’un ×3 çarpıcısı yaklaşık 9000 transistör içerir
    • Bu, 1976 tarihli Z80 mikroişlemcisinin tamamından biraz daha fazladır
    • ×3 devresi, Pentium’un kayan nokta birimi içindeki kayan nokta çarpıcısının yalnızca küçük bir parçasıdır

İlgili okumalar

1 yorum

 
GN⁺ 2025-03-04
Hacker News yorumları

  • Çok yan bir konu ama uzun zaman önce üçlü bilgisayar emülasyonu üzerinde çalışırken, 3'ün kuvvetlerine bölme işlemini bit kaydırma ve toplamalardan oluşan bir seriye dönüştüren kapalı biçimli bir dönüşüm bulmak için sevimli bir numara kullanmıştım
    Önce 1/3 - 1/2 = 2/6 - 3/6, yani 1/3 = 1/2 - 1/2 (1/3) olduğunu görmek yeterli
    Bu ifadeyi sağ tarafa sonsuz kez yerine koyunca 1/3 = -(-1/2)^N biçimi ortaya çıkıyor; N ise 1..inf aralığında
    Sadece 2 ve 3'ün kuvvet çiftleri için değil, başka tabanlarda da benzer şeyler yapılabiliyor
    Anlamı şu: 2'nin kuvvetlerine yakın değerler için, yalnızca toplayıcı ve çıkarıcılarla sabit zamanda çalışan sabit bölenli bölme devreleri yapmak oldukça kolay

    • Şaşırtıcı. Üçlü bilgisayarın üç durumlu mantığa dayandığını varsayıyorum; bunun ikili durumları kodlayan transistörlerden, hatta vakum tüplerinden bile daha az güvenilir olduğunu anlamak doğru mu diye merak ediyorum

  • Cinematronics arcade oyun işlemcisinde iki adet 12 bitlik akümülatör var
    Çarpma komutu bu ikisini tek bir 24 bitlik değer gibi sağa kaydırıyor ve en düşük anlamlı bitten 1 gelirse bellek içeriğini ekliyor
    Bu yüzden üst yarıyı temizleyip alt yarıya bir değer yüklüyor, diğer operandın bellek adresini nasıl ayarladıklarını unuttum ama 1 bitlik çarpmayı art arda birkaç kez çalıştırıyorlardı
    Böylece 24 bitlik çarpım elde edilebiliyor; fakat gördüğüm kodların çoğu 8 çarpma işlemini peş peşe kullanıyordu ve en yaygın kullanım oyun nesnesi koordinatlarını döndürmek için 2x2 matris çarpımıydı
    1970'lerin ortasında hazır 7400 serisi parçalarla yapılmıştı ve en yüksek verimi 5 MIPS idi

    • Tek bir çarpmanın tam olarak bir çevrim olduğunu sanmıyorum. Öyleyse 5 MIPS de hızla tükenirdi
      Son 20 yılda birkaç kez sabit noktalı aritmetik yapmak zorunda kaldım; önceki nesil programcılara duyduğum saygı arttı

  • carry lookahead, Kogge-Stone addition gibi teknikleri duymuş olabilirsiniz denilen kısma ek olarak, buradaki Kogge Peter Kogge
    Doktora çalışmasını Stanford'da yaptı, uzay mekiğiyle ilgili işlerde çalıştı, IBM Fellow unvanına sahip ve ilk çok çekirdekli CPU'yu icat eden kişi

    • Onun birçok başarıya imza attığı kesin, ama ilk çok çekirdekli CPU'yu icat etti gibi bir ifadeyi çıkarsak da gerçek yeterince güçlü kalır; dünya da bence bu tür ifadeler olmadan daha iyi olurdu
      “Çok çekirdekli CPU”nun kendisi, kesin konuşmak gerekirse tek bir icattan çok bir fikir sayılır. Yarı iletken tarihinde belli bir noktaya gelindiğinde oldukça açık ve önemsiz bir fikir de
      Çok çekirdekli bir CPU'yu gerçekten çalışır hâle getirmek önemsiz değil; ama o da tekil bir icat değil ve o dönemde geliştirme ekipleri zaten öyle büyümüştü ki, bir kişinin tüm sorunları tek başına çözdüğünü söylemek neredeyse hakaret olur
      Kogge ilk çok çekirdekli CPU'nun geliştirilmesine liderlik etmiş olabilir, başkaları mümkün görmeden önce bunu zorlayan bir öncü de olabilir; ama iki durumda da bunu tek başına icat etmiş değil
    • İlk çok çekirdekli CPU ekibine Kunle Olukotun'un liderlik ettiğini biliyordum
    • Bir ek daha: Peter Kogge, erken dönem süperbilgisayar vektör işlemcilerinin nasıl tasarlandığını öğrenmek isteyenlerin okuyabileceği boru hatlı mikro mimari üzerine erken dönem ders kitaplarından birini yazdı: The Architecture of Pipelined Computers (1981)
    • Peter eskiden laboratuvarımızla danışmanlık ve iş birliği yapmıştı. Uzaktan algılama hesaplamasını sensörlere daha yakına taşıma yaklaşımını, bugünkü deyişle edge computingi destekliyordu
      Bu yaklaşım entelektüel olarak gayet ikna edilebilir. Veriyi merkezi hesaplamaya taşımada gecikme veya maliyet varsa makuldür; bizim durumumuzda da uzay tabanlı sensörler olduğu için bu mantık kurulabiliyordu
      Ancak bildiğim kadarıyla bu tür işleme uzay tabanlı işleme sistemlerinde sistematik olarak benimsenmiş değil; radar gibi birçok sistem sensöre yakın donanımda geçici veri azaltma yapıyor
      Bu bağlantıyı gösterdiğin için teşekkürler

  • Yazarıyım. Sorunuz varsa yanıtlarım

    • Sonraki makinelerde özel 3 ile çarpma birimine ne olduğunu merak ediyorum. Herhangi bir biçimde kalmaya devam etti mi, yoksa taktikler değişip gereksiz mi hâle geldi?
    • Ken, artık kitap çıkarma zamanı gelmedi mi?
    • Temel bir soru olabilir ama bu kayan noktalı çarpma için mi? Üslerin de toplanması gerektiğine göre fiilen çarpılan kısım 64 bitten küçük değil mi?
    • Anlayışım bulanık; çok aptalca bir soruysa görmezden gelebilirsiniz ama “×3 hesaplayabiliyorsanız ×8'den çıkarıp ×5 elde edebilirsiniz” ise neden x4ü x7den çıkarıp x3 elde etmek gibi bir şey yapılamıyor, merak ediyorum

  • Bir şeyi atlıyor gibiyim
    ×2, 6x = 8x - 2x kullanılabilecek kadar kolay hesaplanabiliyorsa ve ×4 de 4x = 4x olarak kolayca hesaplanabiliyorsa, 3x'i 2x + 1x toplamı ya da 4x - 1x farkı olarak hesaplamak neden bundan daha zor, anlamıyorum
    Ayrıca ×6 herhangi bir şekilde kolayca hesaplanabiliyorsa, o değeri sağa kaydırıp ×3 yapmak neden olmaz, bunu da merak ediyorum. Ek bir adım ama o ek adım yalnızca kaydırma

    • 64 bitlik çarpmada sekizlik tabandaki her basamak için bir tane olmak üzere toplam 22 terim toplanıyor. İlkokul usulü çarpmayı düşünün
      Her terimin hesaplanması önemsiz olmalı; bu yüzden terimi elde etmek için kaydırma veya işaret değiştirme yapılabilir ama başka bir toplama yapılamaz
      Kilit nokta şu: ×3 bir kez önceden hesaplanırsa, daha sonra gereken 22 terimden herhangi birine doğrudan konabilir
      Terimin içinde ×2 ve ×1 koyup ×3 oluşturamazsınız. Bunu yapmak her terim için bir başka toplayıcı gerektirir
      Başka bir deyişle istediğiniz şey ×3 hesaplayan tek bir devredir, 22 devre değil
      ×6 sorusuna gelince, bu değer terime negatif ×2 koyup kavramsal olarak bir sonraki basamağa 1 ekleyerek ×8 elde etme biçiminde hesaplanır. Bu ×8 değeri tamamen başka bir terimin parçası olduğundan sağa kaydırılamaz
      Sayılar ve toplamlar çok yer değiştirdiği için karmaşık, ama böyle bakınca mantıklı gelecektir

  • 3 ile çarpma aslında yaygın bir işlem; özellikle adres hesaplamada, index’i shift ve toplama ile 3 ile çarpmak sık görülür.
    Safça uygulanırsa gecikme epey artar. Ama bu devre kullanılırsa LEA (Load Effective Address) komutu tek çevrimde işlenebildiğinden, bu kadar transistör bütçesini buna ayırmak gayet iyi bir tercihti.

    • Bu devre gerçekten orada mı kullanılıyor? Yazıdan anladığım kadarıyla bu devre kayan nokta çarpmasının bir parçası.
    • Ne demek istediğini anlamadım.
      LEA, adresleme modunun hesapladığı adresi o adresten veri taşımak yerine çıktı operandına koyan bir komuttan ibaret; LEA’nın yapabildiği adres hesaplamalarının hepsini MOV komutu da yapabilir.
      x86’da MOV veya LEA’nın kullandığı index adresleme modu 3 ölçek katsayısını desteklemez; yalnızca 1, 2, 4, 8 gibi 2’nin kuvvetlerini destekler. Bu yüzden adres üretiminde 3 ile çarpmanın kullanılacağı bir yer yok.
      Yazı, 3 ile çarpma biriminin kayan nokta çarpıcısının bir parçası olduğunu açıkça belirtiyor.

  • “Bu ×3 çarpıcı yaklaşık 9000 transistör içerir; bu da Z80 mikroişlemcisinin tamamından (1976) biraz daha fazladır. ×3 çarpıcının Pentium’un kayan nokta biriminin içindeki kayan nokta çarpıcısının küçük bir parçası olduğunu unutmayın. Yani tek bir işlevin küçük bir parçası, 17 yıl önceki bütün bir mikroişlemciden daha karmaşıktır; bu da işlemci karmaşıklığının ne kadar muazzam arttığını gösterir.”
    Bugünkü yazılım şişkinliğini doğuran şey bu performans artış hızı oldu. Çünkü gelecek yılki performans artışı, algoritmaları ve veri akışı bağlamını/yerelliğini eleştirel biçimde düşünmemenin günahlarının çoğunu örtebiliyordu.
    Bugün, okuduğum kadarıyla silikon yarı iletken teknolojisi ve mevcut fizik anlayışıyla makul biçimde yapılabilecek şeylerin pratik sınırına ulaşmış durumdayız. Artık sarkaç ters yöne hareket etmeli; bilgisayarlar daha sert değil, daha akıllı çalışmalı.

    • “Mevcut fizik anlayışıyla mümkün olan pratik sınırlara” onlarca yıl önce ulaşılmıştı.
    • Yazılım şişkinliğinin donanım iyileştirme hızını yakalaması olgusu Wirth yasası olarak bilinir: https://en.wikipedia.org/wiki/Wirth%27s_law
      Ancak yazılım şişkinliğinin daha hızlı büyüdüğünü düşünüyorum.
    • Öte yandan çarpıcı, Z80’den yapısal olarak çok daha düzenlidir. Pentium’un veri yolu da birkaç kat daha geniştir.
    • Fonksiyon çağrısının tarihi: goto/jmp ile komutlara atlama → vtable araması → sözlükte hash alma ve arama → büyük dil modeli çalıştırma
    • Neyse ki çoğu uygulamada hâlâ iyileştirme için geniş alan var.

  • “7 ile çarpmak yerine sayının 8 katını ekleyip sayıyı çıkararak 7 katını elde eder. İki adım gerekiyor gibi görünebilir, ancak soldaki basamakta 1 ile fazladan çarpma hilesiyle ek adım olmadan 8 katsayısı elde edilir.”
    Bu, ana çarpıcı kısmına sayıyı koymadan önce “bir sonraki basamağa” 1 ekleyen bir toplayıcı olduğu anlamına mı geliyor? Bu da kendi başına elde tahmin devresine benziyor.
    Bunun ne zaman gerekli olduğunu da düşündürüyor: 7 = 8-1, 6 = 8-2, 5 = 8-3, 4 = 8-4
    Son durumda yazı bunun yapıldığını söylemiyor, ama 3 bitlik değerin en yüksek bitine bakarak bir sonraki basamağa 1 eklenip eklenmeyeceğine karar vermek birkaç gate tasarrufu sağlayabilir gibi görünüyor.

  • ×3 devresi gerektiren taban 8 Booth çarpıcısının seçilmiş olması ilginç. Maksimum frekansı artırmak için alan/performans ödünleşimi gibi görünüyor; aynı şey daha fazla pipeline ile de mümkün olabilirdi, demek ki gecikme çevrimi kısıtları varmış.

    • Evet, bu bir ödünleşim. O dönemdeki başka birçok kayan nokta birimi, ek ×3 devresinden kaçınabildiği için taban 4 kullanıyordu.
      Pipeline’a almak zor, çünkü çarpma dizisini ikiye bölmek için iyi bir nokta yok.

  • https://github.com/EI2030/Low-power-E-Paper-OS/blob/master/P...
    8086: 29.000
    386: 275.000
    486: 1,2 milyon
    Pentium: 3,1 milyon
    Hatırladığım kadarıyla NSA 2000’den sonra bir noktada bu alana girdi.