Pentium memiliki rangkaian khusus kompleks untuk mengalikan dengan 3

 (righto.com)
3 poin oleh GN⁺ 2025-03-04 | 1 komentar | Bagikan ke WhatsApp
  • Pada 1993, Intel Pentium menyertakan rangkaian khusus ×3 untuk menghasilkan nilai tiga kali lipat agar perkalian floating-point bisa diproses lebih cepat, dan rangkaian kecil ini saja menggunakan ribuan transistor
  • Pentium memakai perkalian radix-8 untuk mengurangi jumlah suku yang dijumlahkan pada perkalian 64-bit dari 64 menjadi 22, tetapi pendekatan ini mengharuskan pembuatan kelipatan ×3 dengan cepat
  • Perhitungan ×3 sendiri adalah penjumlahan x + 2x, tetapi karena tahap perkalian lainnya harus menunggu hasil ini, dibutuhkan teknik adder berkecepatan tinggi seperti carry lookahead dan Kogge-Stone
  • Rangkaian ini memiliki struktur hierarkis yang menggabungkan 8 blok 8-bit dan lookahead tingkat atas, dan keluaran nyatanya diperluas menjadi 69-bit untuk overflow dan pembulatan
  • Sekitar 9000 transistor dipakai untuk satu rangkaian ×3, menunjukkan betapa rumitnya optimasi perangkat keras yang diterapkan demi performa pada era Pentium

Mengapa Pentium memiliki rangkaian ×3 terpisah

  • Pengali floating-point pada Pentium mengalikan dua bilangan 64-bit dengan metode radix-8
    • Perkalian biner biasa menambahkan 0 atau multiplicand untuk setiap bit, sehingga pada perkalian 64-bit dibutuhkan 64 suku
    • Metode radix-8 mengelompokkan pengali per 3 bit untuk mengalikan salah satu dari 0~7, sehingga jumlah suku yang dijumlahkan berkurang menjadi 22
  • Sebagian kelipatan dari 0~7 relatif mudah dibuat di perangkat keras
    • ×2 diproses dengan shift kiri 1 bit
    • ×4 diproses dengan shift kiri 2 bit
    • ×6 dan ×7 dapat diproses dengan algoritme perkalian Booth melalui kombinasi +1 dari digit radix-8 berikutnya dan pengurangan pada digit saat ini
    • ×5 bisa diperoleh dengan mengurangkan ×3 dari ×8
  • Pada akhirnya, kelipatan yang paling merepotkan adalah ×3, dan Pentium menyelesaikannya dengan rangkaian khusus di dalam pengali floating-point

Titik ketika penjumlahan sederhana menjadi bottleneck

  • Nilai 3 kali lipat dapat dibuat dengan menambahkan nilai masukan dan nilai masukan yang digeser kiri 1 bit
    • Jika hanya melihat strukturnya, ini adalah penjumlahan x + 2x
  • Bottleneck muncul pada propagasi carry dalam proses penjumlahan
    • Ripple-carry adder mengharuskan carry yang muncul di bit rendah diteruskan secara berurutan hingga ke bit tinggi
    • Selama hasil ×3 belum siap, sisa proses perkalian tidak bisa dimulai, jadi latensi harus ditekan
  • Pentium memakai carry-lookahead adder untuk menghitung carry secara paralel alih-alih menyebarkannya secara berurutan
    • Pada setiap bit dibuat sinyal carry generate dan carry propagate
    • Generate menunjukkan bahwa posisi tersebut menghasilkan carry
    • Propagate menunjukkan bahwa carry yang masuk akan diteruskan keluar
    • Jika carry dihitung secara paralel, bit sum juga bisa dihitung secara paralel

