Intel 8087 のタンジェントアルゴリズムのリバースエンジニアリング:CORDIC だけではない
Reverse-engineering the Intel 8087's tangent algorithm: more than CORDIC (righto.com)
要約
この記事は、Intel 8087 FPU がタンジェント関数を計算するために使用したアルゴリズムを詳細に解説しています。8087 は、三角関数計算に広く使われる CORDIC アルゴリズムと、より高精度な有理多項式近似を組み合わせることで、当時の他のプロセッサと比較して桁違いの高速性と精度を実現しました。著者はチップの回路とマイクロコードを分析し、このハイブリッドアプローチの仕組みを明らかにしています。
全文翻訳
CORDICアルゴリズム
8087に関する記事はまだ続きます。Intelは1980年に8087を導入し、IBM PCなどのシステムで浮動小数点演算を大幅に高速化しました。この記事では、チップのタンジェント命令の背後にあるアルゴリズムに焦点を当てます。三角関数を計算する一般的なアプローチの一つにCORDICアルゴリズムがあります。もう一つのアプローチは多項式近似です。8087はこれら二つを組み合わせて、高い精度と高いパフォーマンスを両立させました。8087は、8086マイクロプロセッサと比較して、タンジェント計算を90マイクロ秒で完了させ、13,000マイクロ秒かかっていたものを劇的に高速化しました。
8087の回路とマイクロコードを調べることで、FPTANというタンジェント命令の背後にあるアルゴリズムを説明できます。8087の回路を調査するために、チップの蓋をノミでこじ開け、顕微鏡で高解像度の画像を作成しました。マイクロコードROMは、チップの中央にある大きな長方形の領域で、チップを制御する1648個のマイクロ命令を格納しています。チップの下半分(赤い箱)はデータパスであり、80ビット値に対する浮動小数点演算を実行する回路です。
[画像: 8087のデータパスのクローズアップ。FPTANが使用する機能ブロックを示しています。この画像(または他の画像)をクリックすると、より大きなバージョンが表示されます。]
8087のデータパスのクローズアップ。FPTANが使用する機能ブロックを示しています。この画像(または他の画像)をクリックすると、より大きなバージョンが表示されます。
データパスを拡大すると、関連する機能ユニットが見えます。指数ROMは、アルゴリズムが必要とする固定指数値を保持します。定数ROMは、CORDICアルゴリズムで使用される定数を含む定数を保持します。シフターは大きなコンポーネントで、64ビット値を任意の量だけ左または右にシフトします。加算器は8087の演算の中心であり、加算と減算を提供するだけでなく、乗算、除算、平方根のためのループでも使用されます。Bレジスタは加算器の一方の入力を保持し、複数のソースがもう一方の入力を提供できます。合計レジスタは加算器の出力を保持します。8つのスタックレジスタと一時レジスタは浮動小数点数を保持します。最後に、シフトレジスタはCORDIC計算のための16ビットステータスビットを保持します。
CORDICは、シフトと加算命令、およびテーブル参照を使用する、単純なハードウェアで超越関数を高速に計算するための巧妙なアルゴリズムです。乗算や除算は必要ありません。このアルゴリズムは1956年に遡り、マッハ2で飛行可能な最初の爆撃機であるB-58ハスラーのために開発されました。航空機にはアナログナビゲーションコンピュータが搭載されていましたが、アナログコンポーネントは精度が限定的でした。エンジニアのジャック・ヴォルダーは、アナログコンピュータを置き換えるデジタルコンピュータの設計を依頼されました。アナログコンピュータは、レゾルバと呼ばれる電気機械装置でサインとコサインを簡単に生成できますが、三角関数をデジタルで生成するのは困難であり、特に当時の遅いトランジスタではそうでした。
[画像: サンアントニオ、テキサス州に展示されているコンベアB-58Aハスラー(詳細)。]
サンアントニオ、テキサス州に展示されているコンベアB-58Aハスラー(詳細)。
ジャック・ヴォルダーは、単純なハードウェアで三角関数を高速に計算する方法を考案しました。彼はそのアルゴリズムとそれを実装したコンピュータをCORDIC(「COordinate Rotation DIgital Computer」)と名付けました。CORDICは角度をベクトルに変換し、ベクトルの座標が必要な三角関数を提供します。そのトリックは、角度を特殊な角度のシーケンスに分解することです。これらの特殊な角度は事前に計算されてテーブルに格納されているため、CORDIC計算は1950年代のハードウェアでも高速に実行できます。各CORDICイテレーションは追加のビット精度を提供するので、アルゴリズムは急速に収束します。CORDICは、科学計算機などで人気を博し、バイナリCORDICではなく10進CORDICが使用されました。
いくつかの三角法
数学は最小限に抑えるようにしますが、このセクションではCORDICの仕組みを簡単に説明します。下の図は、三角関数が点の座標とどのように関連しているかをレビューしています。角度θがあるとします。それは単位円上の点(X, Y)を指定します。基本的な公式はX=cos θ、Y=sin θ、Y/X = tan θです。したがって、座標(X, Y)を決定できれば、三角関数の値を決定できます。点が単位円上にない場合、例えば(X', Y')でも、tan θは簡単に決定できます。(ネタバレ:8087が行うのはこれです。)しかし、sin θとcos θは複雑になります。
角度、XおよびY座標、および三角関数の関係。
コンピュータグラフィックスを扱ったことがあるなら、回転行列を使って点を角度だけ回転させる方法を見たことがあるかもしれません。(回転行列に慣れていない場合は、こちらで読むか、機能すると信じてください。)点(X, Y)を回転行列で乗算すると、新しい点(X', Y')が得られます。
[画像: 点は回転行列を使用して回転させることができます。]
点は回転行列を使用して回転させることができます。
残念ながら、回転行列(1)はsinとcosを必要とするため、問題の解決には役立たないようです。しかし、行列をcos θで割ることができます。これはさらに役立たないように見えます。なぜなら、行列(2)は私たちが評価したいtanを必要とするからです。(さらに、ベクトルの長さは増加します。)しかし、CORDICの鍵は特殊な角度αn = arctan(2^-n)を使用することです。これらの特殊な角度の一つを行列に代入すると、行列(3)が得られます。これはハードウェアで評価が容易です。2のべき乗を掛けることは、ビットをシフトすることで実行できます。
回転行列の単純化。
行列(3)を点(X,Y)に適用すると、方程式(4)が得られます。これらはCORDICプロセスの主要な方程式です。重要なのは、これらの方程式はマシン言語またはハードウェアで高速かつ簡単に計算できることです。なぜなら、唯一の操作は加算、減算、およびバイナリシフトだからです。
その背景を踏まえると、CORDICがどのように機能するかが見えてきます。まず、目的の入力角度を、合計して目的の角度になる特殊な角度の組み合わせに分解します。次に、上記の回転式を各特殊な角度に対して適用し、単位ベクトル(1, 0)から開始します。結果は目的の角度にある点(X, Y)になり、目的のタンジェントは単純にY/Xになります。特殊な角度のテーブルは事前に計算されているため、arctan操作はプロセスを遅くしません。ちなみに、最初の数項の後、特殊な角度は2^-nに近づくため、各ステップで約2倍ずつ縮小します。
要約すると、CORDICアルゴリズムは、格納された角度のテーブルをループすることから構成されます。格納された角度が目的の角度より小さい場合、目的の角度から格納された角度を引いて新しい目的の角度を生成し、上記の方程式(シフト、加算、減算)を適用して新しいベクトルを生成します。最後に、元の角度のタンジェントはY/Xで与えられます。
有理多項式近似
CORDICの精度は使用される項数に依存します。16項を使用すると、精度は約2^-16、つまり16ビットの精度になります。64ビットの精度を得るには、64項(および64個の特殊な角度のテーブル)を計算する必要があります。より速く結果を得るために、8087は16ビットのCORDICを使用し、残りの角度には別のアルゴリズムを使用します。(残りの角度は、特殊なCORDIC角度の合計と目的の角度との差であるため、非常に小さく、約2^-16です。)
残りの角度に対して、8087はパデ近似(Padé approximant)を使用します。これは2つの多項式の比です。多項式の次数によって、パデ近似のファミリー全体があります。8087は単純な式3x/(3-x^2)を使用します。この近似は単純ですが、小さな値に対しては非常に正確です。その誤差はx^4に比例します。x<2^-16なので、誤差は2^-64未満になり、8087の64ビット精度要件を満たします。さらに、8087は有理多項式での除算を実行する必要がありません。なぜなら、FPTANは個別の分子と分母を返すからです。したがって、除算は「無料」です。
[画像: タンジェント関数(赤)、有理近似(青)、およびテイラー級数(緑)。免責事項:テイラー級数は、関連する範囲が0に非常に近いため、それほど悪くはありません。Desmosで生成されたグラフ。]
タンジェント関数(赤)、有理近似(青)、およびテイラー級数(緑)。免責事項:テイラー級数は、関連する範囲が0に非常に近いため、それほど悪くはありません。Desmosで生成されたグラフ。
微積分を学んだことがあるなら、テイラー級数多項式が最善の方法だと思うかもしれませんが、2つの多項式の比の方が優れています。(理由の一つは、タンジェントがπ/2で無限大に発散することです。多項式は発散しませんが、多項式の比は発散する可能性があるため、タンジェント関数によりよく適合します。)上のグラフは、タンジェント関数(赤)、有理近似(青)、および3次テイラー級数(緑)を比較しています。
ピースを組み合わせる:8087アルゴリズム
8087のタンジェントアルゴリズムは3つの部分からなります:CORDIC決定ビットの決定(擬似除算と呼ばれる)、有理近似の計算、およびCORDIC決定ビットに基づく回転式の適用(擬似乗算と呼ばれる)。
詳細には、最初のステップは、入力角度を近似するためにどの特殊な角度を加えるかを決定します。各特殊な角度は、残りの入力角度と比較され、小さい場合は減算されます。角度が減算された場合、1が記録され、そうでなければ0が記録されます。このプロセスは、長除算が除数の連続したシフトバージョンを(減算または減算しない)方法に似ているため、商の1または0を生成するため、擬似除算として知られています。このステップでは回転は適用されません。代わりに、このステップで後で適用する回転が決定されます。
下の図は、入力角度0.95ラジアンに適用されたこのプロセスを示しています。このプロセスは、ビットシーケンス[1,0,0,1,0,1,0,1,0,0,1,0,0,1,1,1]を生成します。ここで、最も左のビットはarctan(2^0)を示し、以下同様です。角度は各ステップで約2倍ずつ減少するため、残りの角度は非常に小さくなります。
[画像: CORDICアルゴリズムの最初のフェーズ—擬似除算—では、入力角度は特殊な角度によって減らされ、最後に残余角度が残ります。(「rad」はラジアンであり、放射線の単位ではありません。)]
CORDICアルゴリズムの最初のフェーズ—擬似除算—では、入力角度は特殊な角度によって減らされ、最後に残余角度が残ります。(「rad」はラジアンであり、放射線単位ではありません。)
次に、残りの角度のタンジェントが有理近似関数3x/(3-x^2)で計算されます。結果は次のステップの初期ベクトルとして使用されます。ここでは除算は実行されません。代わりに、分子が初期ベクトルのYになり、分母がXになります。したがって、高価な除算ステップは、答えの中で暗黙的に発生するため回避されます。3を掛けることは簡単です(左シフトして加算)。したがって、このステップで唯一高価な操作は角度の二乗であり、完全な64ビット乗算が必要です。
最後のステップは、最初のステップからの対応する決定ビットが1の場合に各CORDIC回転を適用します。これは、乗数ビットが1の場合に各ステップで被乗数を加算するバイナリ乗算にいくらか類似しているため、このステップは擬似乗算として知られています。前述のように、各回転はシフト、加算、および減算で計算されるため、各回転は安価です。このステップでの各回転は、最初のステップでの角度減少に対応します。丸め誤差を減らすために、回転は逆順に適用されます—最も小さいものから順に。これを達成するために、決定ビットは最初のステップで16ビットシフトレジスタに格納され、このステップで逆順にシフトアウトされます。
[画像: CORDICアルゴリズムの最後のフェーズ—擬似乗算—では、ベクトルはシフトと加算を適用して複数回回転させられます。最終的なベクトルがタンジェントを提供します。]
CORDICアルゴリズムの最後のフェーズ—擬似乗算—では、ベクトルはシフトと加算を適用して複数回回転させられます。最終的なベクトルがタンジェントを提供します。
上の図は、入力0.95に適用されたプロセスを示しています。初期ベクトル(緑)は有理近似関数から来ており、(3, 0)に非常に近いですが、わずかに回転しています。これは、わずかな残余角度のためです。各回転ステップは、最初の部分の対応するステップの角度に一致する新しいベクトルを生成します。ここでは2つの回転行列を示します。ベクトルは円から離れていくことに注意してください—これは各行列をcos θで割った結果ですが、タンジェントには影響しません。
FPTAN命令は、直接タンジェントを返さないという点でやや奇妙です。代わりに、部分タンジェント(タンジェントを生成するために除算できる2つの座標値(XとY)を返します。なぜチップが自動的に除算を行わなかったのか不思議に思うかもしれません。その動機は、当時除算は遅かったため、除算を省略することで一部のケースで最適化が可能になったことです。
8087の関連ハードウェア詳細
このセクションでは、FPTANのマイクロコード実装にとって重要な8087のいくつかの機能について説明します。
8087はさまざまなデータ型をサポートしていますが、内部的にはすべて「テンポラリリアル」と呼ばれる80ビット浮動小数点数として格納されます。数値は、符号ビット、15ビット指数、および64ビット仮数(小数部)の3つの部分で構成されます。ほとんどの場合、浮動小数点数は符号 × 仮数 × 2指数で表されます。浮動小数点数の利点は、指数によって非常に小さい値から非常に大きい値まで、広範囲をカバーできることです。仮数は、1.bbb…の形式の64ビットバイナリ数です。先頭の1、それに続くバイナリ小数点(10進小数点に相当)、そして残りのビットです。重要な詳細として、指数は「バイアス」である16383が加算されて格納されます。したがって、実際の指数が負であっても、格納される指数は常に正です。例えば、指数1は0x4000として格納され、指数-16は0x3fefとして格納されます。
[画像: 80ビットテンポラリリアルフォーマットとレジスタフォーマット。ドットは10進小数点に類似したバイナリ小数点を示します。]
80ビットテンポラリリアルフォーマットとレジスタフォーマット。ドットは10進小数点に類似したバイナリ小数点を示します。
8087を使用するために、プログラマは8つの内部レジスタに値を格納します。これらはスタックとして編成されています。各レジスタは80ビット浮動小数点数を保持します。パフォーマンスを最適化するために、レジスタスタック内の各値には、「タグ」値(ゼロ、有効、特殊、または空)が関連付けられています。値がゼロの場合はゼロとしてタグ付けされます。「正規」の浮動小数点値は有効としてタグ付けされます。値が無限大、非数(NaN)、または非正規化値の場合、特殊としてタグ付けされます。最後に、空タグはレジスタが値を保持していないことを示します。これにより、スタックアンダーフロー(空のレジスタの読み取り)またはスタックオーバーフロー(空でないレジスタへの格納)を検出できます。
8087には、内部で使用する一時レジスタ(tmpA、tmpB、tmpC)もあります。(これらのレジスタはタンジェント計算で多用されます。)tmpAとtmpBは80ビットレジスタで、2つのタグビットが付いています。しかし、tmpCは異なります。符号、指数、またはタグはありません。さらに、仮数は68ビットです。tmpCには、オーバーフローを防ぐための追加ビットと、丸めのために使用される3つの低位ビット(ガード、ラウンド、スティッキー)があります。
マイクロコードでは、各16ビットマイクロ命令が1つの低レベル操作を実行します。多くの操作は、あるレジスタから別のレジスタへデータを移動します。他の操作は、条件付きジャンプ、サブルーチン呼び出し、およびリターンを提供します。ビットシフト操作は2つのマイクロ命令を必要とします。最初の命令は値をシフターに移動し、シフトの方向と量を設定します。2番目のマイクロ命令(最初の命令から数命令後になる場合がある)は、シフターから宛先へ結果を移動します。
同様に、加算は2つのマイクロ命令を必要とします。最初のマイクロ命令は加算の最初の引数を指定し、キャリーや丸めなどのさまざまなオプションを選択します。(減算の場合、オプションは2番目の引数を補数化します。)2番目の引数は常にBレジスタから取得されます。これは紛らわしいことにtmpBレジスタとは無関係です。2番目のマイクロ命令は、合計レジスタから宛先へ結果を移動します。
タンジェントアルゴリズムのマイクロコード実装
このセクションでは、タンジェントマイクロコードのいくつかのハイライトについて説明します。以下のリストは8087のマイクロコードと私のコメントを示しています。各行は16ビットマイクロ命令を示しています。制御フローは少し複雑なので、脚注にフローチャートを載せました。
FPTAN:
#1039 st(0) -> tmpA 引数をtmpAに格納
#1040 stackPtr-- 結果をプッシュするスタックの空きを確認
#1041 stack overflow? スタックオーバーフロー?
#1042 jmp #1022 if tmp empty/special/overflow/div 不正な引数またはスタックオーバーフローの場合終了
#1043 jmp #1045 if tmpA:tag ZERO is argument 0? 引数が0の場合?
#1044 except:precision 0に対する精度例外
#1045 expconst 0x3ff0 指数 >= -16 かどうかテスト
#1046 adder: tmpA:exp + 0 cin=1 引数指数 + 1
#1047 expConst -> Breg
#1048 adder: sumreg:frac - Breg cin=1 -15 を減算
#1049 jmp #1061 if adder pos 指数 >= -16 ならCORDICへ
#1050 expconst 0x3fff 非CORDICパス:
#1051 tmpA:exp -> Breg 元の指数をチェック
#1052 expConst -> tmpB:frac 指数0と比較
#1053 adder: tmpB:frac - Breg cin=1 減算
#1054 sumreg:frac -> expConv 3fff - exp (つまり、バイアスなしの-exp)
#1055 sumreg:frac -> shiftcount
#1056 jmp #1082 if exponent[6:14] != 0 指数が-64より大きい場合は有理近似へ
#1057 high bit -> tmpB:frac それ以外の場合は元の引数を返す
#1058 expConst -> tmpB:sign,exp X(分母)に1をプッシュ:結果は元の角度
#1059 tmpB -> st(0)
#1060 RNI
#1061 expconst 0x0010 CORDICパス
#1062 sumreg:frac -> loopcounter loopcounter = exp + 16
#1063 tmpA:frac -> tmpC tmpC = 元の角度
#1064 trig const -> Breg/rnd
#1065 adder: tmpC - Breg cin=1, roundmode 最初のCORDIC角度を減算
#1066 adder sign -> cordic, shl ビットをシフトレジスタに保存
#1067 jmp #1079 if not adder pos 加算器が正でない場合はジャンプ
#1068 sumreg:frac,rnd -> tmpC
#1069 adder: tmpA:exp + 0 cin=1 最初の角度が使用された場合、指数をインクリメント
#1070 sumreg:frac -> tmpA:exp
#1071 jmp #1079
#1072 shift tmpC L 0 bytes, 1 bits CORDICスキャンループのトップ
#1073 shift L -> tmpC 角度を左シフト
#1074 trig const -> Breg/rnd
#1075 adder: tmpC - Breg cin=1, roundmode CORDIC角度を減算
#1076 adder sign -> cordic, shl 決定ビットをシフトレジスタに保存
#1077 jmp #1079 if not adder pos 加算器が正でない場合はジャンプ
#1078 sumreg:frac,rnd -> tmpC
#1079 jmp #1072 if not const latch zero CORDICスキャンループのボトム
#1080 tmpC -> tmpA:frac tmpA, tmpBを更新
#1081 expConst -> shiftcount 16 -> shiftcount (それ以外の場合は指数に基づく)
#1082 tmpA:frac -> tmpB:frac パデ近似
#1083 tmpA:frac -> Breg tmpA = ang
#1084 call SQUARE 角度を二乗
#1085 shift sumreg:frac R count byte bit
#1086 shift R -> sumreg:frac スケールするために2回右シフト
#1087 shift sumreg:frac R count byte bit
#1088 shift R -> Breg Breg = ang^2
#1089 1.1 -> tmpB:frac 3 (指数1で)
#1090 adder: tmpB:frac - Breg cin=0
#1091 sumreg:frac -> tmpB:frac tmpB (X) = 3-ang^2
#1092 shift tmpA:frac R 0 bytes, 1 bits
#1093 shift R -> Breg/rnd
#1094 adder: tmpA:frac + Breg cin=0, roundmode ang + ang/2
#1095 sumreg:sign,frac,rnd -> tmpC tmpC (Y) = 3×ang (適切な指数で)
#1096 expconst 0x3ff0 指数 -15
#1097 expConst -> Breg
#1098 adder: tmpA:exp - Breg cin=1
#1099 jmp #1118 if not adder pos 指数が小さすぎる場合はスキップ
#1100 shift tmpC R 0 bytes, 1 bits CORDIC擬似乗算パス
#1101 #15 -> loopcounter
#1102 shift R -> tmpC
#1103 jmp #1118 if not cordic[0] CORDIC: 保存された決定ビットが...の場合ジャンプ
#1104 shift tmpC R loopcount tmpC (Y) をシフターに送信
#1105 tmpC -> Breg/rnd tmpC を加算器に送信
#1106 adder: tmpB:frac + Breg cin=0, roundmode tmpB (X) はtmpCがスケールされているためシフトされない
#1107 sumreg:sign,frac,rnd -> tmpC tmpC = tmpC + tmpB (暗黙的 >>n)
#1108 shift R -> sumreg:frac,rnd 古いtmpCをシフトして合計レジスタに
#1109 shift sumreg:frac,rnd R loopcount tmpCがスケールされているため再度右シフト
#1110 shift R -> Breg/rnd そしてBレジスタに送信
#1111 adder: tmpB:frac - Breg cin=1, roundmode
#1112 sumreg:frac,rnd -> tmpB:frac tmpB = tmpB - tmpC>>n
#1113 cordic shr シフトレジスタビットをシフトアウト
#1114 shift tmpC R 0 bytes, 1 bits tmpC (Y) のシフト開始
#1115 jmp #1118 if not cordic==0 カウンターがゼロなら終了
#1116 shift R -> tmpC tmpC (Y) を右シフト
#1117 jmp #1103 if not const latch zero カウンターがゼロなら終了
#1118 expconst 0x3fff CORDIC完了
#1119 tmpB:frac -> sumreg:frac tmpB (X) の最上位ビットをテスト
#1120 jmp #1124 if reg bit 63 セットされている場合、指数0を使用
#1121 expconst 0x3ffe それ以外の場合は、指数-1を使用し
#1122 shift sumreg:frac L 0 bytes, 1 bits 左に1ビットシフトして正規化
#1123 shift L -> tmpB:frac
#1124 expConst -> tmpB:sign,exp tmpBに指数を格納
#1125 tmpC -> tmpA:frac tmpC (Y) をtmpAに格納
#1126 tmpC -> sumreg:frac,sign
#1127 jmp #1132 if not sumreg[64] オーバーフロービットをテスト
#1128 shift tmpC R 0 bytes, 1 bits セットされている場合、右シフトして正規化
#1129 shift R -> tmpA:frac
#1130 adder: tmpA:exp + 0 cin=1 指数を1つインクリメント
#1131 sumreg:frac -> tmpA:exp
#1132 tmpB -> st(0) tmpB をスタックトップにプッシュ:X(分母)
#1133 stackPtr++
#1134 tmpA -> st(0) tmpA を st(1) にプッシュ:Y(分子)
#1135 stackPtr--
#1136 RNI FPTAN終了
FPTANマイクロコードはアドレス#1039(10進数)から始まります。マイクロコードは、スタックのトップから引数をtmpAレジスタに移動させることから始まります。トップの値が空の場合、スタックアンダーフローを示します。スタックの次の要素(結果を保持する位置)が空でない場合、スタックオーバーフローを示します。いずれの場合も、マイクロコードは「無効」例外を示し、命令を終了します。
8087の奇妙な機能の一つは、結果が正確でない場合に「精度」例外で結果にフラグを立てることです(これは非常に頻繁に発生します。例えば、1/10でさえも)。8087が正確に計算できる唯一のタンジェントはtan(0)であり、他のすべての入力は精度例外(#1044)になります。
次に、引数の指数がテストされ、実行が3つのパスに分割されます。指数が-64以下の場合、引数は非常に小さいため、タンジェントはシステムの精度内で引数と等しくなります。この場合(#1057)、元の引数は変更されずに返され(分母1がプッシュされ)、コードは終了します。2番目のケースは、引数の指数が-17以下の場合です。この場合、CORDICステップはスキップされ、ルーチンは直接有理近似(#1082)にジャンプします。
CORDIC擬似除算
最も興味深いケースは、指数が-1から-16の間の場合に実行されるCORDICパス(#1061)です。概念的には、コードは16個のCORDICステップを実行し、16個の格納された角度を使用します。しかし、コードは最適化されており、小さい入力に対して大きい角度をスキップします。具体的には、ループカウンタは入力角度の指数に基づいて初期化されます(#1062)。CORDIC擬似除算ループ(#1061〜#1080)は角度をテストし、大きすぎないものを減算します。
決定結果は、チップの右端にある16ビットシフトレジスタに記録されます。おそらく、レイアウトに未使用のスペースがあったのでしょう。シフトレジスタはシリアルにロードおよびアンロードされるため、内部フラクショントバスにアクセスする必要はなく、ビットをシフトインおよびアウトするための2本の線だけで済みます。そのため、シフトレジスタは未使用のスペースに配置できます。
コードは浮動小数点演算ではなく64ビット整数演算を使用するように最適化されています。これにより、コードの理解が難しくなります。なぜなら、値は暗黙的な指数を持つ固定小数点数として見なす必要があるからです。これらの指数はどこにも格納されていませんが、アルゴリズムを分析することで決定できます。ROM内の角度定数でさえ、明示的な指数を持っていません。さらに、ループをステップごとに通過するたびに暗黙的な指数が変化して精度を維持します。大まかに言えば、ループの各サイクルで値は約2倍になり、角度定数もそれに応じて縮小します。値に固定指数があった場合、16個の先頭ゼロになり、精度が無駄になります。しかし、各サイクルで値をスケーリングする(左シフトで)ことで、数値は引き続き64ビット全体を使用します。つまり、ハードウェアは高速な整数演算を実行していますが、数学的には、チップに物理的に存在しない指数を持つ固定小数点演算と考えることができます。ループ中の暗黙的な指数の変化の詳細については、脚注の表を参照してください。
有理多項式近似
CORDIC擬似除算ループの後、マイクロコードは有理多項式近似(#1082)を計算します。小角パスはここで実行フローに再結合します。多項式近似を計算するマイクロコードには、いくつかの興味深い特徴があります。最も時間のかかる部分はSQUAREルーチンで、固定小数点数をそれ自身で乗算します。乗算は複雑なので、詳細は後日投稿します。しかし、簡単に言うと、8087はブースのアルゴリズムを使用して一度に2ビット(基数4)で乗算するため、通常のバイナリ乗算よりも2倍高速です。シフトと加算を実行するループは、マイクロコードではなくハードウェアで実装されています。つまり、1つのマイクロ命令が32回の加算を実行します。ハードウェアはビットをテストし、適切な加算または減算を行い、ループカウンタを更新し、ループします。パフォーマンスのために、シフトは8087の汎用シフターではなく、特殊なシフターで行われます。
平方を除く多項式は、乗算ではなく加算で計算されます。定数3は定数ROMからではなく、仮数の上位2ビットを設定する専用トランジスタから来ています。これは通常、NaNを提供するために使用されます。(暗黙的な指数が1の場合、これは3に対応します。)二乗を減算すると分子が得られます。分母については、角度は右シフト(つまり2で割る)され、自身に加算されます。これは3(厳密には1.5)を掛けることになりますが、暗黙的な指数を1に増やすとこれが3になります。分子を分母で割るのは高価でしょう。代わりに、分子と分母は、次のCORDICステップの初期YおよびX値として使用されます。
CORDIC擬似乗算
次に、回転をベクトルに適用するCORDICループ(#1100)です。回転は、最初のステップで計算された順序とは逆の順序で適用されます。精度を維持するために、最も小さい回転から順に適用されます。シフトレジスタからビットがシフトアウトされ、回転を適用するかどうかを示します。シフトレジスタがすべてゼロになるとすぐに、ループは停止します。つまり、小さい角度はループをフル16回ではなく、数回だけ通過します。
マイクロコードROMの顕微鏡下でのクローズアップ。垂直ポリシリコンラインがドーピングされたシリコン(ピンク)と交差する場所にトランジスタが形成されています。8087のROMは珍しく、4つのトランジスタサイズを使用しているため、トランジスタあたり2ビットを格納でき、通常のROMの2倍の密度です。
回転はシフトと加算(または減算)によって適用されますが、暗黙的な指数を追跡するのは少しトリッキーです。ベクトルはほぼ水平に始まるため、X値は約3、Y値は約2^-16です。ベクトルが回転するにつれて、Xは約3のままですが、Yは各ステップで約2倍になる可能性があります。各数値に最大の精度を提供するために、X(tmpB)の指数は1ですが、Y(tmpC)の指数は-14から始まり、Yが右シフトされるにつれてループごとに1ずつ増加します。(これらの指数はどこにも格納されていないことに注意してください。暗黙的です。)2つのレジスタは異なる(暗黙的な)指数を持つため、加算する前に値をシフトする必要があります。シフト量は直感的ではありません。脚注の表は、暗黙的な指数がループ中にどのように変化するかを明確にするのに役立つかもしれません。
CORDICループの後、コードの最後の部分(#1118)はXとY値を正規化し、命令から返される浮動小数点値を作成します。これらは現時点では「実際の」浮動小数点値ではないことを思い出してください。そのため、調整が必要になる場合があります。具体的には、Xに先頭の1がない場合、1位置右にシフトされ、Yに2つの先頭桁がある場合、1位置右にシフトされます。いずれの場合も、指数はそれに応じて調整されます。XとY値はスタックにプッシュされ(#1132)、命令が完了します。
結論
FPTAN命令は、その複雑さのため、8087命令としてはかなり遅いです。ドキュメントによると、通常450クロックサイクルかかります。(時間は大きく変動し、値によっては30から540クロックサイクルかかる場合があります。)私が調査した値(0.95)では、時間の33%がCORDIC擬似除算、15%が有理近似(主に二乗演算)、47%がCORDIC擬似乗算、5%がオーバーヘッドです。
CORDICは三角関数を計算する一般的な方法ですが、多項式などの代替手段もあります。8087は、CORDICと有理多項式を組み合わせている点で珍しいです。Pentiumでは、IntelはCORDICから多項式近似に移行しました。Pentiumの高速乗算回路により、多項式が実用的になりました。現在、IntelはMKL(Math Kernel Library)やShort Vector Math Library(SVML)などのライブラリを提供しており、Intelハードウェアに最適化された高度に最適化された実装を提供しています。これらのライブラリは、パフォーマンスのために並列命令(SIMD)を使用した多項式近似を使用していると言われています。これらのライブラリにより、x87操作と80ビット浮動小数点数はほとんど廃止されています。それにもかかわらず、オリジナルの8087アルゴリズムのこの探求を楽しんでいただけたなら幸いです。
私は8087マイクロコードのリバースエンジニアリングを続ける予定です。最新情報については、Bluesky(@righto.com)、Mastodon(@kenshirriff@oldbytes.space)、またはRSSでフォローしてください。この作業は「Opcode Collective」のメンバー、特にROMイメージをマイクロコードデータに変換し、内容を広範囲に分析したSmartest BlobとGloriouscowと協力して行いました。詳細については、GitHubの8087リポジトリを参照してください。AIステートメント:エマーダッシュが存在するにもかかわらず、この記事の執筆にはAIは使用されていません(詳細)。Opcode Collectiveは、MLアルゴリズムを使用して各ROMセルを分類し、マイクロコードを抽出しました。
注釈と参考文献
-
8087についてさらに知りたい場合は、私の以前の8087投稿のリスト(新しいものから古いものへ)を以下に示します。
Intel 8087浮動小数点チップのマイクロコード:scale命令
Intel 8087浮動小数点チップの中心にある加算器
Intel 8087浮動小数点チップのマイクロコード内部:レジスタ交換
Intel 8087浮動小数点チップの命令デコーディング
Intel 8087浮動小数点チップのマイクロコードにおける条件
Intel 8087浮動小数点チップのスタック回路、リバースエンジニアリング
8087数学コプロセッサの高速ビットシフターのダイ分析
8087数学コプロセッサのダイからROM定数を抽出
Intel 8087浮動小数点チップの高密度ROM:トランジスタあたり2ビット
Intel 8087コプロセッサチップのダイ内部、現代の浮動小数点数の根源
↩ -
Intelのドキュメントは、8087と8086でエミュレートされた浮動小数点演算のパフォーマンス比較を提供しています。速度向上は命令によって異なりますが、通常は100倍近くになります。この速度向上により、8087チップはCADやスプレッドシートなどの数値アプリケーションで非常に望ましいものとなりました。 ↩
-
内部的には、8087は80ビットを使用して浮動小数点数を保持します。符号に1ビット、指数に15ビット、仮数に64ビットです。ただし、8087は丸めのために3つの追加の低位ビット(ガード、ラウンド、スティッキー)を使用します。これらのビットは、値が常に正しい方向に丸められることを保証します。データパスの一部には、符号またはオーバーフローのための追加ビットがあります。シフターは68ビット幅で、加算器は69ビット幅です。ほとんどの場合、これらの追加ビットは無視し、データパスを64ビット幅と呼びます。 ↩
-
8087のXおよびY値からsin θを計算するための一般的な式はsin θ = Y/sqrt(X^2+Y^2)です。cos θも同様です。 ↩
-
特殊な角度(度数)は約45°、26.6°、14°、7.1°、3.6°、1.8°、0.9°…です。特殊な角度を合計すると常に目的の角度θに収束するかどうか疑問に思うかもしれません。証明はこちらで見つけることができます。arctan(2^-n)は2^-n(ラジアン)に急速に近づくことに注意してください。そのため、バイナリ小数表現に似ており、ギャップを各ステップで約半分にカットします。 ↩
-
8087のCORDIC実装は、sinとcosを見つける一般的なCORDICの使用とはいくらか異なります。このアプローチでは、すべての特殊な角度が使用されますが、角度は各ステップで加算または減算され、目的の角度への収束につながります。各ステップで行列が1/sin αiでスケーリングされるため、終了ベクトルはもはや単位ベクトルではないことを思い出してください。その結果、cosとsinは最終ベクトル(X, Y)と一致しません。
トリックは、すべての特殊な角度が使用される場合、全体のスケーリング係数が最終的に同じになり、単純にすべてのcos αi因子の積になることです。(回転が正か負かは関係ありません。なぜならcos αi = cos -αiだからです。)したがって、全体のスケーリング係数は事前に計算でき、初期単位ベクトルはこの量で事前にスケーリングできます。その結果、最終ベクトル(X, Y)は直接(cos θ, sin θ)を生成します。これが私たちが望むものです。
重要な点は、CORDICアプローチには2つあることです。正と負の角度を使用するアプローチ、または角度を使用または省略するアプローチです。(最初のケースは各角度を+1または-1で乗算し、2番目のケースは各角度を1または0で乗算します。)ほとんどのCORDIC実装は最初のケースを使用し、8087は2番目のケースを使用します。 ↩
- CORDICの作成者であるジャック・ヴォルダーは、CORDICの誕生という記事を書き、その歴史を詳細に説明し、B-58ナビゲーションコンピュータの写真も掲載しています。ヴォルダーの1959年の元の記事はCORDIC計算技術とCORDIC三角計算技術です。
[画像: CORDIC-IIデジタルコンピュータシステム。写真提供:General Dynamics、「CORDICの誕生」より。]
CORDIC-IIデジタルコンピュータシステム。写真提供:General Dynamics、「CORDICの誕生」より。
上の写真はB-58航空機で使用されたCORDIC IIコンピュータを示しています。これは30ビットシリアルコンピュータで、198.4 kHzで動作し、重さは134ポンドでした。ダイオードトランジスタロジック(DTL)ゲートで実装され、2498個のトランジスタと4265個のダイオードを使用し、メモリとしてドラムメモリ(上部に見える)を使用していました。これは39キロバイトに相当します。興味深いことに、CORDIC操作はサブルーチンではなく、命令セットの基本命令として実装されていました。CORDIC命令は5ミリ秒かかり、乗算または除算と同じ速度でした。 ↩
- このパデ近似は、分子が1次多項式、分母が2次多項式であるため、[1,2]近似と呼ばれます。パデ近似は、tanの連分数展開から導出できます。パデ近似の構築を参照してください。
ところで、微積分を学んだことがあるなら、テイラー級数が関数を近似するのに良い方法だと思うかもしれません。残念ながら、テイラー級数は、点ではなく、区間全体で関数を近似するのに適していません。Pentiumのように、区間全体での最大誤差を最小化する多項式を使用する方がはるかに優れています。 ↩
-
8087のアルゴリズムは、Rafi Naveによる超越関数の数値プロセッサへの実装で説明されています。Rafi Naveは8087のハードウェア設計を主導しました。 ↩
-
FPTANの有効な引数範囲は0 < θ < π/4と文書化されています。そのため、私が使用するデモンストレーション値0.95は、文書化された範囲外です。この範囲は奇妙に思えます。なぜなら、最初のCORDIC定数はarctan(1)、π/4であり、これはπ/4より大きい入力にのみ役立つからです。したがって、8087は希少なROMエントリと追加のループサイクルを使用して、範囲外の値に対処します。これについて2つの仮説があります。おそらく8087はより広い引数範囲のために実装されましたが、数値誤差が予想よりも大きかったため、範囲が切り捨てられました。あるいは、FPATANアークタンジェント命令は最初のCORDIC定数を必要とする可能性があり、FPTANとFPATANで同じ定数ループを使用する方が簡単だったかもしれません。(まだFPATANを調べていないので確認できません。)いずれにしても、コードは0.95で動作します。角度が大きく、より見やすいため、例として使用します。
もう一つの奇妙な点は、ドキュメントが0が範囲に含まれるかどうかに一貫性がないことです。8087と8086の主要なアーキテクトによる書籍The 8087 Primerは、引数範囲が0を除外していると述べています。これはマイクロコードを単純化するために行われた決定です。しかし、マイクロコード(#1044)を見ると、コードが明示的にゼロ入力をチェックし、そのケースを処理していることがわかります。
FPTANは、結果が無限大に近づくにつれて精度が低下するものの、π/2に近い値まで機能するようです。しかし、1からπ/2までの値(定義された範囲外で指数が0)は、設計ではなく偶然によって機能する可能性が高いです。より大きな指数は追加のループ反復をもたらします。三角定数のルックアップはアルゴリズムをラップアラウンドし、最後の定数atan(2^-15)から開始します。しかし、スケーリングのため、この値は約2として解釈されます。このCORDIC角度はπ/2より大きいため、スキップされます。その後、アルゴリズムは残りの定数で進行し、正常に実行されます。
脚注の脚注:数学的な意味での「範囲」は関数の出力ですが、Intelはそれを関数の入力を記述するために使用しており、これは数学者がドメインと呼びます。 ↩
-
8087のテンポラリリアルフォーマットと外部フォーマットの1つの違いは、テンポラリリアルでは、先頭の1桁が数値に明示的に格納されていることです。外部フォーマットでは、先頭の1は暗黙的で数値に格納されていないため、追加の1ビットの精度が得られますが、演算はより複雑になります。 ↩
-
下のフローチャートは、
FPTANマイクロコードの制御フローを示しています。主なブロックは、CORDIC擬似除算、有理近似、およびCORDIC擬似乗算です。(大きな画像をクリックしてください。)
FPTANマイクロコードのフローチャート。
-
比較には複数のマイクロ命令が必要です。例えば、
0x3ff0のような定数を選択し(指数は16383または0x3fffでバイアスされていることを思い出してください。したがって、0x3ff0は-15に対応します)、定数を加算器に移動し、定数を指数から減算し、結果に基づいて分岐します。 ↩ -
CORDICアルゴリズムの最初のステップ(
#1061〜#1068)は別々に処理されます。CORDICアルゴリズムの最初のステップが特別な理由を理解するのにしばらく時間がかかりました。原因は、CORDIC角度が2^-nに近いが、正確ではないことです。したがって、CORDICサイクルの数は、入力角度の指数が変わるときに正確には変化しません。これは問題です。なぜなら、擬似除算サイクルの数は指数に依存しますが、擬似乗算サイクルの数は使用される最大のCORDIC角度に依存するからです。両方のループで数値がスケーリングされるため、サイクルの数が一致しないと、結果が2倍ずれます。最初のCORDICステップは、最初のCORDIC定数が使用されるかどうかをテストし、このずれを相殺するためにtmpA指数を1つインクリメントします。(これが理解できなくても心配しないでください。) ↩ -
8087の定数ROMは仮数を保持しますが、指数は保持しません。私が最初に定数ROMから定数を抽出したとき(2020年頃、リンク)、指数が見つからなかったので、意味のある値になるような妥当な指数を考え出しました。8087には別の指数ROMがあります。マイクロコードを調べた今、指数ROMの指数は定数ROMの仮数とは無関係であることがわかります。当時、指数を理解しようと時間を無駄にしなかったことを嬉しく思います :-) ↩
-
以下の表は、0.95を入力としたアルゴリズムの各ステップでの計算を示しています。計算は整数演算で行われることに注意してください。指数(灰色)は数値の一部として格納されていませんが、アルゴリズムによって暗示されています。指数は各ステップで変化するため、擬似除算ステージ中に値が小さくなるにつれて指数も小さくなり、値が利用可能なビットの大部分を使用できるようになります。逆のことが擬似乗算中に起こります。値は小さく始まり、ベクトルが回転するにつれて増加します。指数は各ステップで増加し、これを相殺します。「実際の」浮動小数点数とは異なり、ビット表現は正規化されていません。場合によってはバイナリポイントの左側に2つの1があり、場合によっては先頭ゼロがあります。つまり、指数は各ステップで固定されており、値に基づいて変化しません。
| 操作 | ビット | 値 | フラグ | レジスタ |
|---|---|---|---|---|
| θ でロード | 1.1110011…×2^-1 | 0.9500 | tmpC | |
| atan(2^0) を比較 | 1.1001001…×2^-1 | 0.7854 | 1 | const |
| 角度を減算 | 0.0101010…×2^-1 | 0.1646 | tmpC | |
| 左シフト | 0.1010100…×2^-2 | 0.1646 | tmpC | |
| atan(2^-1) を比較 | 1.1101101…×2^-2 | 0.4636 | 0 | const |
| 左シフト | 1.0101000…×2^-3 | 0.1646 | tmpC | |
| atan(2^-2) を比較 | 1.1111010…×2^-3 | 0.2450 | 0 | const |
| 左シフト | 10.1010001…×2^-4 | 0.1646 | tmpC | |
| atan(2^-3) を比較 | 1.1111110…×2^-4 | 0.1244 | 1 | const |
| 角度を減算 | 0.1010010…×2^-4 | 0.04025 | tmpC | |
| 左シフト | 1.0100100…×2^-5 | 0.04025 | tmpC | |
| atan(2^-4) を比較 | 1.1111111…×2^-5 | 0.06242 | 0 | const |
| 左シフト | 10.1001001…×2^-6 | 0.04025 | tmpC | |
| atan(2^-5) を比較 | 1.1111111…×2^-6 | 0.03124 | 1 | const |
| 角度を減算 | 0.1001001…×2^-6 | 0.009007 | tmpC | |
| 左シフト | 1.0010011…×2^-7 | 0.009007 | tmpC | |
| atan(2^-6) を比較 | 1.1111111…×2^-7 | 0.01562 | 0 | const |
| 左シフト | 10.0100111…×2^-8 | 0.009007 | tmpC | |
| atan(2^-7) を比較 | 1.1111111…×2^-8 | 0.007812 | 1 | const |
| 角度を減算 | 0.0100111…×2^-8 | 0.001195 | tmpC | |
| 左シフト | 0.1001110…×2^-9 | 0.001195 | tmpC | |
| atan(2^-8) を比較 | 1.1111111…×2^-9 | 0.003906 | 0 | const |
| 左シフト | 1.0011100…×2^-10 | 0.001195 | tmpC | |
| atan(2^-9) を比較 | 1.1111111…×2^-10 | 0.001953 | 0 | const |
| 左シフト | 10.0111001…×2^-11 | 0.001195 | tmpC | |
| atan(2^-10) を比較 | 1.1111111…×2^-11 | 0.0009766 | 1 | const |
| 角度を減算 | 0.0111001…×2^-11 | 0.0002181 | tmpC | |
| 左シフト | 0.1110010…×2^-12 | 0.0002181 | tmpC | |
| atan(2^-11) を比較 | 1.1111111…×2^-12 | 0.0004883 | 0 | const |
| 左シフト | 1.1100100…×2^-13 | 0.0002181 | tmpC | |
| atan(2^-12) を比較 | 1.1111111…×2^-13 | 0.0002441 | 0 | const |
| 左シフト | 11.1001001…×2^-14 | 0.0002181 | tmpC | |
| atan(2^-13) を比較 | 1.1111111…×2^-14 | 0.0001221 | 1 | const |
| 角度を減算 | 1.1001001…×2^-14 | 0.00009604 | tmpC | |
| 左シフト | 11.0010010…×2^-15 | 0.00009604 | tmpC | |
| atan(2^-14) を比較 | 1.1111111…×2^-15 | 0.00006104 | 1 | const |
| 角度を減算 | 1.0010010…×2^-15 | 0.00003500 | tmpC | |
| 左シフト | 10.0100101…×2^-16 | 0.00003500 | tmpC | |
| atan(2^-15) を比較 | 1.1111111…×2^-16 | 0.00003052 | 1 | const |
| 角度を減算 | 0.0100101…×2^-16 | 0.000004482 | tmpC | |
| X 近似 | 1.0111111…×2^1 | 3.0000 | tmpB | |
| Y 近似 | 0.0011100…×2^-14 | 0.00001345 | tmpC | |
| Y += 2^-15X | 1.1011100…×2^-14 | 0.0001050 | 1 | tmpC |
| X -= 2^-15Yold | 1.0111111…×2^1 | 3.0000 | tmpB | |
| 右シフト | 0.1101110…×2^-13 | 0.0001050 | tmpC | |
| Y += 2^-14X | 10.0101110…×2^-13 | 0.0002881 | 1 | tmpC |
| X -= 2^-14Yold | 1.0111111…×2^1 | 3.0000 | tmpB | |
| 右シフト | 1.0010111…×2^-12 | 0.0002881 | tmpC | |
| Y += 2^-13X | 10.1010111…×2^-12 | 0.0006543 | 1 | tmpC |
| X -= 2^-13Yold | 1.0111111…×2^1 | 3.0000 | tmpB | |
| 右シフト | 1.0101011…×2^-11 | 0.0006543 | tmpC | |
| 右シフト | 0.1010101…×2^-10 | 0.0006543 | 0 | tmpC |
| 右シフト | 0.0101010…×2^-9 | 0.0006543 | 0 | tmpC |
| Y += 2^-10X | 1.1101010…×2^-9 | 0.003584 | 1 | tmpC |
| X -= 2^-10Yold | 1.0111111…×2^1 | 3.0000 | tmpB | |
| 右シフト | 0.1110101…×2^-8 | 0.003584 | tmpC | |
| 右シフト | 0.0111010…×2^-7 | 0.003584 | 0 | tmpC |
| 右シフト | 0.0011101…×2^-6 | 0.003584 | 0 | tmpC |
| Y += 2^-7X | 1.1011101…×2^-6 | 0.02702 | 1 | tmpC |
| X -= 2^-7Yold | 1.0111111…×2^1 | 3.0000 | tmpB | |
| 右シフト | 0.1101110…×2^-5 | 0.02702 | tmpC | |
| 右シフト | 0.0110111…×2^-4 | 0.02702 | 0 | tmpC |
| Y += 2^-5X | 1.1110111…×2^-4 | 0.1208 | 1 | tmpC |
| X -= 2^-5Yold | 1.0111111…×2^1 | 2.9991 | tmpB | |
| 右シフト | 0.1111011…×2^-3 | 0.1208 | tmpC | |
| 右シフト | 0.0111101…×2^-2 | 0.1208 | 0 | tmpC |
| Y += 2^-3X | 1.1111101…×2^-2 | 0.4957 | 1 | tmpC |
| X -= 2^-3Yold | 1.0111110…×2^1 | 2.9840 | tmpB | |
| 右シフト | 0.1111110…×2^-1 | 0.4957 | tmpC | |
| 右シフト | 0.0111111…×2^0 | 0.4957 | 0 | tmpC |
| 右シフト | 0.0011111…×2^1 | 0.4957 | 0 | tmpC |
| Y += 2^0X | 1.1011110…×2^1 | 3.4797 | 1 | tmpC |
| X -= 2^0Yold | 1.0011111…×2^1 | 2.4884 | tmpB | |
| 最終的なX | 1.0011111…×2^1 | 2.4884 | tmpB | |
| 最終的なY | 1.1011110…×2^1 | 3.4797 | tmpA |