Mẹo cơ số 2^51 (2017)

• Trong phép toán số nguyên lớn, vấn đề carry (nhớ) phát sinh là nguyên nhân chính khiến việc song song hóa phép toán trở nên khó khăn
• Trên kiến trúc x86, lệnh adc dùng để xử lý carry chậm hơn lệnh add thông thường, và việc xử lý carry liên tiếp làm hạn chế thực thi song song
• Dùng biểu diễn radix 2^51 có thể trì hoãn lan truyền carry để thực hiện nhiều phép cộng nhanh hơn
• Chỉ phân bổ 51 hoặc 52 bit cho mỗi limb (giá trị thành phần), và dùng phần không gian bit cao còn lại làm vùng lưu tạm carry
• Kỹ thuật này dù tốn thêm thanh ghi và chi phí chuyển đổi, trên thực tế vẫn cho hiệu năng tốt hơn cơ số 2^64

---

Cộng và trừ nhanh: vấn đề carry

• Trong phép cộng số nguyên lớn, cũng giống như khi con người xử lý carry theo từng chữ số bằng tay, máy tính cũng khó song song hóa thuật toán cộng vì carry
• Về cơ bản, ta cộng từng phần từ bên phải (hàng thấp) sang, rồi đẩy carry phát sinh ở mỗi hàng sang bên trái (hàng cao)
• Nếu bắt đầu cộng từ bên trái, carry trước đó sẽ ảnh hưởng đến phép toán của hàng tiếp theo, nên không thể song song hóa thứ tự thực hiện

Xử lý carry trong máy tính

• Máy tính xử lý phép cộng theo đơn vị số nguyên 64 bit
• Một số nguyên 256 bit có vẻ như có thể tách thành 4 limb 64 bit để cộng song song, nhưng trên thực tế vẫn phải xử lý overflow (carry) mới tạo ra kết quả đúng
• x86 có lệnh adc (add with carry) tự động xử lý carry

Nguyên nhân suy giảm hiệu năng

• Lệnh adc cần thêm đầu vào là carry flag, nên hiệu năng kém hơn add đơn giản
• Trên kiến trúc Haswell, add có thể chạy song song trên nhiều cổng, trong khi adc gần như buộc phải thực thi tuần tự
• Đặc biệt khi dùng các lệnh SIMD (vpaddq v.v.), phép cộng song song không carry nhanh hơn rất nhiều

Ý tưởng trì hoãn carry (ví dụ trên giấy)

• Để giảm carry, có thể mở rộng phạm vi chữ số (ví dụ: từ 0-9 thành 0-9, A-Z, và * để có tổng cộng 37 ký tự), nhờ đó tạm thời cộng nhiều số mà không cần carry
• Làm vậy cho phép thực hiện nhiều phép cộng mà không phải lan truyền carry, rồi cuối cùng mới dọn carry một lần bằng normalization (chuẩn hóa)
• Khái niệm này tách riêng việc tích lũy carry và lan truyền carry, để chỉ xử lý carry ở bước cuối cùng
• Trong phép toán thực tế, nếu xuất hiện giá trị vượt ngưỡng cơ số của một chữ số, thì carry sẽ được cộng dồn tuần tự từ bên phải

Áp dụng trì hoãn carry trên máy tính (mẹo Radix 2^51)

• Để giảm lan truyền carry trong máy tính, dùng biểu diễn radix 2^51
• Thay vì 256 bit được chia thành 4 limb 64 bit, nó được chia thành 5 limb, mỗi limb 51~52 bit
  • 12~13 bit cao của mỗi limb đóng vai trò vùng lưu tạm carry
• Với cách này, mỗi limb vẫn giữ trong phạm vi giá trị 2^64, nhưng khi tính toán thực tế carry không dễ phát sinh, nên có thể thực hiện nhiều phép toán song song mà không cần carry
• Sau khoảng 2^13 phép toán liên tiếp mới cần normalization (chuẩn hóa) một lần
• Trên CPU Haswell, sau khi áp dụng radix 2^51, chỉ cần thực hiện nhiều phép cộng đơn giản không carry nên hiệu năng cải thiện lớn so với radix 2^64 thông thường
• Carry propagation để normalization chỉ được thực hiện một lần ở cuối

Ví dụ mã

• Chia giá trị vào 5 thanh ghi để có thể cộng mà không cần carry
• Normalization được thực hiện bằng cách lấy các bit cao của mỗi limb, cộng sang limb bên cạnh, rồi lặp lại việc đưa giá trị carry của chính nó về 0

Mở rộng sang phép trừ

• Phép trừ cũng có thể áp dụng theo cách tương tự
• Khi đó carry có thể mang giá trị âm, nên limb được xử lý như signed integer
• Bit cao nhất của limb được dùng làm bit dấu, nên số lượng phép toán có thể xử lý trong một lần sẽ giảm nhẹ so với phép cộng

Kết luận