Kogge-Stone dan carry lookahead 2 tahap

  • Jika carry lookahead diimplementasikan langsung secara sederhana, beban rangkaian dan wiring akan meningkat seiring bertambahnya jumlah bit
    • Logika menjadi lebih kompleks pada posisi bit yang lebih tinggi
    • Gate dengan banyak input menjadi lebih lambat karena alasan elektris
  • Pentium menggunakan parallel prefix adder Kogge-Stone dalam unit 8-bit
    • Kogge-Stone menghitung carry secara paralel dengan menggabungkan sinyal propagate/generate per rentang
    • Hasil antara digunakan kembali untuk mengelola latensi dan jumlah rangkaian
  • Alih-alih memproses seluruh 64-bit dengan satu Kogge-Stone, Pentium membaginya menjadi struktur hierarkis 2 tahap
    • Lapisan bawah menghitung carry di dalam tiap blok dengan 8 rangkaian Kogge-Stone 8-bit
    • Lapisan atas menghitung carry antarblok dengan memperlakukan tiap blok 8-bit sebagai satu unit
    • Kedua lapisan digabung untuk menyediakan carry yang dibutuhkan bagi penjumlahan 64-bit dengan cepat
  • Rangkaian ini bisa dipandang sebagai untuk 64-bit, tetapi pada praktiknya menghasilkan keluaran 69-bit karena mencakup bit ekstra untuk pencegahan overflow dan pembulatan

Mengurangi waktu tunggu dengan carry-select

  • Setiap blok 8-bit memiliki carry-select adder
    • Hasil untuk carry-in 0 dan 1 dihitung terlebih dahulu, keduanya sekaligus
    • Ketika rangkaian lookahead tingkat atas memberi tahu carry-in yang sebenarnya, multiplexer memilih hasil yang benar
  • Pendekatan ini menghemat waktu dengan mengorbankan perangkat keras yang lebih banyak
    • Dibutuhkan dua adder dan multiplexer untuk memilih hasil
    • Perhitungan sum dan carry ditumpangtindihkan untuk mengurangi latensi total
  • Blok 8-bit paling rendah tidak memiliki carry-in, jadi tidak memerlukan rangkaian carry-select
    • Bit keluarannya dihitung dengan gerbang XNOR

Apa yang terjadi di dalam blok 8-bit

  • Setiap blok 8-bit pada rangkaian ×3 membagi jalur input ke adder kiri dan jalur kanan
    • Struktur percabangan ini mengimplementasikan ×3 dengan menjumlahkan nilai input dan versi input yang digeser kiri 1 bit
  • Bagian atas blok terdiri dari rangkaian pembuat sinyal propagate/generate
    • Sinyal-sinyal ini masuk ke rangkaian lookahead Kogge-Stone 8-bit
    • Bagian Kogge-Stone tampak tidak beraturan dan bukan seperti blok berulang, karena kompleksitasnya berbeda di tiap posisi bit
  • Bagian bawah blok adalah area carry-select adder
    • Dua hasil sum dihitung lebih dulu, lalu multiplexer memilih sesuai carry-in
    • Blok carry-select adder ditempatkan lebih sempit daripada rangkaian sekitarnya agar tersedia ruang untuk sebagian rangkaian Kogge-Stone tingkat atas
  • Setiap blok memperkuat bit keluarannya dengan rangkaian driver sebelum mengirimkannya ke rangkaian pengali berikutnya

Gerbang XNOR dan implementasi tingkat transistor

  • Gerbang XNOR di area bit rendah diimplementasikan pada Pentium sebagai multiplexer
    • Intel 386 mengimplementasikan XOR dengan gerbang AND-NOR, dan Z-80 memakai pass transistor, tetapi pendekatan Pentium berbeda
  • Rangkaian XNOR tersebut terdiri dari empat inverter dan multiplexer pass-transistor
    • Input B memilih input A atau A yang dibalik sebagai salah satu dari dua masukan multiplexer
    • Hasilnya membentuk fungsi XNOR
  • Dalam analisis foto chip, dua lapisan logam teratas dihapus untuk mengamati lapisan logam bawah M1 dan area silikon terdoping
    • Titik tempat jalur polisilikon melintasi silikon terdoping menjadi gate transistor
    • Rangkaian CMOS terdiri dari transistor NMOS di bagian atas dan PMOS di bagian bawah

