Giải mã thuật toán tang trên Intel 8087: Không chỉ dừng lại ở CORDIC

Hy vọng bạn chưa chán ngấy con chip 8087, vì tôi lại có thêm một bài viết nữa về chip dấu phẩy động của Intel.1 Năm 1980, Intel giới thiệu 8087, giúp các phép toán dấu phẩy động nhanh hơn đáng kể trên IBM PC và các hệ thống khác. Trong bài viết này, tôi sẽ xem xét thuật toán đằng sau lệnh tính tang của con chip. Một phương pháp phổ biến cho các hàm lượng giác là thuật toán có tên CORDIC. Một phương pháp khác là xấp xỉ đa thức. 8087 kết hợp cả hai để đạt được cả độ chính xác cao và hiệu suất cao. 8087 mang lại tốc độ vượt trội so với bộ vi xử lý 8086, tính toán tang trong 90 micro giây thay vì 13.000 micro giây.2

Bằng cách kiểm tra mạch và vi mã của 8087, tôi có thể giải thích thuật toán đằng sau lệnh tính tang, gọi là FPTAN. Để khám phá mạch của 8087, tôi đã cạy nắp chip bằng đục và tạo ra hình ảnh độ phân giải cao bằng kính hiển vi. ROM vi mã là vùng hình chữ nhật lớn ở trung tâm của die, chứa 1648 vi lệnh điều khiển con chip. Nửa dưới của chip (khung màu đỏ) là datapath, mạch thực hiện các phép tính dấu phẩy động trên các giá trị 80-bit.3

Cận cảnh datapath của 8087, hiển thị các khối chức năng được FPTAN sử dụng. Nhấp vào hình ảnh này (hoặc bất kỳ hình ảnh nào khác) để xem phiên bản lớn hơn.

Phóng to datapath cho thấy các đơn vị chức năng liên quan. ROM số mũ chứa các giá trị số mũ cố định mà các thuật toán cần. ROM hằng số chứa các hằng số, bao gồm cả các hằng số được thuật toán CORDIC sử dụng. Bộ dịch bit (shifter) là một thành phần lớn; nó dịch một giá trị 64-bit sang trái hoặc phải theo các lượng tùy ý. Bộ cộng là trái tim trong các phép tính của 8087; ngoài việc cung cấp phép cộng và trừ, nó còn được sử dụng trong một vòng lặp cho phép nhân, chia và căn bậc hai. Thanh ghi B giữ một đầu vào cho bộ cộng, trong khi nhiều nguồn có thể cung cấp đầu vào còn lại. Thanh ghi tổng giữ đầu ra của bộ cộng. Tám thanh ghi ngăn xếp và các thanh ghi tạm thời giữ các số dấu phẩy động. Cuối cùng, thanh ghi dịch giữ 16 bit trạng thái cho các phép tính CORDIC.

CORDIC là một thuật toán thông minh để tính nhanh các hàm siêu việt với phần cứng đơn giản: nó sử dụng các lệnh dịch và cộng cùng với tra bảng, nhưng không cần phép nhân hoặc chia. Thuật toán này có từ năm 1956, khi nó được phát triển cho B-58 Hustler, máy bay ném bom đầu tiên có khả năng bay ở tốc độ Mach 2. Máy bay này có một máy tính dẫn đường analog, nhưng các thành phần analog cung cấp độ chính xác hạn chế. Kỹ sư Jack Volder được giao nhiệm vụ thiết kế một máy tính kỹ thuật số để thay thế máy tính analog.7 Một vấn đề chính là máy tính analog có thể dễ dàng tạo ra sin và cos bằng một thiết bị cơ điện gọi là resolver. Nhưng các hàm lượng giác rất khó tạo ra bằng kỹ thuật số, đặc biệt là với các bóng bán dẫn chậm thời bấy giờ.

Một chiếc Convair B-58A Hustler, đang được trưng bày tại San Antonio, TX (chi tiết).

