Trik radix 2^51 (2017)

 (chosenplaintext.ca)
1 poin oleh GN⁺ 2025-05-31 | 1 komentar | Bagikan ke WhatsApp
  • Penjumlahan bilangan bulat besar biasanya diproses dengan membaginya menjadi limb 64-bit, tetapi jika propagasi carry terjadi, sulit memanfaatkan keunggulan eksekusi paralel CPU modern secara penuh
  • adc pada x86 bergantung pada carry flag dari operasi sebelumnya sehingga merangkai instruksi secara serial, dan ini menjadi bottleneck bahkan pada arsitektur seperti Intel Haswell yang mampu mengeksekusi beberapa add secara paralel
  • Representasi radix 2^51 membagi nilai 256-bit menjadi lima digit basis 2^51 alih-alih empat digit basis 2^64, lalu memanfaatkan bit-bit atas yang tersisa pada tiap limb sebagai ruang penyimpanan carry sementara
  • Ini bukan cara untuk menghilangkan carry, melainkan menunda propagasinya selama beberapa kali penjumlahan lalu memprosesnya sekaligus pada tahap normalisasi terakhir
  • Dalam benchmark sederhana di Haswell, bahkan setelah memasukkan biaya konversi, metode ini sudah lebih cepat daripada pendekatan radix 2^64 mulai dari tiga kali penjumlahan, dan keuntungannya makin besar saat jumlah iterasi bertambah

Mengapa carry menjadi bottleneck dalam penjumlahan bilangan bulat besar

  • Penjumlahan panjang di atas kertas biasanya dilakukan dari kanan ke kiri, mulai dari digit satuan
    • Karena hasil tiap digit bergantung pada carry yang datang dari digit di sebelah kanan
    • Jika dijumlahkan dari kiri, carry yang muncul belakangan dapat memaksa hasil digit depan yang sudah dihitung untuk diperbaiki lagi
  • Penjumlahan bilangan bulat besar memiliki kendala yang sama
    • Jika bilangan bulat 256-bit x dan y dibagi menjadi empat limb 64-bit, maka limb pada posisi yang sama dapat dijumlahkan satu sama lain
    • Jika terjadi overflow pada limb yang lebih rendah, nilai 1 itu harus diteruskan ke limb yang lebih tinggi
  • adc pada x86 adalah instruksi untuk menangani propagasi ini
    • Instruksi ini melihat apakah operasi sebelumnya overflow, lalu menambahkan 1 bila diperlukan
    • Penjumlahan 256-bit yang benar akan berurutan dari limb paling rendah sebagai add, adc, adc, adc

Struktur yang membuat adc melambat di CPU modern

  • adc umumnya lebih mahal dieksekusi daripada add biasa
    • adc lebih kompleks daripada add karena menggunakan carry flag sebagai input ketiga
    • Karena digunakan lebih jarang daripada add, perancang CPU juga memiliki insentif lebih kecil untuk mengalokasikan area chip demi mengoptimalkan performa adc
  • Masalah yang lebih besar adalah ketergantungan instruksi
    • Pada Intel Haswell, satu add membutuhkan 1 siklus untuk dieksekusi
    • Dalam kondisi ideal, Haswell dapat mengeksekusi hingga 4 add per siklus
    • Haswell memiliki 8 execution port, dan 4 di antaranya dapat menjalankan add bilangan bulat
  • Empat add yang independen mudah dieksekusi secara paralel
    • Sebaliknya, rantai adc membuat tiap instruksi bergantung pada carry flag keluaran dari instruksi sebelumnya
    • CPU tidak bisa memparalelkannya dan harus mengeksekusinya secara berurutan
  • Pada SIMD, kerugiannya bahkan lebih besar
    • vpaddq melakukan empat penjumlahan 64-bit sekaligus
    • Haswell dapat mengeksekusi dua vpaddq per siklus
    • Jika paralelisme ini harus ditinggalkan demi menangani carry, keuntungan performanya ikut berkurang

