Giải mã thuật toán tính tang của Intel 8087: Khi CORDIC không còn đủ

Năm 1980, Intel giới thiệu chip đồng xử lý toán học 8087, giúp các phép tính dấu phẩy động trên IBM PC và nhiều hệ thống khác nhanh hơn hẳn. Điều đáng chú ý là lệnh tính tang FPTAN của chip này chỉ mất 90 micro giây, so với 13.000 micro giây khi thực hiện trên vi xử lý 8086.

Đằng sau tốc độ đó là một thuật toán lai độc đáo: 8087 kết hợp CORDIC với xấp xỉ đa thức hữu tỷ để vừa đạt độ chính xác cao vừa đảm bảo hiệu năng. Bài viết này sẽ mổ xẻ mạch điện và vi mã của chip để làm rõ cách FPTAN hoạt động.

Sơ đồ đường dữ liệu của 8087 với các khối chức năng dùng cho FPTAN

CORDIC – Thuật toán ra đời từ máy bay ném bom

CORDIC (COordinate Rotation DIgital Computer) là thuật toán thông minh giúp tính nhanh các hàm siêu việt bằng phần cứng đơn giản: chỉ dùng phép dịch bit, cộng trừ và tra bảng, không cần nhân hay chia.

Thuật toán này ra đời năm 1956, khi kỹ sư Jack Volder được giao nhiệm vụ thiết kế máy tính số thay thế máy tính tương tự cho máy bay ném bom B-58 Hustler – chiếc đầu tiên bay được ở tốc độ Mach 2.

Máy bay ném bom Convair B-58A Hustler

Ý tưởng cốt lõi của CORDIC là chia một góc thành chuỗi các góc đặc biệt dạng αₙ = arctan(2⁻ⁿ), nhờ đó phép quay vector trở nên cực kỳ đơn giản trong phần cứng. Mỗi vòng lặp CORDIC cho thêm một bit chính xác, nên thuật toán hội tụ rất nhanh.

Quy trình gồm các bước:

• Phân rã góc đầu vào thành tổng các góc đặc biệt đã lưu sẵn trong bảng
• Áp dụng công thức quay cho từng góc, bắt đầu từ vector đơn vị (1, 0)
• Kết quả thu được điểm (X, Y) tại góc mong muốn, và tang chính là Y/X

Với 16 vòng lặp, CORDIC cho độ chính xác khoảng 2⁻¹⁶, tức 16 bit. Muốn đạt 64 bit thì cần tới 64 vòng lặp – quá chậm.

Bước đột phá: Kết hợp CORDIC với xấp xỉ Padé

Thay vì chạy đủ 64 vòng CORDIC, 8087 chỉ dùng 16 bit CORDIC rồi chuyển sang thuật toán khác cho phần góc còn lại. Góc dư này rất nhỏ (khoảng 2⁻¹⁶), nên chip dùng xấp xỉ Padé – tỷ số của hai đa thức.

Công thức 8087 sử dụng khá đơn giản: 3x/(3 − x²). Dù đơn giản, nó rất chính xác với giá trị nhỏ, với sai số tỷ lệ thuận với x⁴. Đây là xấp xỉ Padé bậc [1,2], có thể suy ra từ khai triển phân số liên tục của hàm tang.

Điểm thú vị: Cách tiếp cận này khác hẳn với chuỗi Taylor truyền thống. Chuỗi Taylor chỉ tốt để xấp xỉ hàm tại một điểm, trong khi xấp xỉ Padé tối ưu cho cả một khoảng – đúng thứ mà phần cứng tính toán cần.

Biểu đồ so sánh các hàm xấp xỉ

Ba nhánh xử lý trong vi mã FPTAN

Vi mã của FPTAN bắt đầu tại địa chỉ #1039 và chia đầu vào thành ba nhánh tùy theo số mũ của đối số:

• Số mũ từ −64 trở xuống: Đối số quá nhỏ, tang gần bằng chính nó. Chip trả về nguyên giá trị gốc kèm mẫu số bằng 1.
• Số mũ từ −17 trở xuống: Bỏ qua CORDIC, nhảy thẳng tới xấp xỉ hữu tỷ.
• Số mũ từ −1 đến −16: Nhánh CORDIC đầy đủ – phần phức tạp và thú vị nhất.

Một đặc điểm kỳ lạ của 8087 là chip đánh dấu ngoại lệ "precision" nếu kết quả không chính xác tuyệt đối. Vì tang chỉ chính xác hoàn hảo tại tan(0), mọi đầu vào khác đều kích hoạt ngoại lệ này.

Phép chia giả CORDIC: Tối ưu đến từng bit

