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

 (chosenplaintext.ca)
1 điểm bởi GN⁺ 2025-05-31 | 1 bình luận | Chia sẻ qua WhatsApp
  • Phép cộng số nguyên lớn thường được xử lý bằng cách chia thành các limb 64 bit, nhưng khi phát sinh lan truyền nhớ thì khó tận dụng đầy đủ lợi thế thực thi song song của CPU hiện đại
  • adc của x86 phụ thuộc vào carry flag của phép toán trước đó nên chuỗi lệnh bị tuần tự hóa, trở thành nút thắt ngay cả trên các kiến trúc có thể chạy song song nhiều lệnh add như Intel Haswell
  • Biểu diễn cơ số 2^51 chia giá trị 256 bit thành năm chữ số cơ số 2^51 thay vì bốn chữ số cơ số 2^64, tận dụng các bit cao còn dư của mỗi limb làm không gian lưu trữ nhớ trung gian
  • Cách này không loại bỏ nhớ, mà trì hoãn lan truyền qua nhiều lần cộng rồi xử lý một lần ở bước chuẩn hóa cuối cùng
  • Trong benchmark đơn giản trên Haswell, ngay cả khi tính cả chi phí chuyển đổi thì từ ba phép cộng trở lên đã nhanh hơn cách cơ số 2^64, và lợi thế càng tăng khi số lần lặp nhiều hơn

Vì sao nhớ trở thành nút thắt trong phép cộng số nguyên lớn

  • Phép cộng dài trên giấy thường được thực hiện từ phải sang trái, bắt đầu ở hàng đơn vị
    • Vì kết quả của mỗi chữ số phụ thuộc vào nhớ chuyển sang từ chữ số bên phải
    • Nếu cộng từ trái sang phải thì nhớ phát sinh về sau sẽ buộc phải sửa lại các chữ số phía trước đã tính
  • Phép cộng số nguyên lớn cũng có cùng ràng buộc
    • Nếu chia hai số nguyên 256 bit x và y thành bốn limb 64 bit thì có thể cộng các limb cùng vị trí với nhau
    • Nếu limb thấp bị tràn thì phải chuyển giá trị 1 đó sang limb cao hơn
  • adc của x86 là lệnh dùng để xử lý sự lan truyền này
    • Nó kiểm tra xem phép toán trước có tràn hay không rồi cộng thêm 1 nếu cần
    • Phép cộng 256 bit đúng nghĩa sẽ nối tiếp từ limb thấp nhất theo thứ tự add, adc, adc, adc

Cấu trúc khiến adc chậm trên CPU hiện đại

  • adc nhìn chung tốn chi phí thực thi cao hơn add thường
    • adc dùng carry flag như đầu vào thứ ba nên phức tạp hơn add
    • Nó cũng ít được dùng hơn add, nên nhà thiết kế CPU có ít động lực hơn để dành diện tích chip tối ưu hiệu năng cho adc
  • Vấn đề lớn hơn là phụ thuộc lệnh
    • Trên Intel Haswell, một lệnh add đơn mất 1 chu kỳ để thực thi
    • Trong điều kiện lý tưởng, Haswell có thể thực thi tối đa 4 lệnh add mỗi chu kỳ
    • Haswell có 8 cổng thực thi, trong đó 4 cổng có thể chạy add số nguyên
  • Bốn lệnh add độc lập rất dễ chạy song song
    • Ngược lại, chuỗi adc khiến mỗi lệnh phụ thuộc vào đầu ra carry flag của lệnh trước
    • CPU không thể song song hóa các lệnh này mà phải thực thi tuần tự
  • Với SIMD, tổn thất còn lớn hơn
    • vpaddq thực hiện đồng thời bốn phép cộng 64 bit
    • Haswell có thể chạy hai lệnh vpaddq mỗi chu kỳ
    • Nếu phải từ bỏ tính song song này để xử lý nhớ thì lợi ích hiệu năng sẽ giảm đi