Menunda carry lewat analogi penjumlahan di atas kertas

  • Kita bisa menunda carry dengan mempertahankan nilai tempat desimal, tetapi memperluas himpunan simbol yang boleh masuk ke tiap digit
    • Alih-alih 0-9, digunakan total 37 simbol hingga A-Z dan *
    • Namun basis bilangannya sendiri bukan basis 37; nilai tempatnya tetap desimal
  • Dengan begitu, digit yang melewati 9 tidak perlu langsung di-carry
    • 29 + 1 bisa ditulis sebagai 30, tetapi juga dapat direpresentasikan sebagai 2A, 1K, atau U
    • Jika setiap digit dari kedua bilangan semuanya sudah ternormalisasi hingga maksimal 9, carry saat penjumlahan dapat ditunda
  • Ini tidak selalu berlaku untuk semua input
    • Jika sudah ada digit besar seperti 9 + W, carry tetap diperlukan
    • Untuk bilangan yang ternormalisasi, hingga empat buah bilangan masih dapat dijumlahkan tanpa carry
  • Pada akhirnya hasilnya tetap harus dinormalisasi kembali ke representasi desimal biasa
    • Dari kanan, hitung berapa banyak kelompok 10 yang terkandung dalam tiap digit
    • Kurangi sebanyak itu dari digit saat ini lalu teruskan ke digit berikutnya
  • Intinya bukan menghapus propagasi carry, melainkan menyimpannya selama perhitungan antara lalu mempropagasikannya sekali di bagian akhir

Representasi radix 2^51 di komputer

  • Jika nilai 256-bit dibagi menjadi empat limb basis 2^64, setiap limb dapat memiliki nilai dari 0 sampai 2^64−1
    • Ini adalah cara memandang tiap limb sebagai digit dalam basis 2^64
  • Karena rentang integer 64-bit pada perangkat keras tidak bisa diperlebar, ukuran basisnya diperkecil
    • Nilai 256-bit dibagi menjadi lima digit basis 2^51 alih-alih empat digit basis 2^64
    • Setiap limb tetap disimpan sebagai integer 64-bit, tetapi nilai aktualnya hanya memakai 51 atau 52 bit
  • Bit-bit atas yang tersisa menjadi ruang penyimpanan carry sementara
    • Tiap limb memuat 51 atau 52 bit dari angka aslinya
    • Sisa 12 atau 13 bit menampung carry yang timbul selama perhitungan
  • Teknik ini dalam literatur kriptografi disebut radix 2^51 representation
  • Untuk bilangan yang sudah ternormalisasi, di dalam 2^64 kemungkinan nilai limb, kita tidak perlu mengkhawatirkan overflow pada 13 bit atas sampai sebelum menjumlahkan maksimal 2^13 buah nilai

Limb paling atas 52-bit dan normalisasi

  • Limb paling atas dialokasikan 52 bit
    • Limb lainnya menggunakan 51 bit
    • Carry dari limb paling atas diabaikan sehingga nilai yang melebihi 2^256−1 akan dibungkus kembali
    • Ini sama seperti cara penjumlahan integer unsigned berukuran tetap biasa di C yang wrap saat overflow
  • Kode penjumlahan radix 2^51 tidak memakai rantai adc, melainkan mengeksekusi lima add secara independen
    • Dibanding pendekatan empat limb basis 2^64, jumlah add meningkat dari 4 menjadi 5
    • Sebagai gantinya, tidak ada ketergantungan pada carry flag sehingga eksekusi paralel dimungkinkan
  • Pada tahap normalisasi, bit-bit atas dari tiap limb diambil lalu ditambahkan ke limb yang lebih tinggi berikutnya
    • shr 51 digunakan untuk mengekstrak bagian carry
    • and 0x0007FFFFFFFFFFFF menyisakan hanya 51 bit terbawah
    • Limb paling atas dirapikan dengan and 0x000FFFFFFFFFFFFF
  • Normalisasi adalah tahap yang menjalankan propagasi carry yang sebelumnya ditunda
    • Dalam penjumlahan antara, ketergantungan pada carry flag tidak dibentuk
    • Pada akhirnya, tiap limb dikembalikan lagi ke rentang yang diizinkan

Hasil performa dan perluasan ke pengurangan

  • Dalam benchmark sederhana, penjumlahan radix 2^51 menunjukkan hasil yang lebih cepat pada CPU Haswell
    • Termasuk biaya konversi ke dan dari representasi radix 2^51
    • Hanya dengan tiga kali penjumlahan, metode ini sudah lebih cepat daripada penjumlahan radix 2^64
    • Semakin banyak jumlah penjumlahan, semakin besar pula penghematan yang diperoleh
  • Ide yang sama dapat diperluas ke pengurangan
    • Dalam pengurangan, carry menjadi carry negatif
  • Untuk mendukung pengurangan, limb diperlakukan bukan sebagai unsigned melainkan seperti integer signed
    • Setiap nilai digit dapat bernilai positif atau negatif
    • Tiap limb dapat menyimpan carry positif maupun carry negatif
  • Perubahan ini ada biayanya
    • Bit paling atas dari tiap limb harus dicadangkan sebagai bit tanda
    • Jumlah operasi yang dapat dilakukan di antara dua normalisasi turun dari 2^13 menjadi 2^12
  • Meskipun data dibagi ke lebih banyak register dan jumlah operasinya bertambah, mengurangi ketergantungan carry tetap dapat meningkatkan performa keseluruhan

