Intel 8087 のタンジェントアルゴリズムのリバースエンジニアリング：CORDIC だけではない

ヴィンテージ Intel 8087 のタンジェントアルゴリズムのリバースエンジニアリング：CORDIC だけではない Intel の浮動小数点チップに関する記事にまだ飽きていないことを願っています。1980 年に Intel は 8087 を発表し、IBM PC やその他のシステムで浮動小数点演算を大幅に高速化しました。この記事では、チップのタンジェント命令の背後にあるアルゴリズムを見ていきます。三角関数の一つの一般的なアプローチは CORDIC と呼ばれるアルゴリズムです。別のアプローチは多項式近似です。8087 はこの 2 つを組み合わせて、高い精度と高いパフォーマンスの両方を達成しました。8087 は 8086 マイクロプロセッサと比較して、タンジェントを 13,000 マイクロ秒ではなく 90 マイクロ秒で計算するという、途方もない高速化を実現しました。2 8087 の回路とマイクロコードを調べることで、FPTAN と呼ばれるタンジェント命令の背後にあるアルゴリズムを説明できます。8087 の回路を探求するために、私はチップの蓋をノミでこじ開け、顕微鏡で高解像度の画像を作成しました。マイクロコード ROM は、ダイの中央にある大きな長方形の領域で、チップを制御する 1648 個のマイクロ命令を保持しています。チップの下半分（赤い箱）はデータパスで、80 ビット値に対して浮動小数点計算を実行する回路です。3 FPTAN によって使用される機能ブロックを示す 8087 のデータパスのクローズアップ。この画像（または他の画像）をクリックすると、より大きなバージョンが表示されます。データパスを拡大すると、関連する機能ユニットが表示されます。指数 ROM には、アルゴリズムが必要とする固定指数値が格納されています。定数 ROM には、CORDIC アルゴリズムで使用される定数を含む定数が格納されています。シフターは大きなコンポーネントであり、64 ビット値を任意の量だけ左または右にシフトします。加算器は 8087 の計算の中心であり、加算と減算を提供するだけでなく、乗算、除算、平方根のためのループでも使用されます。B レジスタは加算器の片方の入力を保持し、複数のソースがもう一方の入力を提供できます。合計レジスタは加算器の出力を保持します。8 つのスタックレジスタと一時レジスタは浮動小数点数を保持します。最後に、シフトレジスタは CORDIC 計算のための 16 ビットステータスを保持します。 CORDIC アルゴリズム CORDIC は、単純なハードウェアで超越関数を高速に計算するための巧妙なアルゴリズムです。シフトおよび加算命令とテーブル検索を使用しますが、乗算や除算は必要ありません。このアルゴリズムは 1956 年にまで遡り、マッハ 2 で飛行できる最初の爆撃機である B-58 ハスラーのために開発されました。航空機にはアナログナビゲーションコンピューターがありましたが、アナログコンポーネントは限られた精度しか提供しませんでした。エンジニアの Jack Volder は、アナログコンピューターを置き換えるデジタルコンピューターを設計する任務を与えられました。7 1 つの重要な問題は、アナログコンピューターがレゾルバと呼ばれる電気機械デバイスでサインとコサインを簡単に生成できることでした。しかし、三角関数をデジタルで生成するのは困難であり、特に当時の遅いトランジスタでは困難でした。テキサス州サンアントニオに展示されている Convair B-58A ハスラー（詳細）。Jack Volder は、単純なハードウェアで三角関数を計算する高速な方法を考案しました。彼はこのアルゴリズムとそれを実装したコンピューターを CORDIC、「COordinate Rotation DIgital Computer」と名付けました。CORDIC は角度をベクトルに変換し、ベクトルの座標が必要な三角関数を提供します。このトリックは、角度を特別な角度のシーケンスに分解することです。これらの特別な角度は事前に計算されてテーブルに格納されているため、CORDIC 計算は 1950 年代のハードウェアでも高速に実行できます。各 CORDIC イテレーションは追加のビット精度を提供するので、アルゴリズムは急速に収束します。CORDIC は科学計算機などでも人気があり、バイナリではなく 10 進 CORDIC が使用されました。 いくつかの三角法 数学は最小限に抑えようとしますが、このセクションでは CORDIC がどのように機能するかを簡単に説明します。下の図は、三角関数が点の座標とどのように関連しているかをレビューしています。角度 θ があると仮定します。それは単位円上の点 (X, Y) を指定します。基本的な公式は X=cos θ、Y=sin θ、Y/X = tan θ です。したがって、座標 (X, Y) を決定できれば、三角関数の値を決定できます。点が単位円上にない場合、例えば (X', Y') の場合でも、tan θ を簡単に決定できます。（ネタバレ：8087 はこれを行います。）しかし、sin θ と cos θ は複雑になります。4 角度、X および Y 座標、三角関数の関係。コンピュータグラフィックスを行ったことがあるなら、回転行列がどのようにして点を角度で回転させることができるかを見たことがあるでしょう。（回転行列に慣れていない場合は、ここで読むか、単にそれが機能すると信頼してください。）点 (X, Y) を回転行列で乗算すると、下の式 (1) の新しい点 (X', Y') が得られます。点に回転行列を使用して点を回転させることができます。残念ながら、回転行列 (1) は sin と cos を必要とするため、問題の解決に役立つようには見えません。しかし、行列を cos θ で割ることができます。これは、行列 (2) が tan を必要とするため、さらに役立たないように見えます。これはまさに私たちが評価したいものです。（さらに、ベクトルの長さが増加します。）しかし、CORDIC の鍵は、αn = arctan(2-n) という特別な角度を使用することです。これらの特別な角度のいずれかを行列に代入すると、ハードウェアで評価しやすい行列 (3) が得られます。2 の累乗で乗算することは、ビットをシフトすることで実行できます。回転行列の単純化。行列 (3) を点 (X,Y) に適用すると、方程式 (4) が得られます。これらは CORDIC プロセスの主要な方程式です。重要なのは、これらの方程式は機械言語またはハードウェアで高速かつ簡単に計算できることで、唯一の操作は加算、減算、およびバイナリシフトであることです。その背景知識があれば、CORDIC がどのように機能するかを見ることができます。まず、目的の入力角度を、目的の角度に合計される特別な角度の組み合わせに分解します。5 次に、単位ベクトル (1, 0) から始めて、各特別な角度に対して上記の回転式を適用します。結果は目的の角度にある点 (X, Y) となり、目的のタンジェントは単純に Y/X になります。6 特別な角度のテーブルは事前に計算されているため、arctan 操作はプロセスを遅くしません。余談ですが、最初の数項の後、特別な角度は 2-n に近づくため、各ステップで約 2 倍になります。要約すると、CORDIC アルゴリズムは、格納された角度のテーブルをループすることから構成されます。格納された角度が目的の角度よりも小さい場合、格納された角度が目的の角度から減算されて新しい目的の角度が得られ、上記の方程式（シフト、加算、減算）が適用されて新しいベクトルが得られます。最後に、元の角度のタンジェントは Y/X によって与えられます。 有理多項式近似 CORDIC の精度は、使用される項の数に依存します。16 項の場合、精度は約 2-16、つまり 16 ビットの精度です。64 ビットの精度を得るには、64 項（および 64 個の特別な角度のテーブル）を計算する必要があります。より速く結果を得るために、8087 は 16 ビットの CORDIC を使用し、残りの角度には別のアルゴリズムを使用します。（残りの角度は、CORDIC の特別な角度の合計と目的の角度との間のギャップであり、非常に小さく、約 2-16 です。）残りの角度に対して、8087 は 2 つの多項式の比である Padé 近似を使用します。多項式の次数によって、Padé 近似のファミリー全体があります。8087 は単純な公式を使用します：3x/(3-x2)。8 この近似は単純ですが、小さな値に対しては非常に正確です。その誤差は x4 に比例します。x < 2-16 なので、誤差は 2-64 未満になり、8087 の 64 ビット精度要件を満たします。さらに、8087 は有理多項式で除算を実行する必要はありません。なぜなら FPTAN は個別の分子と分母を返すからです。したがって、除算は「無料」です。タンジェント関数（赤）、有理近似（青）、テイラー級数（緑）。免責事項：テイラー級数はそれほど悪くはありません