Jack Volder đã nghĩ ra một cách nhanh chóng để tính toán các hàm lượng giác với phần cứng đơn giản. Ông gọi thuật toán này—và máy tính thực hiện nó—là CORDIC: "COordinate Rotation DIgital Computer" (Máy tính kỹ thuật số xoay tọa độ). CORDIC chuyển đổi một góc thành một vectơ, trong đó tọa độ của vectơ cung cấp các hàm lượng giác cần thiết. Bí quyết là chia nhỏ góc thành một chuỗi các góc đặc biệt, những góc giúp việc xoay vectơ trở nên dễ dàng. Các góc đặc biệt này được tính toán trước và lưu trữ trong bảng, vì vậy phép tính CORDIC có thể được thực hiện nhanh chóng, ngay cả trên phần cứng những năm 1950. Mỗi lần lặp CORDIC cung cấp thêm một bit độ chính xác, vì vậy thuật toán hội tụ nhanh chóng. CORDIC trở nên phổ biến, bao gồm cả trong máy tính khoa học, vốn sử dụng CORDIC thập phân thay vì nhị phân.

Một chút về lượng giác

Tôi sẽ cố gắng giữ phần toán học ở mức tối thiểu, nhưng trong phần này, tôi sẽ giải thích nhanh về cách CORDIC hoạt động. Sơ đồ dưới đây xem xét cách các hàm lượng giác liên quan đến tọa độ của một điểm. Giả sử bạn có một góc θ; nó xác định một điểm (X, Y) trên đường tròn đơn vị. Các công thức cơ bản là X=cos θ, Y=sin θ, và Y/X = tan θ. Do đó, nếu bạn có thể xác định tọa độ (X, Y), thì bạn có thể xác định giá trị của các hàm lượng giác. Nếu điểm không nằm trên đường tròn đơn vị, ví dụ (X', Y'), thì bạn vẫn có thể dễ dàng xác định tan θ. (Bật mí: đây là điều mà 8087 thực hiện.) Tuy nhiên, sin θ và cos θ sẽ trở nên phức tạp.4

Mối quan hệ giữa một góc, tọa độ X và Y, và các hàm lượng giác.

Nếu bạn từng làm đồ họa máy tính, có lẽ bạn đã thấy cách ma trận xoay có thể xoay một điểm theo một góc. (Nếu bạn không quen với ma trận xoay, bạn có thể đọc về chúng tại đây hoặc chỉ cần tin rằng nó hoạt động.) Nhân một điểm (X, Y) với ma trận xoay sẽ cho ra điểm mới (X', Y') như hình dưới đây.

Một điểm có thể được xoay bằng cách sử dụng ma trận xoay.

Thật không may, vì ma trận xoay (1, bên dưới) yêu cầu sin và cos, nên có vẻ như nó không giúp giải quyết vấn đề của chúng ta. Tuy nhiên, chúng ta có thể chia ma trận cho cos θ; điều này có vẻ thậm chí ít hữu ích hơn vì bây giờ ma trận (2) cần tan, chính là thứ chúng ta muốn tính. (Hơn nữa, độ dài của vectơ sẽ tăng lên.) Nhưng chìa khóa của CORDIC là sử dụng các góc đặc biệt, αn = arctan(2-n). Khi chúng ta thay thế một trong những góc đặc biệt này vào ma trận, chúng ta nhận được ma trận (3), rất dễ đánh giá trong phần cứng: nhân với lũy thừa của 2 có thể được thực hiện bằng cách dịch các bit.

Đơn giản hóa ma trận xoay.

Áp dụng ma trận (3) vào điểm (X,Y) cho ta các phương trình (4). Đây là những phương trình quan trọng cho quá trình CORDIC. Điều quan trọng là các phương trình này nhanh và dễ tính toán trong ngôn ngữ máy hoặc phần cứng, vì các thao tác duy nhất là cộng, trừ và dịch nhị phân.

Với nền tảng đó, chúng ta có thể thấy CORDIC hoạt động như thế nào. Đầu tiên, chúng ta chia nhỏ góc đầu vào mong muốn thành một tổ hợp các góc đặc biệt cộng lại bằng góc mong muốn.5 Sau đó, chúng ta áp dụng công thức xoay ở trên cho từng góc đặc biệt, bắt đầu với vectơ đơn vị (1, 0). Kết quả là một điểm (X, Y) tại góc mong muốn, và sau đó tang mong muốn đơn giản là Y/X.6 Vì bảng các góc đặc biệt được tính toán trước, các phép toán arctan không làm chậm quá trình. Ngoài lề, sau vài số hạng đầu tiên, các góc đặc biệt tiến gần đến 2-n, vì vậy chúng thu nhỏ khoảng một hệ số 2 ở mỗi bước.