Trì hoãn nhớ qua ví dụ cộng trên giấy

  • Có thể trì hoãn nhớ nếu vẫn giữ giá trị vị trí thập phân nhưng mở rộng tập ký tự được phép xuất hiện ở mỗi vị trí
    • Thay vì chỉ dùng 0-9, ta dùng thêm A-Z và *, tổng cộng 37 ký tự
    • Nhưng bản thân hệ cơ số không phải là cơ số 37, mà vẫn giữ giá trị vị trí thập phân
  • Khi một chữ số vượt quá 9 thì không còn cần nhớ ngay lập tức
    • 29 + 1 có thể viết là 30, nhưng cũng có thể biểu diễn như 2A, 1K, hoặc U
    • Nếu mỗi chữ số của cả hai số đều đã được chuẩn hóa trong phạm vi đến 9 thì có thể hoãn nhớ trong lúc cộng
  • Cách này không phải lúc nào cũng áp dụng được với mọi đầu vào
    • Nếu đã có chữ số lớn sẵn như 9 + W thì vẫn cần nhớ
    • Với các số đã chuẩn hóa, có thể cộng tối đa bốn số mà vẫn biểu diễn được không cần nhớ
  • Cuối cùng vẫn phải chuẩn hóa lại về biểu diễn thập phân thông thường
    • Đi từ phải sang trái để tính xem mỗi chữ số chứa bao nhiêu nhóm 10
    • Trừ đi chừng đó ở chữ số hiện tại và chuyển sang chữ số kế tiếp
  • Điểm cốt lõi không phải là loại bỏ lan truyền nhớ, mà là lưu nó trong quá trình tính trung gian rồi lan truyền một lần ở cuối

Biểu diễn cơ số 2^51 trong máy tính

  • Nếu chia giá trị 256 bit thành bốn limb cơ số 2^64 thì mỗi limb có thể mang giá trị từ 0 đến 2^64−1
    • Đây là cách xem mỗi limb như một chữ số trong cơ số 2^64
  • Vì không thể mở rộng phạm vi số nguyên 64 bit của phần cứng, ta giảm kích thước cơ số
    • Chia giá trị 256 bit thành năm chữ số cơ số 2^51 thay vì bốn chữ số cơ số 2^64
    • Mỗi limb vẫn được lưu trong số nguyên 64 bit, nhưng giá trị thực chỉ dùng 51 hoặc 52 bit
  • Các bit cao còn dư trở thành không gian lưu nhớ trung gian
    • Mỗi limb chứa 51 hoặc 52 bit của số gốc
    • 12 hoặc 13 bit còn lại dùng để chứa phần nhớ phát sinh trong khi tính
  • Kỹ thuật này trong tài liệu mật mã học được gọi là radix 2^51 representation
  • Với các số đã chuẩn hóa, trong không gian 2^64 giá trị limb có thể có thì không cần lo 13 bit cao bị tràn cho đến khi đã cộng tối đa 2^13 giá trị

Limb cao nhất 52 bit và chuẩn hóa

  • Limb cao nhất được cấp 52 bit
    • Các limb còn lại dùng 51 bit
    • Phần nhớ của limb cao nhất bị bỏ qua để giá trị vượt quá 2^256−1 sẽ được xử lý theo kiểu wrap-around
    • Điều này giống cách phép cộng số nguyên unsigned kích thước cố định thông thường trong C sẽ wrap khi tràn
  • Mã cộng cơ số 2^51 không dùng chuỗi adc mà thực thi độc lập năm lệnh add
    • So với cách bốn limb cơ số 2^64, số lệnh add tăng từ 4 lên 5
    • Nhưng đổi lại không còn phụ thuộc carry flag nên có thể chạy song song
  • Ở bước chuẩn hóa, các bit cao của mỗi limb được lấy ra và cộng vào limb cao hơn kế tiếp
    • Dùng shr 51 để trích phần carry
    • Dùng and 0x0007FFFFFFFFFFFF để chỉ giữ lại phần dưới 51 bit
    • Với limb cao nhất thì dùng and 0x000FFFFFFFFFFFFF để dọn lại
  • Chuẩn hóa là bước thực hiện lan truyền nhớ đã trì hoãn ở cuối cùng
    • Trong các phép cộng trung gian không tạo ra phụ thuộc vào carry flag
    • Cuối cùng đưa mỗi limb trở lại đúng phạm vi cho phép

Kết quả hiệu năng và mở rộng sang phép trừ

  • Trong benchmark đơn giản, phép cộng cơ số 2^51 cho kết quả nhanh hơn trên CPU Haswell
    • Tính cả chi phí chuyển sang và quay về từ biểu diễn cơ số 2^51
    • Chỉ với ba phép cộng đã nhanh hơn phép cộng cơ số 2^64
    • Số phép cộng càng nhiều thì mức tiết kiệm càng tăng
  • Cùng ý tưởng này cũng có thể mở rộng sang phép trừ
    • Trong phép trừ, nhớ trở thành carry âm
  • Để hỗ trợ phép trừ, các limb được xem như số nguyên có dấu thay vì unsigned
    • Giá trị ở mỗi chữ số có thể dương hoặc âm
    • Mỗi limb có thể lưu cả carry dương lẫn carry âm
  • Sự thay đổi này có cái giá của nó
    • Bit cao nhất của mỗi limb phải dành làm bit dấu
    • Số phép toán có thể thực hiện giữa hai lần chuẩn hóa giảm từ 2^13 xuống 2^12
  • Ngay cả khi dữ liệu phải trải trên nhiều thanh ghi hơn và số phép toán tăng lên, việc giảm phụ thuộc do nhớ vẫn có thể cải thiện hiệu năng tổng thể

