Đã từng có bộ xử lý nào triển khai lệnh căn bậc hai số nguyên không?

 (retrocomputing.stackexchange.com)
1 điểm bởi GN⁺ 2024-04-08 | 1 bình luận | Chia sẻ qua WhatsApp
  • Vấn đề ở đây không phải lệnh sqrt dấu phẩy động phổ biến, mà là liệu đã từng có trường hợp cung cấp căn bậc hai số nguyên dưới dạng lệnh CPU hoặc chức năng phần cứng hay chưa; bộ chia/căn bậc hai của Nintendo DS là trường hợp tương tự nhưng không phải lệnh gốc
  • RTX 2000 Forth CPU của Harris và RTX 2010 chuẩn quân sự được xem là những ví dụ có cung cấp lệnh căn bậc hai nhiều bước; RTX 2000 cho kết quả theo cấu trúc gồm 1 lần setup và 15 lần step
  • Một ví dụ còn sớm hơn là ENIAC: năm 1946, máy này dùng bộ divider/square-rooter để điều khiển bộ tích lũy số nguyên thập phân, thực hiện tối đa 40 phép chia hoặc 3 phép căn bậc hai mỗi giây
  • Căn bậc hai số nguyên đòi hỏi bộ nhân số nguyên nhanh và độ chính xác đủ lớn, nên là gánh nặng với các CPU lịch sử; ngoài ra cũng có cách tách phần ước lượng và lặp để điều chỉnh độ chính xác/tốc độ như frsqrte/frsqrts của ARMv8
  • Phương pháp inverse square root kiểu Quake không còn có ưu thế hiệu năng phổ biến trên phần cứng hiện đại; tra bảng, nội suy, lặp kiểu Halley, hay chia để trị với số cố định đều là các lựa chọn tùy theo môi trường triển khai

Phạm vi câu hỏi và trường hợp Nintendo DS

  • Câu hỏi bàn về việc liệu đã từng có bộ xử lý thực sự triển khai lệnh căn bậc hai số nguyên hay chưa
  • Lệnh square root dấu phẩy động thì rất phổ biến, nhưng tiền đề của câu hỏi là người hỏi chưa từng thấy lệnh square root dành riêng cho số nguyên
  • Nintendo DS có một integer divider/square rooter ánh xạ bộ nhớ
    • Điều này hữu ích cho tính toán 3D vì bộ xử lý ARM không có FPU hay bộ chia phần cứng
    • Tuy vậy, điểm mấu chốt của câu hỏi là đây không phải lệnh bộ xử lý gốc

Harris RTX 2000 và RTX 2010

  • Harris RTX 2000 Forth CPU được nhắc đến như một ví dụ có cung cấp lệnh căn bậc hai nhiều bước
  • Người anh em chuẩn quân sự RTX 2010 cũng cung cấp chức năng cùng họ
  • Tài liệu liên quan được dẫn là Stack Computers: RTX 2000
  • Theo RTX2000 Family Programmer’s Reference Manual, chức năng này gần với căn bậc hai lặp hơn, hoạt động bằng cách chạy 1 lệnh setup và 15 lệnh step để lấy giá trị cuối cùng
  • “A Fast Method for Finding an Integer Square Root” của Ken Lyons cũng được nhắc đến như tài liệu nói về triển khai phần cứng và ví dụ lập trình của dòng RTX2000

Bộ divider/square-rooter của ENIAC

  • ENIAC năm 1946 cũng là một trường hợp phần cứng căn bậc hai số nguyên
  • Theo phần mô tả được trích dẫn, ENIAC dùng 4 bộ tích lũy được điều khiển bởi một bộ nhân đặc biệt để thực hiện tối đa 385 phép nhân mỗi giây
  • 5 bộ tích lũy khác được điều khiển bởi divider/square-rooter unit chuyên dụng để xử lý tối đa 40 phép chia hoặc 3 phép căn bậc hai mỗi giây
  • Các bộ tích lũy của ENIAC hoạt động với số nguyên thập phân