Phần hấp dẫn nhất là vòng lặp chia giả CORDIC (địa chỉ #1061–#1080). Về mặt khái niệm, chip thực hiện 16 bước CORDIC với 16 góc đã lưu. Nhưng vi mã được tối ưu để bỏ qua các góc lớn khi đầu vào nhỏ – bộ đếm vòng lặp được khởi tạo dựa trên số mũ của góc đầu vào.

Các quyết định (dùng hay bỏ qua từng góc) được ghi vào một thanh ghi dịch 16 bit nằm ở rìa phải của chip. Vì thanh ghi này vào ra theo kiểu nối tiếp, nó chỉ cần hai đường tín hiệu thay vì truy cập bus phân số nội bộ – có lẽ đây là chỗ tận dụng khoảng trống trên đế chip.

Điểm đáng chú ý là code dùng số nguyên 64 bit thay vì dấu phẩy động. Điều này khiến việc đọc hiểu trở nên khó khăn, vì các giá trị phải được nhìn như số điểm cố định với số mũ ẩn. Những số mũ này không được lưu ở đâu cả, mà được suy ra từ phân tích thuật toán.

Số mũ ẩn còn thay đổi theo từng bước lặp để bảo toàn độ chính xác. Nếu cố định số mũ, các giá trị sẽ có tới 16 bit 0 ở đầu, lãng phí độ chính xác. Bằng cách dịch trái mỗi chu kỳ, con số luôn tận dụng gần hết 64 bit.

Nói cách khác: phần cứng đang chạy số học nguyên tốc độ cao, nhưng về mặt toán học, ta có thể hình dung nó như số điểm cố định với số mũ không tồn tại thực sự trong chip.

Xấp xỉ đa thức hữu tỷ: Nhân chậm, cộng nhanh

Sau vòng chia giả CORDIC, vi mã tính xấp xỉ Padé. Phần tốn thời gian nhất ở đây là routine SQUARE – bình phương một số điểm cố định bằng thuật toán Booth (radix 4), nhanh gấp đôi phép nhân nhị phân thông thường.

Hằng số 3 không lấy từ ROM hằng số mà đến từ các transistor chuyên dụng đặt hai bit đầu của phần định trị – vốn thường dùng để tạo NaN. Với số mũ ẩn bằng 1, giá trị này tương ứng với 3.

Các phép tính đa thức còn lại chủ yếu dùng phép cộng thay vì nhân. Để tính mẫu số, góc được dịch phải (chia 2) rồi tự cộng với chính nó – tức nhân với 3. Thay vì chia tử cho mẫu (rất tốn kém), chip dùng trực tiếp tử và mẫu làm giá trị Y và X khởi tạo cho giai đoạn CORDIC tiếp theo.

Nhân giả CORDIC: Quay ngược để bảo toàn độ chính xác

Giai đoạn cuối là vòng lặp CORDIC áp dụng các phép quay lên vector, nhưng theo thứ tự ngược lại so với lúc tính: các phép quay nhỏ nhất được áp dụng trước để giữ độ chính xác. Bit được dịch ra khỏi thanh ghi để quyết định có thực hiện phép quay hay không, và vòng lặp dừng ngay khi thanh ghi toàn số 0 – nghĩa là góc nhỏ chỉ qua vài vòng, không cần đủ 16.

Giá trị X xấp xỉ 3 và gần như không đổi, trong khi Y có thể tăng gấp đôi sau mỗi lần quay. Để tối đa độ chính xác, số mũ của X là 1 còn số mũ của Y bắt đầu từ −14 và tăng 1 mỗi vòng. Chính vì hai thanh ghi có số mũ ẩn khác nhau, các giá trị phải được dịch bit trước khi cộng – và số lượng dịch không hề trực quan chút nào.

Sau cùng, vi mã chuẩn hóa X và Y thành số dấu phẩy động thực thụ rồi đẩy lên stack để hoàn tất lệnh.

Hiệu năng thực tế và di sản

FPTAN chậm hơn hầu hết lệnh khác của 8087 do độ phức tạp. Tài liệu Intel ghi khoảng 450 chu kỳ xung nhịp, dao động từ 30 đến 540 tùy giá trị đầu vào.

Với giá trị 0.95 mà tác giả khảo sát, phân bố thời gian như sau:

• 33% cho phép chia giả CORDIC
• 15% cho xấp xỉ đa thức hữu tỷ (chủ yếu là bình phương)
• 47% cho phép nhân giả CORDIC
• 5% cho phần còn lại

Với Pentium, Intel đã chuyển hẳn từ CORDIC sang xấp xỉ đa thức, vì mạch nhân nhanh của Pentium khiến phương pháp này trở nên thực tế. Ngày nay, các thư viện như MKL (Math Kernel Library) và SVML (Short Vector Math Library) cung cấp các cài đặt tối ưu cho phần cứng Intel, dùng xấp xỉ đa thức kết hợp lệnh song song SIMD thay vì phần cứng chuyên dụng. Các phép toán x87 và số thực 80 bit gần như đã lỗi thời.

Dẫu vậy, thuật toán của 8087 vẫn là một ví dụ tuyệt vời về thiết kế phần cứng thông minh, nơi giới hạn về transistor buộc các kỹ sư phải sáng tạo theo cách mà ngày nay ít ai còn phải làm.