Bài viết liên quan

1 bình luận

 
GN⁺ 2025-05-31
Ý kiến trên Hacker News

  • Có người thắc mắc liệu có thể để limb cao nhất là 64 bit, còn bốn limb còn lại mỗi limb 48 bit hay không
    Như vậy có thể tích lũy nhiều phép cộng hơn trước khi chuẩn hóa, nếu tập lệnh có tính năng hữu ích thì khi tách và chuẩn hóa cũng có thể tận dụng căn chỉnh theo word, và đặc tính overflow trông cũng giống nhau

    • Nếu một trong các mục tiêu là thực hiện phép toán 256 bit bằng 5 thanh ghi 64 bit, thì tức là dùng 256/5 = 51,2 bit cho mỗi word, nên đây có vẻ là cách bố trí khá lý tưởng
      Với thư viện số nguyên lớn tổng quát thì có thể không tối ưu; trước đây không có barrel shifter để thực hiện dịch bit tùy ý một cách hiệu quả, nên cách dùng 56 bit trong 64 bit và chừa đúng 1 byte cho carry có lẽ đã tốt hơn
      Vì RISC-V không có flag, cuộc thảo luận này khá liên quan
    • Nếu cộng limb cao nhất của hai số đã mã hóa thì overflow xảy ra quá nhanh
      Ví dụ nếu cả hai đều là 2^63 thì tràn ngay; có thể ổn với số học wrapping, nhưng không phù hợp trong trường hợp thông thường
    • Làm vậy sẽ cần 6 word để chứa giá trị 256 bit, chứ không phải 5 word như cách trong bài gốc, nên cũng cần nhiều lệnh cộng hơn

  • AVX512, và ở một mức nào đó cả AVX2, cũng có thể triển khai phép cộng 256 bit khá hiệu quả, đồng thời có lợi thế chứa được nhiều số hơn trong thanh ghi
    Kết hợp _mm256_add_epi64, mask so sánh và mask carry; throughput có vẻ cũng tốt hơn: https://godbolt.org/z/e7zETe8xY
    Chuyển sang phép cộng 512 bit cũng đơn giản, và khi đó mức cải thiện có lẽ còn lớn hơn

  • Trên các CPU x86 đủ mới, chẳng hạn Intel Broadwell hay AMD Ryzen, cũng có thể dùng ADX, và ngày nay có thể còn nhanh hơn ngay cả trong các tình huống như Curve25519, nơi biểu diễn radix 2^51 từng có lợi thế truyền thống
    [1] https://en.wikipedia.org/wiki/Intel_ADX

  • Các bài liên quan gồm những luồng thảo luận cũ về radix 2^51 trick
    The radix 2^51 trick - https://news.ycombinator.com/item?id=33706153 - tháng 11 năm 2022
    The radix 2^51 trick (2017) - https://news.ycombinator.com/item?id=23351007 - tháng 5 năm 2020

  • Điểm cốt lõi là dù số phép toán nhiều hơn, nếu chúng phần lớn độc lập thì có thể chạy song song và nhanh hơn
    Ngược lại, dù số phép toán ít hơn nhưng phải chạy tuần tự vì phụ thuộc dữ liệu thì có thể chậm hơn; ý tưởng này áp dụng rộng hơn rất nhiều so với phép toán số nguyên dài

    • Một cách tiếp cận khác là vẫn dùng các mảnh 64 bit thông thường, nhưng thực thi suy đoán song song mỗi phép cộng ở hai trường hợp có carry và không có carry, rồi chọn kết quả đúng dựa trên carry của phép cộng ở phần thấp hơn
      Số phép cộng tăng gấp đôi, nhưng có thể giảm thời gian lan truyền carry từ tuyến tính xuống log(bits)
    • Phần khó hiểu là kỹ thuật được trình bày ở đây dường như tập trung vào việc khi cộng N giá trị thì ripple carry chỉ xảy ra một lần, thay vì N-1 lần
      Phép toán carry phức tạp hơn, nhưng các phép cộng thực sự có thể được song song hóa
      Tuy nhiên, ngay từ đầu đã phải chia số đầu vào thành các nhóm 5 thanh ghi, nên để có lợi tổng thể thì chẳng phải bước chia đó cũng phải song song hóa được hay sao
    • Nvidia đang đào sâu vào ý tưởng tổng quát đó, và dường như đang có kết quả khá hứa hẹn trong một số lĩnh vực
    • Quy tắc này mở rộng tới cả siêu máy tính đa node hoặc đám mây
      Nếu có thể huy động 10.000 lõi, overhead trở nên không đáng kể

  • Điều này cho thấy rất rõ, với người chỉ làm việc trên x86_64, rằng việc RISC-V bỏ qua carry flag không hẳn là sai

    • Vẫn có thể giữ limb 64 bit mà làm theo cách khác
      Nhận xét then chốt là miễn là tổng ở một vị trí limb cụ thể không phải toàn bit 1, carry đi ra từ vị trí đó không phụ thuộc vào carry đi vào, mà chỉ phụ thuộc vào việc phép cộng ban đầu ở vị trí đó có tạo carry hay không
      Nếu tổng toàn bit 1 thì carry đi ra bằng carry đi vào
      Nếu biểu diễn điều này bằng nhánh có điều kiện gần như luôn được dự đoán là not-taken, thì với giả định nhiều nhánh có điều kiện có thể được dự đoán not-taken trong cùng một chu kỳ xung, từng khối lệnh có thể chạy hoàn toàn song song
      Cứ 2^64 lần thì có một lần chạy rất chậm
      Trên máy 4-wide với số 4 limb thì không có lợi thế so với adc, nhưng trên máy 8-wide với số 8 limb thì lợi ích bắt đầu lớn lên
      Có thể không giúp ích nhiều cho x86_64 hiện tại, nhưng có tiềm năng trên dòng Apple M, nơi M1 cũng là 8-wide, dù việc đi đường vòng có thể khó vì Arm ISA
      Khi RISC-V Ascalon 8-wide của Tenstorrent ra mắt vào cuối năm nay hoặc đầu năm 2026, ta có thể kiểm chứng thực tế cùng với Ventana, Rivos, XiangShan, v.v.
      Nếu có shift 1-lane nhanh thì cách này cũng hoạt động tốt hơn trên SIMD rộng; trong RISC-V nó được gọi là slideup
    • Vẫn còn nhiều trường hợp phổ biến mà carry-save addition kém hơn add-with-carry
      Hai thuật toán cộng nhiều word này không thể thay thế cho nhau và có mục đích khác nhau, nên một ISA tử tế sẽ có lệnh ADC/SBB, mà chi phí bổ sung cũng rất nhỏ
      Cũng không nhất thiết cần thanh ghi flag chuyên dụng; một số ISA lưu flag carry/borrow vào thanh ghi đa dụng khi cần
      Việc RISC-V không có carry không phải đặc điểm tệ nhất; tệ hơn là không có integer overflow flag
      Với các chương trình tự nhận là được viết an toàn, phát hiện overflow số nguyên là bắt buộc; nếu đi vòng bằng phần mềm thì hiệu năng có thể đạt được sẽ thấp hơn nhiều so với việc đi vòng cho thiếu carry
    • Dòng chảy này rốt cuộc bắt nguồn từ việc C bỏ qua carry flag, và trong thực tế nó gần như không còn được dùng cho mục đích carry nữa
    • Nếu carry flag dù sao cũng chậm, thì tôi không phải người duy nhất nghĩ rằng “tranh cãi RISC-V GMP rốt cuộc là gì vậy?”

  • Radix trick này cũng áp dụng cho cấu trúc dữ liệu
    Có ví dụ hay trong cuốn 『Purely Functional Data Structures』 của Okasaki

  • Giá mà tôi đọc được bài này vài tháng trước
    Tôi đã cố mã hóa/giải mã buffer theo một cơ số tùy ý, rồi quá muộn mới đi đến kết luận rằng carry có thể lan tới cuối buffer và vì thế làm thuật toán chậm đi rất nhiều
    Cuối cùng lời giải cũng có điểm tương tự trick này: chia buffer thành các chunk và chừa khoảng trống để xử lý carry
    Không hoàn toàn giống; tôi để lại một ít bit lãng phí, dùng thêm chút ít dung lượng lưu trữ hoặc băng thông mạng để đổi lấy việc giảm tính toán
    Không biết liệu bằng cách gom carry như vậy rồi xử lý ở giai đoạn sau có thể được cả đôi đường hay không, nhưng có lẽ chỉ là mong muốn

  • Tôi biết theo hướng dẫn của HN thì không nên sửa tiêu đề, nhưng tôi không thích những tiêu đề câu view thổi phồng một luận điểm nhỏ thành quá rộng
    Tiêu đề bài này đáng ra nên là “radix 2^51 trick để cộng song song các số nguyên 64 bit trên một số kiến trúc x86 mà không làm chậm pipeline vì phụ thuộc carry”