Vì sao căn bậc hai số nguyên khó triển khai

  • Một câu trả lời giải thích rằng cách hiệu quả để tính square root là dùng lặp Newton-Raphson để tìm nghịch đảo căn bậc hai, rồi nhân với giá trị ban đầu
  • Cách này được biết đến với tên “Quake method”, và trên CPU/GPU hiện đại đã được khái quát hóa thành các trường hợp có lệnh ước lượng ban đầu và lệnh lặp
  • Ràng buộc cốt lõi của cách tiếp cận này là cần bộ nhân nhanh
    • Với sqrt dấu phẩy động, cần bộ nhân FP nhanh và FPU vốn có sẵn phần đó
    • Với sqrt số nguyên, cần bộ nhân số nguyên nhanh, nhưng theo giải thích thì trong lịch sử đa số CPU không có phần cứng như vậy
    • Để đạt độ chính xác đủ cao, còn cần một bộ nhân nhanh có bề rộng gấp đôi bề rộng đầu vào
  • Vì yêu cầu độ chính xác không phải lúc nào cũng giống nhau, việc tách ước lượng và lặp như frsqrte và frsqrts cho phép điều chỉnh số lần lặp theo điểm cân bằng giữa tốc độ và độ chính xác mong muốn

Tranh luận về kỹ thuật Quake và triển khai sqrt hiện đại

  • Một câu trả lời khác phản bác rằng nhận định mẹo Quake là hiệu quả nhất đã không còn đúng từ lâu, và chỉ phù hợp trong một số phần cứng nhất định khi cần kết quả float chất lượng thấp
  • Trên chip hiện đại, lệnh sqrt gốc nhanh hơn nhiều và thường chỉ ở mức vài chu kỳ xung nhịp
  • Một cách nhanh hơn được đề xuất là lưu bảng các giá trị cách đều không đồng nhất, lấy nhanh hai giá trị rồi nội suy, sau đó dịch exponent cơ số 2 và nếu cần thì áp dụng một vòng lặp còn tốt hơn Newton-Raphson
  • Các phương pháp kiểu Halley và nhiều phép lặp khác có thể hội tụ nhanh hơn Newton-Raphson, nhưng tốc độ thực tế còn phụ thuộc vào chi phí của từng phép toán
  • Với phạm vi chỉ dành cho số nguyên, ví dụ 2^32, có thể áp dụng cùng ý tưởng bằng số cố định
    • Với phần cứng, một cách đơn giản được đưa ra là chia để trị
    • Mỗi 8 bit được ánh xạ sang bảng 256 giá trị số cố định và tra cứu song song; sau đó thực hiện 3 phép nhân, trong đó 2 phép có thể chạy song song, để thu được giá trị 32 bit rồi cắt ngắn
  • Nghiên cứu tối ưu hóa sqrt vẫn đang tiếp tục, và tài liệu INRIA HAL được nêu như một ví dụ

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-04-08
Ý kiến trên Hacker News

  • AArch64 NEON có lệnh URSQRTE, nên thực ra khá gần với câu hỏi gốc hơn tưởng tượng
    Nếu xem giá trị 32-bit là số nguyên fixed-point với 32 bit phần thập phân, thì miền biểu diễn được chia đều từ 0 đến 1-ε, với ε=2^-32
    URSQRTE tính nghịch đảo căn bậc hai gần đúng, sau đó chia đôi và kẹp kết quả vào khoảng từ 0 đến 1-ε
    Số nguyên fixed-point không phải số nguyên theo nghĩa chặt chẽ, và nghịch đảo căn bậc hai gần đúng cũng không phải căn bậc hai, nhưng vẫn có thể tiến khá gần
    FRSQRTE liên quan là lệnh phổ biến hơn nhiều, cung cấp nghịch đảo căn bậc hai gần đúng cho số dấu phẩy động 32-bit

    • Tôi tò mò không biết loại tác vụ nào mang lại lợi ích đủ lớn để được đưa vào AArch64, dù một lệnh phức tạp như vậy có thể dễ dàng tách thành các lệnh đơn giản hơn

  • Nếu hỏi có làm được trong một chu kỳ clock đơn hay không, thì có thể nếu có một bảng tra cứu cực lớn
    Có vẻ cũng có thể giảm kích thước tùy theo số cổng logic nối tiếp mà bạn có thể chạy trong một chu kỳ clock
    Ví dụ, căn bậc hai nhị phân của 10000 khá giống căn bậc hai của 100, chỉ khác số lượng số 0

    • Lệnh ước lượng nghịch đảo căn bậc hai dấu phẩy động (frsqrte) thường được hiện thực theo kiểu tra bảng như vậy, dùng một phần bit của mantissa và bit thấp nhất của số mũ để lập chỉ mục
      Độ chính xác thường tương đương cỡ bf16 (ARM, RISC-V) hoặc fp16 (x86), nên nếu cần độ chính xác cao hơn thì sau đó sẽ chạy thêm vài vòng lặp Newton-Raphson
    • Khi số bit của đầu vào là n, căn bậc hai số nguyên có thể được tính trong n/2 vòng lặp chỉ với dịch bit và cộng
      Ở mỗi bước, việc có nên bật bit mới trong kết quả n_old hay không được tính bằng n2_new = (n_old + (1 << bit))^2 = n2_old + (n_old << (bit + 1)) + (1 << (bit*2))
      Sau đó so với toán hạng gốc; nếu nhỏ hơn hoặc bằng thì 1) bật bit đó trong kết quả và 2) cập nhật n2_old thành n2_new
      Nếu có tập lệnh vi mã và ALU phù hợp thì có thể làm trong n/2 hoặc thậm chí n chu kỳ clock, và nếu tối ưu hơn nữa thì có thể giảm n xuống chỉ còn chỉ số của bit 1 ngoài cùng bên trái trong toán hạng
    • Có thể là câu hỏi ngớ ngẩn, nhưng bảng tra cứu lớn có thực sự kết thúc trong một chu kỳ clock không?
      Nếu là bảng tra cứu lớn thì hẳn phải lấy từ bộ nhớ, vậy chẳng phải sẽ dính độ trễ của cache và hệ thống phân cấp bộ nhớ sao?
    • Nghe vậy thì có vẻ như bất kỳ thuật toán nào trên đời cũng có thể chạy trong 1 chu kỳ clock
    • Căn bậc hai số nguyên thực ra không tệ đến vậy, vì với bảng tra cứu lớn/nhỏ chỉ cần lưu N^0.5 mục
      Tức là lưu N^2 cho mọi đáp án N
      Với số nguyên 16-bit thì khả thi, 32-bit có lẽ cũng còn có thể, nhưng 64-bit thì không ổn

  • Nếu mở rộng định nghĩa “processor” đến cả thiết bị cơ điện, thì Friden SRQ có thể tính căn bậc hai chỉ bằng cộng và dịch bit, không dùng linh kiện điện tử nào ngoài mô-tơ
    Vì phải tự chỉnh vị trí dấu thập phân bằng tay, nên xét về mặt kỹ thuật cũng có thể xem là phép toán số nguyên
    Video: https://youtu.be/o44a1ao5h8w

  • Chẳng phải có thể dùng dãy 1 + 3 + 5 + ... + 2k + 1 để tìm căn bậc hai số nguyên của bất kỳ số nguyên nào sao?
    Về cơ bản là tìm k của số hạng gần nhất nhưng không vượt quá số của tôi trong dãy đó

    • Bạn có thể giải thích ý tưởng không?
      Theo định nghĩa thì đúng là một thuật toán, nhưng nếu hiện thực ngây thơ thì ngay cả với số 32-bit cũng rất chậm
      Đến mức này thì tìm kiếm nhị phân còn nhanh hơn nhiều
    • Cách tốt hơn có thể là dùng khai triển (x+y)^2=x^2+2xy+y^2 cùng với nhận xét rằng trong bất kỳ cơ số nào, căn bậc hai của số có 2n chữ số nhiều nhất chỉ có n chữ số
      Đây cũng chính là cách thủ công quen thuộc để tính căn bậc hai bằng bút và giấy
      Nếu xử lý theo từng 8 bit thì chỉ cần một bảng tra cứu cho căn bậc hai của số 8-bit
    • Nếu ý là cứ lặp dãy đó tuần tự, thì thời gian chạy sẽ là hàm mũ theo độ dài bit của đầu vào
    • Đây là một trong những dạng công việc điển hình dễ song song hóa đến mức khó xử

  • Tôi thấy đoạn này trong câu trả lời bên dưới khá buồn cười:

    My implementation of square root using binary search, that doesn't depend on a multiplier. Only basic ALU instructions are used. It is vigorously undocumented. I have no idea what I wrote but it seems to work.
    Một lời nhắc hay rằng nếu viết mã quá thông minh thì về sau rất dễ không còn nhớ nó hoạt động như thế nào

  • Phải đọc xuống dưới một chút, nhưng việc đáp án là ENIAC thật sự rất buồn cười

    • Nhiều người nghĩ mọi thứ tồn tại trước khi họ đi học đều nguyên thủy và chỉ vừa đủ chạy được :)
      Chỉ cần đọc thêm chút là thấy ngược lại hoàn toàn
      Phần lớn những ý tưởng thông minh ngày nay thực ra đã có trong các máy tính thập niên 1940–60, và đang được tái sử dụng trên các chip bán dẫn mới
      Ví dụ như pipelining, thực thi ngoài thứ tự, hay đa lõi
      Phần cứng ngày xưa có thể hơi “thô”, nhưng kiến trúc thì chứa đầy các kỹ thuật rất tinh vi

  • 2 ^ (1/2 * Log2(X)) = sqrt(X)
    Nếu biến Log2(x) thành đếm số 0 ở đầu thì có thể lấy được một xấp xỉ rất thô
    Nếu xấp xỉ Log(2) tốt hơn thì cũng có thể đến gần đáp án hơn

  • Nếu chỉ cần một xấp xỉ rất thô chứ không phải đáp án chính xác đến số nguyên gần nhất, thì chỉ cần dịch phải bằng một nửa vị trí của bit 1 đầu tiên
    Gần như mọi processor đều có lệnh dịch bit, và các lệnh như FLO (Find Leading One) hay FFS (Find First Set) dường như cũng phổ biến đến mức khó mà nói là hiếm
    Với một số trường hợp sử dụng, kiểu xấp xỉ cực thô này cũng hữu ích chẳng kém đáp án chính xác
    Ví dụ khi bạn chỉ cần một giá trị khởi đầu đủ tốt cho các vòng lặp Newton-Raphson sau đó
    Tất nhiên, mẹo dịch phải này cũng là điểm khởi đầu ổn cho việc tính căn bậc hai chính xác hơn :P

    • Có phải đây là lúc nhắc đến DOOM không?
      Giờ thì đó đã là một giai thoại internet khá nổi tiếng, với Carmack và con số 32-bit kỳ diệu
    • Một sự thật thú vị là FFS và dạng tổng quát hơn của nó là FNS có trong CUDA: https://docs.nvidia.com/cuda/cuda-math-api/index.html#group_...
      Một intrinsic phần cứng CUDA khác mà cá nhân tôi thích là log2

  • Nếu tôi nhớ không nhầm thì phần lớn, có lẽ là tất cả, DSP fixed-point đều có lệnh căn bậc hai hoặc lệnh hỗ trợ

  • Một bài phân tích toàn diện về thuật toán căn bậc hai có liên quan đôi chút và có thể thú vị với fan 6502: https://github.com/TobyLobster/sqrt_test