• Kỹ thuật kháng carry (trì hoãn) dù làm tăng số lượng limb và thêm công đoạn chuyển đổi, vẫn thực sự cải thiện mạnh hiệu năng tổng thể
• Mẹo radix 2^51 được dùng rộng rãi trong các lĩnh vực đòi hỏi hiệu năng cao như phép toán số nguyên lớn, mật mã học
• Đây là một ý tưởng quan trọng để tối ưu hiệu năng thực tế của phần cứng/thuật toán

[GN⁺]

Ý kiến trên Hacker News

• Lúc đầu nhìn thấy con số 2^51, tôi tưởng đây là câu chuyện về việc lưu số nguyên trong kiểu double, nhưng rồi nhận ra giá trị thực sự có thể biểu diễn chính xác một Integer trong double là 2^53-1

• Trên AVX512 (và AVX2 ở một mức độ nào đó), có một môi trường cho phép triển khai phép cộng bổ sung 256-bit khá hiệu quả, với ưu điểm là có thể chứa nhiều số hơn trong thanh ghi
  Ví dụ trực tiếp hoạt động như đoạn mã dưới đây

__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);

Nó còn cho thấy cả thông lượng cũng được cải thiện, nên có thể xem ví dụ mã thực tế tại godbolt.org
Việc mở rộng logic này lên phép cộng 512-bit cũng rất đơn giản

• Đặc biệt, có ý kiến chỉ ra rằng trên một số kiến trúc CPU Intel nhất định, chỉ riêng việc dùng lệnh AVX512 cũng có thể làm giảm xung nhịp toàn bộ bộ xử lý, dẫn đến hiệu năng tổng thể không ổn định hoặc thậm chí chậm hơn
  Có thể xem tham khảo liên quan tại liên kết stackoverflow

• Trước câu hỏi “sao không dùng 12 bit thay vì 13 bit?”, ở đây người ta bỏ qua xử lý carry ở bit cao nhất (limb), để khi tràn thì nó hoạt động theo kiểu wraparound
  Kết quả là limb cao nhất được cấp 52 bit, nên có nhược điểm là nó hết chỗ nhanh hơn các limb khác, nhưng lại hoạt động tương tự phép cộng số nguyên không dấu trong C
  Vậy thì có thể đề xuất cách cấp 64 bit cho limb cao nhất và 48 bit cho bốn limb còn lại
  Làm vậy sẽ cho phép tích lũy nhiều phép toán hơn trước khi chuẩn hóa, đồng thời có lợi thế như căn chỉnh theo word
  Đặc tính xử lý tràn cũng vẫn như cũ

  • Nếu chỉ cấp 64 bit cho limb cao nhất, thì khi cộng các limb của hai số, tràn sẽ xảy ra quá sớm
    Ví dụ nếu cả hai đều có giá trị 2^63 thì sẽ tràn ngay
    Với số học wraparound thì không sao, nhưng trong trường hợp thông thường thì không ổn

  • Với cấu trúc như vậy, sẽ cần 6 word thay vì 5 như trong bài gốc
    Cũng sẽ cần nhiều lệnh hơn

  • Mục tiêu là xử lý toán học 256-bit bằng 5 thanh ghi 64-bit
    Tức là lý tưởng nhất là mỗi word mang 256/5 = 51.2 bit
    Nếu chỉ giới hạn ở 256 bit thì cách này ổn, nhưng không tối ưu cho thư viện big-int đa dụng
    Ngày xưa từng có bối cảnh muốn dùng đúng 1 byte cho mỗi carry, và vào thời chưa có barrel shifter thì người ta thích chỉ dùng 56 trong số 64 bit để dễ căn chỉnh
    Trên RISC-V, do phần cứng không có cờ, những thảo luận kiểu này lại càng quan trọng

• Trên CPU x86 hiện đại (ví dụ: Intel Broadwell, AMD Ryzen), có thể dùng lệnh Intel ADX để còn nhanh hơn ngay cả trong những tình huống mà biểu diễn radix 2^51 vốn mạnh theo truyền thống (ví dụ: Curve25519)

• Tài liệu thảo luận liên quan

  • The radix 2^51 trick (tháng 11 năm 2022)
  • The radix 2^51 trick (2017)

