Trik radix 2^51 (2017)

• Masalah carry pada operasi bilangan bulat besar adalah salah satu penyebab utama yang menyulitkan paralelisasi komputasi
• Pada arsitektur x86, instruksi adc untuk menangani carry lebih lambat daripada instruksi add biasa, dan pemrosesan carry beruntun membatasi eksekusi paralel
• Dengan menggunakan representasi radix 2^51, propagasi carry dapat ditunda sehingga lebih banyak operasi penjumlahan bisa dilakukan dengan cepat
• Setiap limb (nilai parsial) hanya dialokasikan 51 atau 52 bit, dan sisa ruang bit atas digunakan sebagai penyimpanan sementara carry
• Teknik ini meskipun membutuhkan register tambahan dan biaya konversi, dalam praktiknya memberikan performa yang lebih baik daripada radix 2^64

---

Penjumlahan dan pengurangan cepat: masalah carry

• Dalam penjumlahan bilangan bulat besar, seperti manusia yang menangani carry per digit saat menghitung dengan tangan, komputer juga sulit memparalelkan algoritme penjumlahan karena carry
• Pada dasarnya kita menjumlahkan satu per satu dari kanan (digit lebih rendah), lalu carry yang muncul di setiap digit dinaikkan ke kiri (digit lebih tinggi)
• Jika penjumlahan dimulai dari kiri, carry sebelumnya akan memengaruhi operasi digit berikutnya, sehingga urutan komputasi tidak bisa diparalelkan

Penanganan carry di komputer

• Komputer memproses penjumlahan dalam satuan bilangan bulat 64-bit
• Penjumlahan bilangan bulat 256-bit tampak seolah bisa diparalelkan dengan membaginya menjadi 4 limb 64-bit, tetapi pada praktiknya hasil yang benar hanya diperoleh jika overflow (carry) ditangani
• x86 memiliki instruksi adc (add with carry) yang secara otomatis menangani carry

Penyebab penurunan performa

• Instruksi adc memerlukan nilai masukan tambahan berupa carry flag, sehingga performanya lebih rendah dibanding add sederhana
• Pada arsitektur Haswell, add bisa dieksekusi paralel di beberapa port, sedangkan adc tak terhindarkan harus berjalan secara serial (berurutan)
• Terutama saat menggunakan instruksi SIMD (vpaddq dan sejenisnya), penjumlahan paralel tanpa carry jauh lebih cepat

Ide menunda carry (contoh di atas kertas)

• Untuk mengurangi carry, rentang digit dapat diperluas (misalnya dari 0-9 menjadi total 37 simbol: 0-9, A-Z, dan *) sehingga beberapa bilangan bisa dijumlahkan sementara tanpa carry
• Dengan cara ini, beberapa penjumlahan dapat dilakukan tanpa propagasi carry, lalu carry dirapikan sekaligus di akhir melalui normalization
• Konsep ini memisahkan akumulasi carry dan propagasinya sehingga carry hanya ditangani pada tahap akhir
• Dalam komputasi nyata, jika suatu digit melebihi nilai dasar digit, carry diakumulasikan dan diterapkan berurutan dari sisi kanan

Penerapan penundaan carry di komputer (trik radix 2^51)

• Untuk mengurangi propagasi carry di komputer, digunakan representasi radix 2^51
• Bilangan 256-bit dibagi bukan menjadi 4 limb 64-bit, melainkan 5 limb masing-masing 51~52 bit
  • 12~13 bit teratas pada setiap limb berfungsi sebagai penyimpanan sementara carry
• Dengan pendekatan ini, setiap limb tetap berada dalam rentang nilai 2^64, tetapi carry tidak mudah muncul selama operasi, sehingga banyak operasi bisa dilakukan secara paralel tanpa carry
• Normalization (normalisasi) diperlukan sekali setelah sekitar 2^13 operasi beruntun
• Pada CPU Haswell, setelah menerapkan radix 2^51, cukup dilakukan beberapa penjumlahan sederhana tanpa carry, sehingga performa meningkat jauh dibanding radix 2^64 biasa
• Propagasi carry untuk normalization hanya dilakukan sekali di bagian akhir

Contoh kode

• Nilai dibagi ke dalam 5 register sehingga penjumlahan tanpa carry dapat dilakukan
• Normalization dilakukan dengan mengekstrak bit atas dari tiap limb, menambahkannya ke limb sebelah, lalu mengosongkan nilai carry miliknya sendiri, dan mengulangi proses ini

Ekstensi ke pengurangan

• Pengurangan juga dapat diterapkan dengan cara yang serupa
• Dalam kasus ini carry juga bisa bernilai negatif, sehingga limb diperlakukan sebagai signed integer
• Bit tertinggi pada limb dialokasikan sebagai bit tanda, sehingga jumlah operasi yang dapat diproses sekaligus sedikit lebih sedikit dibanding penjumlahan

Kesimpulan