Tóm lại, thuật toán CORDIC bao gồm việc lặp qua một bảng các góc được lưu trữ. Nếu góc được lưu trữ nhỏ hơn góc mong muốn, góc được lưu trữ sẽ được trừ khỏi góc mong muốn để tạo ra một góc mong muốn mới và các phương trình ở trên (dịch, cộng và trừ) được áp dụng để tạo ra một vectơ mới. Cuối cùng, tang của góc ban đầu được đưa ra bởi Y/X.

Xấp xỉ đa thức hữu tỉ

Độ chính xác của CORDIC phụ thuộc vào số lượng các số hạng được sử dụng. Với 16 số hạng, độ chính xác đạt khoảng 2-16, hay 16 bit độ chính xác. Để đạt được 64 bit độ chính xác, cần tính toán 64 số hạng (và một bảng gồm 64 góc đặc biệt). Để có kết quả nhanh hơn, 8087 sử dụng 16 bit của CORDIC và dùng một thuật toán khác cho phần góc còn lại. (Góc còn lại là khoảng chênh lệch giữa tổng các góc CORDIC đặc biệt và góc mong muốn, vì vậy nó rất nhỏ, khoảng 2-16.)

Đối với phần góc còn lại, 8087 sử dụng xấp xỉ Padé, là tỷ số của hai đa thức. Có cả một họ các xấp xỉ Padé, tùy thuộc vào bậc của đa thức. 8087 sử dụng một công thức đơn giản: 3x/(3-x2). Mặc dù công thức xấp xỉ này đơn giản, nhưng nó rất chính xác đối với các giá trị nhỏ; sai số của nó tỷ lệ thuận với x4. Vì x<2-16, sai số sẽ nhỏ hơn 2-64, đáp ứng yêu cầu độ chính xác 64-bit cho 8087. Hơn nữa, 8087 không cần thực hiện phép chia trong đa thức hữu tỷ vì FPTAN trả về tử số và mẫu số riêng biệt. Do đó, phép chia này là "miễn phí".

Hàm tang (đỏ), xấp xỉ hữu tỷ (xanh dương) và chuỗi Taylor (xanh lá). Lưu ý: Chuỗi Taylor không tệ như vẻ ngoài của nó, vì phạm vi liên quan rất gần với 0. Đồ thị được tạo bằng Desmos.

Nếu bạn đã học giải tích, bạn có thể nghĩ rằng đa thức chuỗi Taylor là cách tốt nhất, nhưng tỷ số của hai đa thức lại hiệu quả hơn. (Một lý do là hàm tang tiến tới vô cùng tại π/2. Đa thức sẽ không tiến tới vô cùng, nhưng tỷ số của các đa thức thì có thể, vì vậy nó phù hợp với hàm tang hơn.) Đồ thị trên so sánh hàm tang (đỏ), xấp xỉ hữu tỷ (xanh dương) và chuỗi Taylor bậc ba (xanh lá).

Tổng hợp các thành phần: thuật toán 8087

Thuật toán tang của 8087 có ba phần: xác định các bit quyết định CORDIC (gọi là giả chia), tính toán xấp xỉ hữu tỷ và áp dụng các phương trình xoay dựa trên các bit quyết định CORDIC (gọi là giả nhân).

Chi tiết hơn, bước đầu tiên xác định các góc đặc biệt nào cần cộng vào để xấp xỉ góc đầu vào. Mỗi góc đặc biệt được so sánh với góc đầu vào còn lại và được trừ đi nếu nó nhỏ hơn. Nếu góc được trừ đi, một bit 1 sẽ được ghi lại; ngược lại, bit 0 sẽ được ghi lại. Vì quá trình này tương tự như cách phép chia dài trừ (hoặc không trừ) các phiên bản dịch chuyển liên tiếp của số chia, tạo ra các bit 1 hoặc 0 cho thương số, nên quá trình này được gọi là giả chia. Lưu ý rằng các phép xoay không được áp dụng trong bước này. Thay vào đó, bước này quyết định các phép xoay nào sẽ được áp dụng sau đó.