Bacaan terkait

1 komentar

 
GN⁺ 2025-05-31
Opini di Hacker News

  • Saya penasaran apakah bisa saja limb teratas dibuat 64-bit, sementara empat limb lainnya masing-masing 48-bit
    Sebelum normalisasi, kita bisa mengakumulasi lebih banyak penjumlahan; jika set instruksinya punya fitur yang berguna, penyelarasan word juga bisa dimanfaatkan saat pemisahan dan normalisasi, dan karakteristik overflow-nya tampak sama

    • Jika salah satu targetnya adalah melakukan operasi 256-bit dengan 5 register 64-bit, berarti tiap word memakai 256/5 = 51,2 bit, jadi ini terlihat seperti penempatan yang cukup ideal
      Untuk pustaka bilangan besar serbaguna, ini mungkin bukan yang optimal; dulu, karena belum ada barrel shifter yang efisien untuk melakukan shift bit sembarang, pendekatan seperti memakai 56 bit dari 64 bit dan menyisakan tepat 1 byte untuk carry mungkin lebih baik
      Karena RISC-V tidak punya flag, diskusi ini cukup relevan
    • Jika limb teratas dari dua angka yang dienkode dijumlahkan, overflow terjadi terlalu cepat
      Misalnya jika keduanya 2^63, langsung meluap; mungkin cocok untuk aritmetika wrapping, tetapi tidak sesuai untuk kasus umum
    • Jika begitu, untuk menyimpan nilai 256-bit dibutuhkan 6 word, bukan 5 word seperti metode di artikel, sehingga instruksi penjumlahannya juga lebih banyak

  • Dengan AVX512, dan sampai batas tertentu AVX2, penjumlahan 256-bit bisa diimplementasikan cukup efisien, dan ada juga keuntungan bisa menyimpan lebih banyak angka di register
    Caranya menggabungkan _mm256_add_epi64, mask perbandingan, dan mask carry; throughput-nya juga terlihat lebih baik: https://godbolt.org/z/e7zETe8xY
    Mengubahnya menjadi penjumlahan 512-bit juga sederhana, dan saat itu peningkatannya mungkin lebih besar

  • Pada CPU x86 yang cukup baru, misalnya Intel Broadwell atau AMD Ryzen, ADX juga bisa dipakai, dan bahkan dalam situasi seperti Curve25519, tempat representasi radix 2^51 secara tradisional menguntungkan, sekarang bisa saja lebih cepat
    [1] https://en.wikipedia.org/wiki/Intel_ADX

  • Tulisan terkait mencakup thread lama tentang radix 2^51 trick
    The radix 2^51 trick - https://news.ycombinator.com/item?id=33706153 - November 2022
    The radix 2^51 trick (2017) - https://news.ycombinator.com/item?id=23351007 - Mei 2020

  • Intinya, meski jumlah operasinya lebih banyak, jika sebagian besar independen, operasi itu bisa dijalankan paralel sehingga bisa lebih cepat
    Sebaliknya, walau jumlah operasinya lebih sedikit, jika harus dijalankan serial karena dependensi data, hasilnya bisa lebih lambat; ide ini berlaku jauh lebih luas daripada operasi bilangan bulat panjang

    • Pendekatan lain adalah tetap memakai potongan 64-bit biasa, tetapi menjalankan tiap penjumlahan secara spekulatif dan paralel untuk kasus dengan carry dan tanpa carry, lalu memilih sisi yang benar berdasarkan hasil carry dari penjumlahan digit rendah
      Jumlah penjumlahan menjadi dua kali lipat, tetapi waktu propagasi carry bisa dikurangi dari linear menjadi log(bits)
    • Bagian yang kurang saya pahami adalah bahwa teknik yang ditunjukkan di sini tampaknya berfokus pada membuat ripple carry saat menjumlahkan N nilai terjadi hanya sekali, bukan N-1 kali
      Operasi carry lebih kompleks, tetapi penjumlahan aktualnya bisa diparalelkan
      Namun sejak awal angka input harus dipecah menjadi kelompok 5 register, jadi agar secara keseluruhan menguntungkan, bukankah pemecahan itu juga harus bisa diparalelkan?
    • Nvidia sedang mendalami gagasan umum itu, dan tampaknya menghasilkan hasil yang cukup menjanjikan di beberapa bidang
    • Aturan ini juga meluas hingga superkomputer multi-node atau cloud
      Jika bisa mengerahkan 10.000 core, overhead-nya bisa diabaikan

  • Ini menunjukkan dengan sangat baik bahwa orang yang hanya bekerja dengan x86_64 tidak benar ketika menganggap RISC-V keliru karena menghilangkan carry flag

    • Ada cara lain sambil tetap mempertahankan limb 64-bit
      Wawasan utamanya adalah selama jumlah pada posisi limb tertentu tidak semuanya 1, carry yang keluar dari posisi itu tidak bergantung pada carry yang masuk, melainkan hanya bergantung pada apakah penjumlahan asli di posisi itu menghasilkan carry
      Jika jumlahnya semuanya 1, carry keluar sama dengan carry masuk
      Jika ini diekspresikan sebagai percabangan kondisional yang hampir selalu diprediksi not-taken, maka dengan asumsi beberapa percabangan kondisional dapat diprediksi not-taken dalam siklus clock yang sama, setiap blok instruksi dapat dijalankan sepenuhnya paralel
      Sekali setiap 2^64 kali, eksekusinya menjadi sangat lambat
      Pada mesin 4-wide dengan angka 4-limb, ini tidak lebih unggul daripada adc, tetapi pada mesin 8-wide dengan angka 8-limb, keuntungannya mulai membesar
      Ini mungkin tidak banyak membantu x86_64 saat ini, tetapi ada peluang pada Apple M series yang seperti M1 juga 8-wide, meski karena ISA Arm, workaround-nya bisa rumit
      Ketika RISC-V Ascalon 8-wide dari Tenstorrent keluar pada akhir tahun ini atau awal 2026, bersama Ventana, Rivos, XiangShan, dan lainnya, hal ini akan bisa diuji secara nyata
      Jika ada shift 1-lane yang cepat, ini juga bekerja lebih baik pada SIMD lebar; di RISC-V ini disebut slideup
    • Carry-save addition masih sering lebih buruk daripada add-with-carry dalam banyak kasus umum
      Kedua algoritma penjumlahan multi-word itu tidak saling menggantikan dan memiliki kegunaan berbeda, jadi ISA yang layak menyertakan instruksi ADC/SBB, dan biaya tambahannya juga kecil
      Register flag khusus juga tidak mutlak diperlukan; beberapa ISA menyimpan flag carry/borrow di register serbaguna saat dibutuhkan
      Tidak adanya carry di RISC-V bukan fitur terburuknya; yang lebih buruk adalah tidak adanya integer overflow flag
      Deteksi integer overflow wajib untuk program yang mengklaim ditulis secara aman, dan jika ini diakali lewat software, performa yang bisa dicapai turun jauh lebih besar daripada workaround untuk absennya carry
    • Alur ini pada akhirnya berasal dari C yang menghilangkan carry flag, dan dalam praktiknya flag itu hampir tidak lagi dipakai untuk carry
    • Jika carry flag memang lambat, saya bukan satu-satunya yang berpikir, “lalu sebenarnya apa masalahnya dengan kontroversi RISC-V GMP?”

  • Radix trick ini juga berlaku pada struktur data
    Ada contoh bagus dalam buku Okasaki, 『Purely Functional Data Structures』

  • Seandainya saya melihat tulisan ini beberapa bulan lalu
    Saat mencoba mengenkode dan mendekode buffer dengan basis sembarang, saya terlambat sekali sampai pada kesimpulan bahwa carry bisa merambat sampai ujung buffer dan karena itu algoritmanya menjadi jauh lebih lambat
    Pada akhirnya solusinya juga mirip dengan trik ini: saya membagi buffer menjadi chunk dan menyisakan ruang longgar untuk menangani carry
    Tidak persis sama; dengan menyisakan beberapa bit terbuang, saya memakai sedikit lebih banyak ruang penyimpanan atau bandwidth jaringan sebagai ganti pengurangan komputasi
    Saya penasaran apakah dengan mengumpulkan carry seperti ini lalu menyelesaikannya pada tahap berikutnya, kita bisa mendapatkan keduanya sekaligus, tetapi mungkin itu hanya harapan

  • Saya tahu pedoman HN mengatakan jangan mengedit judul, tetapi saya tidak suka judul clickbait yang membesar-besarkan klaim kecil menjadi terlalu luas
    Judul tulisan ini seharusnya kira-kira “Trik radix 2^51 untuk menjumlahkan bilangan bulat 64-bit secara paralel pada sebagian arsitektur x86 tanpa memperlambat pipeline karena dependensi carry”