• Teknik ketahanan terhadap carry (penundaan carry), meskipun menambah jumlah limb dan pekerjaan konversi, secara nyata sangat meningkatkan performa keseluruhan komputasi
• Trik radix 2^51 banyak digunakan pada operasi bilangan bulat skala besar, kriptografi, dan bidang lain yang menuntut performa tinggi
• Teknik ini adalah ide penting untuk mengoptimalkan performa nyata perangkat keras dan algoritme

[GN⁺]

Pendapat Hacker News

• Saat melihat angka 2^51, awalnya saya kira ini soal penyimpanan bilangan bulat dalam tipe double, tetapi kemudian sadar bahwa nilai yang bisa disimpan tepat sebagai integer dalam double sebenarnya adalah 2^53-1

• AVX512 (dan sampai batas tertentu juga AVX2) menyediakan lingkungan untuk mengimplementasikan operasi penjumlahan 256-bit dengan cukup efisien, dengan kelebihan tambahan bisa menampung lebih banyak angka dalam register
  Contoh langsungnya bekerja seperti kode di bawah ini

__m256i s = _mm256_add_epi64(a, b);
const __m256i all_ones = _mm256_set1_epi64x(~0);
int g = _mm256_cmpgt_epu64_mask(a, s);
int p = _mm256_cmpeq_epu64_mask(s, all_ones);
int carries = ((g << 1) + p) ^ p;

__m256i ret = _mm256_mask_sub_epi64(s, carries, s, all_ones);

Bahkan terlihat ada peningkatan throughput, dan contoh kode nyatanya bisa dilihat di godbolt.org
Memperluas logika ini sampai penjumlahan 512-bit juga sangat sederhana

• Secara khusus ditunjukkan bahwa pada arsitektur CPU Intel tertentu, hanya dengan memakai instruksi AVX512 saja seluruh clock prosesor bisa turun, sehingga performa keseluruhan menjadi tidak konsisten atau malah lebih lambat
  Referensi terkait bisa dilihat di tautan stackoverflow

• Menanggapi pertanyaan “kenapa tidak pakai 12 bit saja, bukan 13 bit?”, di sini penanganan carry untuk bit paling atas (limb) diabaikan sehingga saat overflow ia bekerja dalam bentuk wraparound
  Akibatnya limb paling atas diberi alokasi 52 bit, sehingga ada kelemahan yaitu ruangnya habis lebih cepat dibanding limb lain, tetapi perilakunya mirip dengan penjumlahan integer tak bertanda dalam bahasa C
  Lalu diajukan usulan: bagaimana jika limb teratas diberi 64 bit, dan empat limb sisanya masing-masing 48 bit
  Dengan begitu lebih banyak operasi bisa diakumulasikan sebelum normalisasi, dan ada keuntungan seperti alignment word
  Sifat penanganan overflow-nya juga sama

  • Jika hanya limb teratas yang dialokasikan 64 bit, maka saat limb dari dua angka dijumlahkan overflow akan terjadi terlalu cepat
    Misalnya jika keduanya bernilai 2^63, langsung overflow
    Untuk aritmetika wraparound itu tidak masalah, tetapi untuk kasus umum ini terlalu berat

  • Dengan struktur seperti ini, dibutuhkan 6 word, bukan 5 seperti pada OP
    Instruksi yang diperlukan juga jadi lebih banyak

  • Tujuannya adalah menangani matematika 256-bit dengan 5 register 64-bit
    Artinya distribusi ideal per word adalah 256/5 = 51.2 bit
    Kalau ini hanya untuk 256-bit, tidak masalah, tetapi untuk pustaka big-int umum ini bukan pilihan optimal
    Dulu ada latar belakang ingin memakai tepat 1 byte untuk satu carry, dan pada masa belum ada barrel shifter orang lebih suka memakai hanya 56 dari 64 bit demi alignment
    Di RISC-V, karena tidak ada flag di tingkat hardware, diskusi seperti ini jadi makin penting

• Pada CPU x86 modern (misalnya Intel Broadwell, AMD Ryzen), instruksi Intel ADX bisa membuat representasi radix 2^51 lebih cepat bahkan dalam situasi yang secara tradisional lebih unggul untuk pendekatan itu (misalnya Curve25519)

• Sebagai bahan diskusi terkait

  • The radix 2^51 trick (November 2022)
  • The radix 2^51 trick (2017)

• Pelajaran intinya adalah, jika operasi-operasi saling independen, menjalankan lebih banyak operasi secara paralel justru bisa lebih cepat
  Sebaliknya, jika karena dependensi operasi harus dijalankan berurutan, jumlah operasi yang lebih sedikit pun bisa malah lebih lambat
  Ide ini bisa diterapkan bukan hanya pada operasi integer panjang, tetapi juga di banyak bidang lain

  • Diusulkan pendekatan membagi ke dalam chunk 64-bit lalu mengeksekusi dua kemungkinan secara paralel terlebih dahulu, tergantung ada tidaknya carry, dan setelah itu memilih hasil yang benar sesuai carry sebenarnya
    Cara ini memang menggandakan jumlah penjumlahan, tetapi kecepatan propagasinya menjadi setingkat log(bits) alih-alih linear

  • Bagian yang dulu sulit saya pahami dari teknik ini adalah, secara esensial metode ini membuat ripple carry yang biasanya berjalan N-1 kali saat menjumlahkan N nilai, cukup dijalankan sekali saja
    Penanganan carry-nya memang jadi lebih rumit, tetapi penjumlahannya bisa diparalelkan
    Namun, agar efisiensi totalnya berarti, pekerjaan membagi bilangan masukan menjadi unit 5 register itu sendiri juga harus bisa diparalelkan

  • Aturan ini bisa diperluas sampai ke tingkat superkomputer atau cloud dengan puluhan ribu node
    Kalau bisa memakai banyak core, overhead-nya menjadi cukup bisa diabaikan

  • Ide ini juga menarik minat NVidia dan memberikan hasil yang baik di berbagai bidang