Driver keluaran BiCMOS

  • Keluaran rangkaian ×3 membutuhkan arus tinggi
    • Setiap sinyal ×3 dapat menggerakkan hingga 22 suku di dalam pengali floating-point
    • Rangkaian tujuan bisa berada jauh dari rangkaian ×3
    • Karena wiring yang panjang dan banyaknya gate transistor, kapasitans menjadi besar dan dibutuhkan arus besar untuk mengubah sinyal dengan cepat
  • Pentium menggunakan proses BiCMOS yang menggabungkan transistor bipolar dan CMOS pada chip yang sama
    • Pentium memakai rangkaian BiCMOS secara luas untuk mengurangi delay sinyal hingga 35%
    • Intel juga memakai BiCMOS pada Pentium Pro, Pentium II, Pentium III, dan Xeon
    • Seiring turunnya tegangan chip, keuntungan transistor bipolar berkurang dan BiCMOS akhirnya tidak lagi digunakan
  • Driver pada rangkaian ×3 memiliki struktur di mana driver BiCMOS menggerakkan driver BiCMOS kedua
    • Gate transistor pada inverter arus tinggi berukuran besar, sehingga dibutuhkan tahap perantara untuk menggerakkannya
    • Memperbesar sinyal kecil lewat beberapa tahap dapat mengurangi latensi total
  • Transistor NPN pada driver BiCMOS tampak seperti kotak besar, tidak seperti transistor MOS biasa
    • Inverternya memakai struktur CMOS standar yang menaikkan keluaran dengan PMOS dan menurunkannya dengan NMOS
    • Beberapa inverter dirancang dengan karakteristik arus asimetris agar menghasilkan high yang kuat atau low yang kuat

Perangkat keras perkalian menunjukkan peningkatan kompleksitas

  • Sejarah perangkat keras perkalian komputer dapat ditelusuri hingga 1950-an
    • Teknik perkalian Booth dijelaskan pada 1951
    • Pengali paralel diusulkan oleh Wallace dan Dadda pada pertengahan 1960-an
  • Mikroprosesor awal memiliki dukungan perangkat keras perkalian yang terbatas
    • Prosesor seperti 6502 tidak memiliki perangkat keras perkalian, sehingga pengguna harus mengimplementasikannya di perangkat lunak dengan shift dan penjumlahan
    • Intel 8086 menjalankan loop shift-and-add yang lambat dengan mikrokode
    • 386 menyertakan multiply unit, tetapi instruksi perkalian membutuhkan hingga 41 siklus clock
  • Pada era Pentium, chip sudah dapat memuat jutaan transistor sehingga optimasi performa yang lebih kompleks menjadi mungkin
    • Perkalian floating-point pada Pentium membutuhkan 3 siklus clock, dan rangkaian pengali dipakai selama 2 siklus di antaranya
    • Perkalian integer MUL jauh lebih lambat, yaitu 11 siklus
    • Mikroarsitektur Nehalem pada 2008 menurunkan waktu perkalian floating-point menjadi 1 siklus
  • Pengali ×3 pada Pentium mencakup sekitar 9000 transistor
    • Jumlah ini sedikit lebih banyak daripada seluruh mikroprosesor Z80 pada 1976
    • Rangkaian ×3 hanyalah sebagian kecil dari pengali floating-point di dalam unit floating-point Pentium

Bacaan terkait