• Bài học cốt lõi là, nếu các phép toán độc lập với nhau, thì việc chạy được nhiều phép toán song song hơn đôi khi lại nhanh hơn
  Ngược lại, nếu vì phụ thuộc mà buộc phải chạy tuần tự, thì dù số phép toán ít hơn cũng có thể chậm hơn
  Ý tưởng này không chỉ áp dụng cho số nguyên dài mà còn có thể áp dụng ở nhiều lĩnh vực khác

  • Có đề xuất chia thành các khối 64-bit, rồi dự tính trước và chạy song song hai trường hợp tùy theo có carry hay không, sau đó chọn phép tính đúng theo kết quả carry thực tế
    Cách này làm số phép cộng tăng gấp đôi, nhưng tốc độ lan truyền tăng lên mức log(bits) thay vì tuyến tính

  • Điều tôi từng chưa hiểu rõ ở kỹ thuật này là, về bản chất nó biến việc ripple carry phải chạy N-1 lần khi cộng N giá trị thành chỉ chạy một lần
    Việc xử lý carry tự nó phức tạp hơn, nhưng phép cộng thì có thể song song hóa
    Tuy nhiên, để hiệu quả tổng thể có ý nghĩa, bản thân việc chia số đầu vào thành các đơn vị 5 thanh ghi cũng phải được song song hóa

  • Quy tắc này còn có thể mở rộng đến mức siêu máy tính hoặc đám mây với hàng chục nghìn node
    Nếu dùng được nhiều lõi, overhead có thể xem như không đáng kể

  • Ý tưởng này cũng được NVidia quan tâm và đang cho kết quả tốt ở nhiều lĩnh vực

• Dù hướng dẫn của HN nói không nên thêm ý kiến vào tiêu đề, tôi không thích những tiêu đề giật gân, phóng đại quá mức
  Tôi nghĩ nên giới hạn nó thành kiểu “mẹo radix 2^51 cho phép cộng song song số nguyên 64-bit không phụ thuộc carry trên một số kiến trúc x86” thì chính xác hơn

• Tôi tiếc là giá như đọc được bài này sớm hơn vài tháng thì đã hữu ích
  Tôi từng gặp trường hợp khi mã hóa/giải mã buffer sang một cơ số tùy ý, carry lan ra toàn bộ buffer khiến thuật toán chậm đi rất nhiều
  Cuối cùng tôi đã để lại “khoảng trống” và chia thành các chunk để xử lý carry, có vẻ khá giống với mẹo này
  Trên thực tế, tôi chọn cách lãng phí một số bit để tiết kiệm lượng tính toán hoặc băng thông mạng
  Tôi tự hỏi liệu việc xử lý carry như thế này cũng có thể được gom lại làm hậu xử lý hay không
  Hy vọng là có thể đạt được một cấu trúc gần như lấy hết mọi lợi ích

• Kinh nghiệm chỉ dùng môi trường x86_64 khiến tôi thấy ví dụ này cho thấy rất rõ rằng việc RISC-V không có carry flag cũng không hẳn là một lựa chọn sai

  • Ngoài cách này ra, còn có mô tả về phương pháp vẫn giữ các limb 64-bit nhưng thực hiện phép cộng an toàn với carry hoàn toàn bằng các biến uint64_t
    Luồng xử lý như dưới đây

  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:
  

  Điểm mấu chốt là khi kết quả cộng (limb) không phải toàn bit 1, thì carry out của limb đó không phụ thuộc vào carry in mà chỉ phụ thuộc vào kết quả sau khi cộng giá trị gốc
  Ngược lại, nếu giá trị là toàn bit 1 thì carry out = carry in
  Nếu cấu trúc nhánh hầu như không cần dự đoán, thì có thể thực thi song song hoàn toàn
  Xác suất bị chậm chỉ là 1 trên 2^64, nhưng trên máy 4-wide thì không có lợi ích lớn
  Trên máy 8-wide hoặc cấu trúc 8 limb thì có thể mang lại cải thiện hiệu năng đáng kể
  Không hợp với x86_64, nhưng trên các máy 8-wide như dòng Apple M* thì có khả năng áp dụng
  Có thể kỳ vọng vào tương lai trên bộ xử lý RISC-V Ascalon 8-wide của Tenstorrent, Ventana, Rivos, XiangShan v.v.
  Hiệu quả được khuếch đại tối đa trên kiến trúc SIMD hoặc kiến trúc có lệnh shift/slideup 1-lane nhanh

  • Carry-save addition không phải lúc nào cũng vượt trội hơn add-with-carry
    Hai loại thuật toán cộng nhiều word này không thể thay thế lẫn nhau, mỗi loại đều có ưu và nhược điểm riêng
    Vì vậy lệnh ADC/SBB nên được đưa vào ISA theo mặc định, và cũng có thể lưu cờ theo kiểu thanh ghi
    Điểm yếu nghiêm trọng hơn của RISC-V là không có integer overflow flag
    Khi cần đường vòng bằng phần mềm để phát hiện overflow, mức giảm hiệu năng còn lớn hơn nhiều so với việc vòng qua carry bit

  • Việc RISC-V không có carry flag bắt nguồn từ chuyện ngôn ngữ C bỏ qua carry flag nhị phân
    Trên thực tế, tần suất tận dụng carry flag là khá thấp

  • Hóa ra không chỉ mình tôi từng nghĩ “nếu carry flag vốn đã chậm thì tại sao lại từng có tranh cãi risc5 gmp?”

• 'Radix trick' cũng có thể áp dụng vào cấu trúc dữ liệu
  Trong sách 'Purely Functional Data Structures' của Okasaki cũng có những ví dụ thú vị