• Walaupun ada pedoman HN bahwa kita tidak boleh menambahkan opini ke judul, saya pribadi tidak menyukai judul yang terlalu dibesar-besarkan demi klik
  Menurut saya akan lebih akurat jika dibatasi menjadi semacam “trik radix 2^51 untuk penjumlahan paralel integer 64-bit tanpa dependensi carry pada sebagian arsitektur x86”

• Sayang sekali, andai saya membaca tulisan ini beberapa bulan lebih awal, pasti akan membantu
  Saya pernah mengalami algoritma melambat drastis karena carry merambat ke seluruh buffer saat proses encode/decode buffer ke basis sembarang
  Akhirnya saya menyisakan 'ruang longgar' lalu membaginya menjadi chunk untuk menangani carry, yang tampaknya punya kemiripan dengan trik ini
  Dalam praktiknya saya memilih membuang beberapa bit demi menghemat jumlah operasi atau bandwidth jaringan
  Saya jadi penasaran apakah penanganan carry seperti ini juga bisa digabung sebagai tahap pascaproses
  Harapannya, ini bisa menjadi struktur yang praktis mengambil hampir semua keuntungannya

• Berdasarkan pengalaman yang selama ini hanya memakai lingkungan x86_64, ini dengan jelas menunjukkan bahwa ketiadaan carry flag di RISC-V belum tentu pendekatan yang salah

  • Selain cara ini, dijelaskan juga metode mempertahankan limb 64-bit sambil melakukan penjumlahan aman-carry seluruhnya dengan variabel uint64_t
    Alurnya seperti berikut

  s0 += a0;
  s1 += a1;
  s2 += a2;
  s3 += a3;
  c0 = s0 < a0; // RISC-V sltu
  c1 = s1 < a1;
  c2 = s2 < a2;
  if (s1 == -1) goto propagate0;
  check_s2:
  if (s2 == -1) goto propagate1;
  add_carries:
  s1 += c0;
  s2 += c1;
  s3 += c2;
  goto done;
  propagate0: c1 = c0; goto check_s2;
  propagate1: c2 = c1; goto add_carries;
  done:
  

  Kuncinya adalah, ketika hasil penjumlahan (limb) tidak semuanya 1, carry-out dari limb tersebut tidak bergantung pada carry-in, melainkan hanya pada hasil penjumlahan nilai aslinya
  Sebaliknya, jika nilainya semua 1 maka carry-out = carry-in
  Jika struktur branch-nya hampir tidak membutuhkan prediksi, eksekusinya bisa benar-benar paralel
  Secara probabilistik hanya melambat sekali dalam 2^64 kasus, tetapi pada mesin 4-wide tidak memberi keuntungan besar
  Pada mesin 8-wide atau struktur 8-limb, ini bisa memberi peningkatan performa yang berarti
  Kurang cocok untuk x86_64, tetapi pada mesin 8-wide seperti seri Apple M* ada kemungkinan berguna
  Ada harapan untuk masa depan di prosesor RISC-V 8-wide seperti Ascalon dari Tenstorrent, Ventana, Rivos, XiangShan, dan lainnya
  Efeknya menjadi maksimal pada struktur SIMD atau arsitektur dengan instruksi shift 1-lane cepat (slideup)

  • Penjumlahan carry-save tidak selalu lebih unggul daripada add-with-carry
    Dua jenis algoritma multi-word addition ini tidak bisa saling menggantikan; masing-masing punya kelebihan dan kekurangan
    Karena itu instruksi ADC/SBB tetap perlu ada sebagai bawaan ISA, dan flag berbasis register juga dimungkinkan
    Kekurangan yang lebih serius di RISC-V adalah tidak adanya integer overflow flag
    Saat perlu solusi SW untuk mendeteksi overflow, penurunan performanya jauh lebih besar daripada solusi pengganti carry bit

  • Tidak adanya carry flag di RISC-V merupakan turunan dari fakta bahwa bahasa C mengabaikan binary carry flag
    Dalam praktiknya, frekuensi penggunaan carry flag memang jauh lebih rendah

  • Ternyata bukan hanya saya yang sempat berpikir, “kalau carry flag memang lambat, kenapa dulu ada kontroversi risc5 gmp?”

• 'Radix trick' juga bisa diterapkan pada struktur data
  Ada contoh yang menarik juga di buku Okasaki, 'Purely Functional Data Structures'