1 komentar

 
GN⁺ 2025-03-04
Komentar Hacker News

  • Ini memang agak menyimpang, tetapi dulu sekali saat mengerjakan emulasi komputer ternary, saya pernah memakai trik lucu untuk menemukan transformasi bentuk tertutup yang mengubah operasi pembagian dengan pangkat 3 menjadi deret bit shift dan penjumlahan
    Pertama, lihat bahwa 1/3 - 1/2 = 2/6 - 3/6, yaitu 1/3 = 1/2 - 1/2 (1/3)
    Jika persamaan ini disubstitusikan ke ruas kanan tanpa henti, muncul bentuk 1/3 = -(-1/2)^N, dengan N berada pada rentang 1..inf
    Hal serupa bisa dilakukan bukan hanya untuk pasangan pangkat 2 dan 3, tetapi juga pada basis bilangan lain
    Artinya, untuk nilai yang dekat dengan pangkat 2, cukup mudah membuat rangkaian pembagian konstanta waktu tetap hanya dengan adder dan subtractor

    • Menakjubkan. Komputer ternary pasti berbasis logika tiga keadaan; apakah benar jika saya memahami bahwa ini kurang andal dibanding transistor yang mengodekan keadaan biner, atau bahkan tabung vakum?

  • Prosesor gim arcade Cinematronics memiliki dua akumulator 12-bit
    Instruksi perkalian menggeser keduanya ke kanan seolah-olah keduanya adalah satu nilai 24-bit, lalu jika bit paling rendah bernilai 1, isi memori ditambahkan
    Jadi, bagian atas dikosongkan, satu nilai dimuat ke bagian bawah, saya lupa bagaimana alamat memori untuk operand lain disetel, lalu perkalian 1-bit dijalankan berkali-kali secara berurutan
    Dengan cara ini bisa diperoleh hasil kali 24-bit, tetapi sebagian besar kode yang saya lihat menjalankan 8 instruksi perkalian berturut-turut, dan penggunaan paling umum adalah perkalian matriks 2x2 untuk rotasi koordinat objek gim
    Ini dibuat dengan komponen 7400 series siap pakai pada pertengahan 1970-an, dan throughput puncaknya 5MIPS

    • Saya rasa satu perkalian tidak persis satu siklus. Kalau begitu, 5MIPS juga akan cepat habis
      Dalam 20 tahun terakhir, beberapa kali saya harus melakukan operasi fixed-point, dan rasa hormat saya kepada programmer generasi sebelumnya makin besar

  • Menambahkan pada bagian yang menyebut Anda mungkin pernah mendengar teknik seperti carry lookahead dan Kogge-Stone addition: Kogge di sini adalah Peter Kogge
    Ia mengerjakan riset doktoral di Stanford, bekerja terkait pesawat ulang-alik, merupakan IBM Fellow, dan merupakan sosok yang menemukan CPU multicore pertama

    • Jelas ia punya banyak pencapaian, tetapi menurut saya pernyataan seperti menemukan CPU multicore pertama bisa dihilangkan tanpa mengurangi kebenaran, dan dunia akan lebih baik tanpa ungkapan seperti itu
      “CPU multicore” sendiri, secara ketat, lebih mirip ide daripada satu penemuan. Pada titik tertentu dalam sejarah semikonduktor, itu juga menjadi ide yang cukup jelas dan sederhana
      Membuat CPU multicore benar-benar berjalan memang tidak sederhana, tetapi itu juga bukan satu penemuan tunggal, dan pada saat itu ukuran tim pengembang sudah begitu besar sehingga mengatakan satu orang menyelesaikan semua masalah sendirian justru terasa merendahkan
      Kogge mungkin memimpin pengembangan CPU multicore pertama, dan mungkin pelopor yang mendorongnya sebelum orang lain menganggapnya mungkin, tetapi bagaimanapun juga ia tidak menemukannya sendirian
    • Saya kira tim CPU multicore pertama dipimpin oleh Kunle Olukotun
    • Tambahan lain, Peter Kogge menulis salah satu buku teks awal tentang mikroarsitektur pipeline yang layak dibaca jika ingin mempelajari bagaimana prosesor vektor superkomputer awal dirancang: The Architecture of Pipelined Computers (1981)
    • Peter dulu pernah menjadi penasihat dan berkolaborasi dengan lab kami. Ia mendukung pendekatan memindahkan komputasi penginderaan jauh lebih dekat ke sensor, yang sekarang disebut edge computing
      Pendekatan ini cukup bisa dipertahankan secara intelektual. Jika ada latensi atau biaya untuk memindahkan data ke komputasi terpusat, ini masuk akal, dan dalam kasus kami, karena sensornya berbasis ruang angkasa, argumen seperti itu bisa dibangun
      Namun, sejauh yang saya tahu, cara pemrosesan seperti ini belum pernah diadopsi secara sistematis dalam sistem pemrosesan berbasis ruang angkasa, meskipun banyak sistem seperti radar melakukan reduksi data sementara pada perangkat keras yang dekat dengan sensor
      Terima kasih sudah memberi tahu kaitan itu

  • Saya penulisnya. Kalau ada pertanyaan, saya akan menjawab

    • Saya penasaran apa yang terjadi pada pengali 3x khusus di mesin-mesin berikutnya. Apakah tetap ada dalam bentuk tertentu, atau taktiknya berubah sehingga menjadi tidak berguna?
    • Ken, bukankah sekarang sudah waktunya menerbitkan buku?
    • Mungkin ini pertanyaan dasar, tetapi apakah ini untuk perkalian floating-point? Karena eksponennya juga harus dijumlahkan, bukankah bagian yang benar-benar dikalikan lebih kecil dari 64-bit?
    • Pemahaman saya samar, jadi abaikan saja kalau ini pertanyaan yang terlalu bodoh, tetapi jika “kalau bisa menghitung ×3, kita bisa menguranginya dari ×8 untuk mendapatkan ×5”, mengapa tidak bisa mengurangkan x4 dari x7 untuk mendapatkan x3?

  • Rasanya ada sesuatu yang terlewat
    Jika ×2 bisa dihitung semudah hingga bisa memakai 6x = 8x - 2x, dan ×4 juga mudah dihitung sebagai 4x = 4x, saya tidak mengerti mengapa menghitung 3x sebagai jumlah 2x + 1x atau selisih 4x - 1x lebih sulit daripada itu
    Saya juga penasaran, jika ×6 bisa dihitung dengan mudah dengan cara apa pun, mengapa tidak bisa menggeser nilai itu ke kanan untuk membuat ×3. Memang ada langkah tambahan, tetapi langkah tambahan itu hanya shift

    • Dalam perkalian 64-bit, untuk setiap digit oktal ada satu suku, sehingga total ada 22 suku yang dijumlahkan. Bayangkan perkalian gaya sekolah dasar
      Setiap suku harus sepele untuk dihitung, jadi untuk mendapatkan suku boleh melakukan shift atau pembalikan tanda, tetapi tidak boleh melakukan penjumlahan lain
      Intinya, jika ×3 dihitung terlebih dahulu sekali, setelah itu nilainya bisa langsung dimasukkan ke mana pun dari 22 suku yang diperlukan
      Tidak bisa memasukkan ×2 dan ×1 di dalam satu suku untuk membuat ×3. Untuk itu, setiap suku akan memerlukan adder lain
      Dengan kata lain, yang diinginkan adalah satu rangkaian untuk menghitung ×3, bukan 22 rangkaian
      Untuk pertanyaan ×6, nilai ini dihitung dengan memasukkan ×2 negatif ke dalam suku dan, secara konseptual, menambahkan 1 ke digit berikutnya untuk mendapatkan ×8. Nilai ×8 ini merupakan bagian dari suku yang sama sekali berbeda, sehingga tidak bisa digeser ke kanan
      Angka dan penjumlahan banyak berpindah-pindah sehingga rumit, tetapi kalau dilihat seperti ini seharusnya masuk akal

  • Perkalian 3 kali sebenarnya adalah operasi yang umum, terutama dalam perhitungan alamat, ketika indeks sering dikalikan 3 dengan shift dan penjumlahan.
    Jika diimplementasikan secara naif, latensinya bertambah cukup besar. Namun dengan memakai rangkaian ini, instruksi LEA (Load Effective Address) bisa diproses dalam satu siklus, jadi mengalokasikan anggaran transistor sebesar itu untuk hal ini adalah pilihan yang sangat masuk akal.

    • Apakah rangkaian ini benar-benar dipakai untuk itu? Dari pemahaman saya terhadap tulisannya, rangkaian ini adalah bagian dari perkalian floating-point.
    • Saya tidak mengerti maksudnya.
      LEA hanyalah instruksi yang memasukkan alamat yang dihitung oleh mode pengalamatan ke operand keluaran, alih-alih memindahkan data dari alamat tersebut; dan semua perhitungan alamat yang bisa dilakukan LEA juga bisa dilakukan oleh instruksi MOV.
      Mode pengalamatan indeks yang dipakai MOV atau LEA di x86 tidak mendukung faktor skala 3, hanya mendukung pangkat dua seperti 1, 2, 4, dan 8. Jadi dalam pembangkitan alamat tidak ada tempat untuk memakai perkalian 3 kali.
      Tulisan itu dengan jelas menyatakan bahwa pengali 3 kali adalah bagian dari pengali floating-point.

  • “Pengali ×3 ini berisi sekitar 9.000 transistor, sedikit lebih banyak daripada keseluruhan mikroprosesor Z80 (1976). Ingat bahwa pengali ×3 hanyalah sebagian kecil dari pengali floating-point di dalam unit floating-point Pentium. Dengan kata lain, satu potongan kecil dari satu fungsi lebih kompleks daripada seluruh mikroprosesor dari 17 tahun sebelumnya, dan ini menunjukkan betapa luar biasanya peningkatan kompleksitas prosesor.”
    Laju pertumbuhan performa seperti inilah yang melahirkan pembengkakan perangkat lunak saat ini. Karena peningkatan performa tahun depan bisa menutupi sebagian besar dosa karena tidak berpikir kritis tentang algoritma serta konteks dan lokalitas aliran data.
    Saat ini, sejauh yang saya baca, kita sudah mencapai batas praktis dari apa yang secara wajar bisa dilakukan dengan teknologi semikonduktor silikon dan pemahaman fisika saat ini. Sekarang bandul harus bergerak ke arah sebaliknya, dan komputer harus bekerja lebih cerdas, bukan lebih keras.

    • “Batas praktis yang mungkin dengan pemahaman fisika saat ini” sudah dicapai sejak puluhan tahun lalu.
    • Fenomena ketika pembengkakan perangkat lunak mengejar laju peningkatan perangkat keras dikenal sebagai Hukum Wirth: https://en.wikipedia.org/wiki/Wirth%27s_law
      Namun menurut saya pembengkakan perangkat lunak tumbuh lebih cepat.
    • Sebaliknya, struktur pengali jauh lebih teratur daripada Z80. Jalur data Pentium juga beberapa kali lebih lebar.
    • Sejarah pemanggilan fungsi: perpindahan instruksi dengan goto/jmp → pencarian vtable → hashing dan lookup di dictionary → menjalankan model bahasa besar.
    • Untungnya, sebagian besar aplikasi masih punya banyak ruang untuk perbaikan.

  • “Alih-alih mengalikan dengan 7, ia menambahkan 8 kali angka tersebut lalu mengurangi angkanya untuk mendapatkan 7 kali. Ini mungkin tampak membutuhkan dua tahap, tetapi dengan trik mengalikan 1 tambahan pada digit di sebelah kiri, koefisien 8 kali diperoleh tanpa tahap tambahan.”
    Apakah ini berarti ada adder yang menambahkan 1 ke “digit berikutnya” sebelum angka dimasukkan ke bagian pengali utama? Itu sendiri juga tampak mirip dengan rangkaian carry prediction.
    Saya juga jadi memikirkan kapan ini diperlukan: 7 = 8-1, 6 = 8-2, 5 = 8-3, 4 = 8-4
    Untuk kasus terakhir, tulisan itu tidak mengatakan bahwa itu dilakukan, tetapi jika memakai bit paling signifikan dari nilai 3-bit untuk menentukan apakah perlu menambahkan 1 ke digit berikutnya, sepertinya beberapa gerbang bisa dihemat.

  • Menarik bahwa mereka memilih pengali Booth radix 8 yang membutuhkan rangkaian ×3. Ini terlihat seperti trade-off area/performa untuk menaikkan frekuensi maksimum, dan karena hal yang sama mungkin bisa dilakukan dengan lebih banyak pipelining, tampaknya ada batasan pada siklus latensi.

    • Benar, itu trade-off. Saat itu banyak unit floating-point lain memakai radix 4 karena bisa menghindari rangkaian ×3 tambahan.
      Pipelining itu rumit, karena tidak ada posisi yang bagus untuk membagi array pengali menjadi dua.

  • https://github.com/EI2030/Low-power-E-Paper-OS/blob/master/P...
    8086: 29.000
    386: 275.000
    486: 1,2 juta
    Pentium: 3,1 juta
    Sepingat saya, NSA masuk ke ranah ini pada suatu titik setelah tahun 2000.