Sơ đồ dưới đây cho thấy quá trình này được áp dụng cho góc đầu vào 0,95 radian. Quá trình tạo ra chuỗi bit [1,0,0,1,0,1,0,1,0,0,1,0,0,1,1,1], trong đó bit ngoài cùng bên trái biểu thị arctan(20) và cứ tiếp tục như vậy. Góc được giảm khoảng một nửa ở mỗi bước, vì vậy góc dư còn lại là rất nhỏ.

Trong giai đoạn đầu của thuật toán CORDIC—giả chia—góc đầu vào được giảm bớt bởi các góc đặc biệt, để lại một góc dư ở cuối. ("rad" là radian, không phải đơn vị bức xạ.)

Tiếp theo, tang của góc còn lại được tính bằng hàm xấp xỉ hữu tỷ, 3x/(3-x2). Kết quả được sử dụng làm vectơ ban đầu cho bước tiếp theo. Phép chia không được thực hiện ở đây; thay vào đó, tử số trở thành Y trong vectơ ban đầu và mẫu số trở thành X. Do đó, bước chia tốn kém được tránh khỏi, vì nó xảy ra một cách ngầm định trong kết quả. Phép nhân với 3 rất dễ dàng (dịch trái và cộng), vì vậy thao tác tốn kém duy nhất ở bước này là bình phương góc, đòi hỏi một phép nhân 64-bit đầy đủ.

Bước cuối cùng áp dụng mỗi phép xoay CORDIC nếu bit quyết định tương ứng từ bước đầu tiên là 1. Vì điều này phần nào tương tự như phép nhân nhị phân, vốn cộng số bị nhân ở mỗi bước nếu bit số nhân là 1, nên bước này được gọi là giả nhân. Như đã mô tả trước đó, mỗi phép xoay được tính toán bằng các phép dịch, cộng và trừ, vì vậy mỗi phép xoay đều không tốn kém. Mỗi phép xoay trong bước này tương ứng với một lần giảm góc ở bước đầu tiên. Các phép xoay được áp dụng theo thứ tự ngược lại—phép nhỏ nhất trước—để giảm sai số làm tròn. Để thực hiện điều này, các bit quyết định được lưu trữ trong một thanh ghi dịch 16-bit ở bước đầu tiên và được dịch ra theo thứ tự ngược lại trong bước này.

Trong giai đoạn cuối của thuật toán CORDIC—giả nhân—một vectơ được xoay nhiều lần bằng cách áp dụng các phép dịch và cộng. Vectơ cuối cùng cung cấp giá trị tang.

Sơ đồ trên cho thấy quá trình được áp dụng cho đầu vào 0,95. Vectơ ban đầu (xanh lá) đến từ hàm xấp xỉ hữu tỷ; nó rất gần với (3, 0), nhưng hơi xoay do góc dư nhỏ. Mỗi bước xoay tạo ra một vectơ mới khớp với góc từ bước tương ứng trong phần đầu; tôi hiển thị hai trong số các ma trận xoay. Lưu ý rằng các vectơ phân kỳ khỏi đường tròn—một hệ quả của việc chia mỗi ma trận cho cos θ—nhưng điều này không ảnh hưởng đến giá trị tang.

Chỉ lệnh FPTAN có phần đặc biệt vì nó không trả về giá trị tang trực tiếp. Thay vào đó, nó trả về Tang từng phần: hai giá trị tọa độ (X và Y) có thể được chia cho nhau để tạo ra giá trị tang. Người ta có thể tự hỏi tại sao con chip không thực hiện phép chia tự động. Động lực là vì phép chia thời đó rất chậm, và việc lược bỏ phép chia cho phép tối ưu hóa trong một số trường hợp.

Các chi tiết phần cứng liên quan của 8087

Trong phần này, tôi sẽ giải thích một số tính năng của 8087 quan trọng đối với việc triển khai vi mã (microcode) của FPTAN.

Bài gốc còn tiếp — xem tiếp tại bài gốc ↗