The SNAP Project: Design of Floating Point Arithmetic Units

(Proc. of the 13th IEEE Symposium on Computer Arithmetic , July 1997) Stuart F.Oberman , Hesham Al–Twaijry , and Michael J. Flynn

Abstract

近年、アプリケーションが行う計算は、ますます複雑になっている。 SPEC や一般的な 3D グラフィックスのようなパフォーマンスベンチマークの出現により、プロセッサ設計者は浮動小数点演算ユニットのインプリメンテーションに特に注意を払わなければならない。この論文は Stanford subnanosecond arithmetic processor(SNAP) の研究における、浮動小数点の加算、乗算、除算のハードウェアの設計の成果を示したものである。我々は 1 サイクルの浮動小数点加算演算を、可変レイテンシアルゴリズムにより全体の 32%に適用させることができた。乗算は、現在の実装線幅 (0.3 ミクロン) によるレイアウトアプローチでは二進木による方法が Wallace 木よりも劣っている。更に部分木生成では、大抵の場合において非 Booth 法よりも 2 ビット Booth 法の方が好ましい。除算については、機能反復法を使用することによって、最適なエリア・パフォーマンスを得ることができる。そして除算レイテンシの平均を下げる 2 つの方法を示す。

1 始めに

浮動小数点による表現は、広範囲の数値と高精度の数値を同時に扱うことを可能にする。そのため、今日の一部のマイクロプロセッサは浮動小数点用ハードウェアを備えている。以前は、シリコン面積の制限によって FPU の規模が抑えられてきた。集積回路技術の発達が、線幅の縮小とダイエリアの拡大をもたらした。この傾向によって、プロセッサ設計者が大量のトランジスタを利用できるようになりその結果、よりパフォーマンスの高い FPU を作るための複雑な計算アルゴリズムのインプリメンテーションが可能となった。

IEEE の浮動小数点標準規格である IEEE 754 は、現在の標準的なマイクロプロセッサで用いられている浮動小数点数の最も一般的な表現であり、インプリメントしなければならない数値の精度、計算の正確さ、数値演算の方法について書かれているものである。仮数部に要求される精度として、単精度 (24 ビット)、倍精度 (53 ビット) が規定され、拡張倍精度 (64 ビット以上) のサポートを推奨している。演算には加算、乗算、除算が含まれている。 SNAP は、 IEEE に従うハイパフォーマンスの浮動小数点の加算器、乗算器、除算器のアルゴリズムおよびインプリメンテーションの研究を行った。

1.1 デザインスペース

機能ユニットのパフォーマンスと使用面積は、回路構成、論理実装とアルゴリズムの選択に依存する。現在の回路構成には、 CMOS を静的に設計するものから、手で最適化したものまで様々である。論理設計も、行き当たり的な自動論理合成から、手動でゲートを配置するカスタム方式まで多岐に及んでいる。我々は全てのレベルでパフォーマンスとエリアサイズのトレードオフを検討した。

浮動小数点の機能ユニット設計において、 3 つの重要なパラメータとしてレイテンシ、サイクルタイム、エリアサイズが挙げられる。機能ユニットレイテンシとは、計算を完了するのに必要な時間のことで、通常はマシンサイクルを尺度にする。設計方針としては、固定レイテンシ (FL) と可変レイテンシ (VL) のどちらかが選択可能である。 FL 設計法において各計算ステップは、決まったステップで完了する。即ち、どの演算についても固定のサイクル数が経過した後に終了することを意味する。 FL 法におけるサイクルタイムは、レジスタからのオペランドの入力から結果を次のレジスタへラッチするまでの間の、最大の時間に相当する。一方、 VL 設計法は完了に要するサイクルは可変量である。 VL 法は、最大のレイテンシよりも速く結果を返すことを認めて、平均のレイテンシを小さくしている。 VL 法は、アルゴリズムの選択 (VLA) や回路デザイン (VLC) の選択によって、様々な設計が可能である。 VLA の設計は、システムクロックと同期を取って行われる。しかしながら、演算を完了するのに必要なトータルクロック数は、入力オペランドに入る実際の値のような要素に依存して変化する。 VLC の設計は、システムの他の場所と内部同期をとる必要がない。代わりに、同時に新しい複数の入力を認めて、システムクロックにとは独立に結果を出力する。

1.2 構成

以下の節では、パフォーマンスと実装面積のトレードオフについて詳細に述べていく。第 2 節では、浮動小数点加算のパフォーマンスを上げるための VLA のテクニックについて述べる。第 3 節はいかに、乗算のパフォーマンスとエリアサイズが、テクノロジに依存しているかを調査する。特に、部分積の数を減らすような、様々な部分積生成アルゴリズムの使用について分析している。第 4 節は浮動小数点除算のパフォーマンスについて調べ、第 5 節で結果をまとめる。

2 浮動小数点加算

最も頻繁に発生する浮動小数点演算は加算と減算であり、典型的な科学計算アプリケーションにおいては半分以上に達する。加算と減算はどちらも浮動小数点加算器で行われる。以上の理由から加算器のレイテンシを減らし、スループットを向上させる技術は、以前から多くの研究の対象になっている。

レイテンシを減らすために、我々は全ての入力について、構成要素を全て使用する必要がないということに着目した。この利点を活かして、平均の加算演算レイテンシを減らす、 2 つの VLA の技術が提案されている。平均レイテンシを効果的に使用するために、プロセッサは可変レイテンシの機能ユニットを使用しなければならない。プロセッサは、レイテンシを減らして最高のパフォーマンスを得るために、アウトオブオーダー実行が可能なダイナミックスケジューリングを利用しなければならない。

2.1 現在のアルゴリズム

浮動小数点加算器は数個の独立した操作から構成されている。アルゴリズムのクリティカルパス上にある最大の操作の数を減らすことで、最大のパフォーマンスを得ることができる。ここでは、精度を倍精度と仮定して解析を行なう。

浮動小数点加算器のブロック図を図 1 に示す。商用のマイクロプロセッサの中には、図と同様のアーキテクチャに基づいて実装されているものもある。このアーキテクチャは、浮動小数点加算器のデータフローを多角的に分析し、利用している。有効数字部 (仮数部) のデータパスは CLOSE path と FAR path の 2 つに分けられている。減算において、 2 数の指数の差が 1 よりも大きいとき (FAR path) は、桁のキャンセレーションは決して大きなものにはならない。言いかえれば、左シフトは多くても 1 ビットであるということである。反対に、指数部の差が最大 1 である (CLOSE path) とき、大きなキャンセレーションが起こりうるが、最初の桁合わせには大きな右シフトを必要としない。これは、クリティカルパス上で 1 回だけ、大きなシフトが起こりうることを示すもので、桁合わせの右シフトと正規化の左シフトが排他的に動作する。

他にも、逐次処理の数そのものを減らすアルゴリズムで最適化を図ることができる。加算器をそのまま素直に実装すると、丸め処理は、他の全ての命令が終了してから逐次処理を行うインクリメンタで実現することになる。しかし、演算の中で丸め処理のステップは時間がかかり、しかも変更される結果は部分的で小さなものである。あらかじめ全ての可能性のある結果を計算しておき、正しい結果を選択することにより、丸めと (数値フォーマットへの) 変換を減らすことができる。 IEEE の、最も近い値への丸め (RN) モードにおいて、 A + B と A + B + 1 という計算は、丸めと変換の全ての可能性を十分満たしている。この最適化をアルゴリズムに組み入れるためには、 2 つのパスの各々で、有効数字部の加算器で sum と sum + 1 の両方の演算が要求され、通常は複合加算器 (ComAdd) が用いられる。正しい結果の選択は丸めビットの解析によってなされ、最終的にどちらかの結果が採用される。この最適化は有効数字の加算ステップを 1 減らすことができる。

IEEE の有向丸めモードである、 +∞ と−∞ への丸め (RP,RM) モードもまた、 A + B + 2 を計算する必要がある。丸めのために ulp に 1 を加算することにより、オーバーフローを引き起こす可能性があるため、正規化のための 1 ビットの右シフトが必要となる。 RN については、保護ビット (有効数字フィールドにおける LSB の更に 1 つ下のビット) が、丸める際には必ず 1 でなければならない為、このことは問題にはならない。従って、 1ulp の加算は保護ビットに対して行えばよく、その結果、 MSB の更に上のビットへキャリーアウトを引き起こす (このビットは正規化の結果 LSB となる)。しかしながら、有向丸めモードにおいて保護ビットは必ずしも 1 である必要がなく、 1 ビット正規化右シフトを要求するオーバーフローが起こるときには、明確な sum + 2 の加算が要求されている。この加算結果は、 FAR path の複合加算器の前に半加算器の列を置くか、 2 つの複合加算器を 2 重に使用して出力することができ、一方の加算器では、キャリーアウトが起こらない場合の sum と sum + 1 を計算し、他方の加算器は、キャリーアウトが起きたと仮定したときの結果を計算している。

必ず大きな値から小さな値が引かれるようにするため、指数の差に基づいて、仮数はスワップされるが、 CLOSE path において指数に差がないときは例外である。しかしながらそのような時は、桁合わせの右シフトが無いため、演算結果は正確で、丸めの必要がない。しかし、丸めの必要がなくてもあらかじめ sum と sum + 1 を計算して選択することで、補数の再計算の手間をはぶくことができる。真の減算 A − B は、 A + \overline{B} + 1 と等価、即ち sum + 1 を用いればよい。しかしこのとき、キャリーが 0 であったなら、演算結果は負となっているので、その値を再び 2 の補数器にかけなくてはならない。補数をかけた結果は、 sum をビット反転して考えると

−(A − B) = \overline{A + \overline{B}}

のようになる。即ち、マルチプレクサとビット反転器のみで、 2 回の補数計算を省略することができる。

CLOSE path における更なる改善方法は、正規化左シフトの大きさの計算を、複合加算と逐次的にではなく並列に行うことであり、これは LOP(leading-one-prediction) と PENC(priority-encoding) というブロックにてなされるものである。クロックレートの高いマイクロプロセッサにおいて、これら全ての最適化を採用した加算器は、通常 3 クロックかかる。クリティカルパスである第 3 ステージは、半加算器、複合加算器、マルチプレクサ、ドライバで構成されている。

2.2 可変レイテンシアルゴリズム

図 1 から、最初のサイクルにおいて、レイテンシの大きなオペレーションは FAR path の方である。ここは、 2 値の指数の差の絶対値を計算し、それに応じて仮数をスワップするハードウェアで構成されている。 IEEE 規格の倍精度オペランドでは、最小のレイテンシは 11 ビット加算器と 2 つのマルチプレクサの遅延に相当するものである。対照的に CLOSE path は比較的小さな計算量である。こちらは、指数の下 2 桁を見て、仮数をスワップするかどうかを調べる少量のゲートと、スワップを行うためのマルチプレクサが必要である。

CLOSE path は、最初のサイクルをアイドル状態にするのではなく、ハードウェアを 2 重化させている利点を活かして、 1 サイクル CLOSE path の初期化を行うことができる。これは CLOSE path において、第 2 ステージと第 3 ステージのハードウェアを前のステージに移動させることで実現できる。 CLOSE path の最初のステージは FAR path に比べて早く終了するので、第 2 ステージの加算器は、サイクルタイムの増加は生じない。この最初のサイクルは、第 2 世代の DEC 21164 の浮動小数点加算器に似ている。

提案しているアルゴリズムによるオペレーションは、以下の通りである。どちらのパスも、最初のサイクルで投機実行を行なっている。第 1 サイクルが終了したときは、 FAR path によって、正確な指数の差が計算されている。指数の差から判断して、 FAR path が正しいパスだとわかると、このパスの残った 2 クロックの計算を続け、トータルのレイテンシは 3 クロックとなる。しかし、もしも CLOSE path が選ばれたならば、もう 1 クロック実行を進め、トータルは 2 サイクルとなる。最大のレイテンシは 3 クロックのままである一方、それより速い CLOSE path によって、平均のレイテンシを減らすことができる。もし、 CLOSE path が、頻度の高いパスであるならば、平均のレイテンシを最大で 1/3 まで減らすことができる。

更にいくつかの点に着目することで、 CLOSE path のレイテンシを減らすことが可能である。 1 つ目は、第 2 サイクルの正規化左シフトは全ての計算結果にとって必ずしも必要ではないことである。正規化シフトは、減算のときだけに起こるのである。加算は絶対に左シフトが必要ないため、 CLOSE path の加算命令は最初のサイクルで命令を終了させることができる。 2 つ目は、減算のとき、正規化のシフト数が 2 ビット以下のような小さなものであるとき、それを大きなシフトを行う回路と分離することができる。大きなシフトは、やはり第 2 サイクルでシフタを必要とするが、小さなシフトのときは、最初のサイクルで、わずかなマルチプレクサを通すだけで完了できる。どちらの改善も、サイクルタイムにほとんど影響を与えることなく、 1 サイクルで命令を完了させることができる。もしこれらのケースが頻繁に起こるのであれば、平均のレイテンシを下げることができる。可変レイテンシ加算器のブロックダイアグラムを図 2 に示す。

2.3 パフォーマンス

この改善による効果を確かめるため、実際のアプリケーションのオペランドを用いて、このアルゴリズムのシミュレーションを行った。ここでは、 DEC Alpha 3000/500 workstation で動作する SPECfp92 ベンチマークのうち、 10 のアプリケーションからなる ATOM instrumentation system を使用して、オペランドのデータを得た。全ての倍精度浮動小数点加算と減算命令が用意され、各命令のオペランドは、入力の標準セットとしてカスタム浮動小数点加算シミュレータに投入され、分析した。シミュレータは各オペランドのセットに対し、実質的な命令の種類、指数の差、正規化の桁数を記録している。

その結果、命令の 57%は FAR path で、 3 サイクルを必要とし、残りの 47% は CLOSE path で、最大 2 サイクルかかることがわかった。他の研究における、全く異なるアーキテクチャで異なるアプリケーションを用いた浮動小数点加算のオペランドと比較すると、この結果が有効であることがわかる。その研究とは、 30 年以上前に、 IBM 704 で、桁合わせと正規化シフトの大きさにおける 6 つの問題をトレースしていた。そのときは、 55%のオペランドが 1 ビットより大きな右シフトを必要とするのに対し、オペランドの 45%が、桁合わせの右シフトには、 0 ないし 1 ビットしか必要としない。この結果の類似は、科学計算のアプリケーションにおける、浮動小数点加算命令のオペランドの基本的な命令分散を示していると考えられる。

CLOSE path における、実効オペランドの分析によって、 43%のうちの 20% が加算命令で、 23%が減算命令であることがわかった。 CLOSE path の減算のうち、 2 ビット以下の左シフトを要する命令は 52.5% であり、全体として、命令の 20% + (0.525) × 23%=32%が 1 サイクルで終了する。提案した方法によるパフォーマンスをまとめたものを図 3 に示す。 3 クロックの固定レイテンシである、ツーパスの浮動小数点加算器を基準にしたスピードアップ率と共に、それぞれのテクニックでの平均のレイテンシを示している。 CLOSE path の加算を 1 サイクルで終らせるようにしたとき (adds)、 1.27 倍のスピードアップが確認された。より高いパフォーマンスを得るために、 2 ビット以下の正規化シフトを第 1 サイクルで終了させるという最も積極的なインプリメンテーション (subs2) では、 1.33 倍にスピードアップした。これらのテクニックは、大きなハードウェアの追加や、サイクルタイムを圧迫することがない。以上で、 1 サイクルのスループットを維持できるとき、如何に VLA のテクニックが平均のレイテンシを下げることができるかを示した。

3 浮動小数点乗算

3.1 背景

浮動小数点乗算器のスピードは、 FPU のパフォーマンスに対してクリティカルである。乗算は、部分積の生成と部分積の加算の 2 つのプロセスによってなされる。乗算アルゴリズムは、どのように部分積を生成するかと、どのように部分積を足し合わせて最終解を導くかによって、差が生じる。

乗算器の設計に関する研究には、部分積の生成に関するものと、部分積の数を抑えることに関するものがある。部分積を減らす木に対して、初期の解析に用いられていたものは、各入力から各出力までの遅延が全て等しい単純な圧縮器遅延モデルの設計に基づいていた。また、相互結合による遅延も通常無視していた。不幸にも、このような単純なモデルでは、全ての入力が同じ遅延を持っているわけではないことと、相互結合による遅延の蓄積が膨大であるため、特に 0.5 ミクロン以下の小さな線幅のときは、実際のインプリメンテーションにおいて、パフォーマンスは正確に反映されない。しかしながら単純な遅延モデルは、 4–2 圧縮器を用いた二進木の設計においては全ての入力に対する遅延は大体等しいので、十分である。

(3,2) カウンタを用いた最適な部分積アレイの設計は、全ての遅延を考慮することが要求され、最悪のケースの遅延を小さくするようにカウンタを構成することは、重要なことである。故に、設計のアルゴリズミックなアプローチによって、カウンタの配置や異なるパスをとることによる遅延を考慮した、洗練された遅延モデルを用いることは極めて効果的である。我々がインプリメントしたのは、 Oklobdzija のアプローチに基づいているものの、カウンタの配置と異なったパスによる、相互接続の遅延も考慮したアルゴリズムである。我々のアルゴリズムは (3,2) カウンタによる複雑な遅延モデルを用いていて、部分積アレイの各列のレイアウトという制限を設けている。一段の配線追跡可能数は、製造プロセスと乗算器のフロアプランの関数となる。各列に対してパラメータを固定して、相互接続を制限している。

3.2 方法論

ここでは、パラメータの組み合わせによる、乗算器のパフォーマンスと実装エリアのトレードオフについて検討する。パラメータは、線幅 (1.0〜0.2 ミクロン)、カウンタコンフィグレーション ((3,2) カウンタ、又は 4–2 圧縮器)、エンコード法 (非 Booth、 Booth 2、又は Booth 3)、仮数の精度 (24b〜113b) の 4 つである。各々のカテゴリで、レイアウトツール MAGIC による二進木乗算器のカスタムレイアウトを行った。更に、線幅、エンコード法、仮数精度の全ての組み合わせ毎に (3,2) アレイを一意に作りなおした。二進木のレイアウトの一部を図 4 に示す。我々は、各パラメータの組み合わせ毎に SPICE でタイミングシミュレーションを行った。シミュレーションでは、相互接続による遅延だけではなく、トランジスタによる遅延も考慮している。 0.2 ミクロンまでの結果を測定するのに、 McFarland のスケーラブルな SPICE モデルを使用した。

倍精度における、非 Booth 法の乗算器について、アルゴリズミックに部分積アレイを生成したものと二進木の比較を図 5 に示す。グラフは、線幅が大きいとき、二進木とアルゴリズミックに生成したアレイのレイテンシは同等であるということを示している。これは、線幅が大きなときは、相互接続の部分が、二進木の全体の遅延に大きく影響しないためである。しかしながら、線幅が小さなときは、アルゴリズミックなレイアウトが二進木を凌いでいる。 4 倍精度 (113 ビット) の Booth 2 法を用いた乗算器も、部分積の数がほぼ等しいため、同様の理由があてはまる。

4 倍精度における非 Booth 法の乗算器について、アルゴリズミックに部分積アレイを生成したものと二進木の比較を図 6 に示す。グラフは、線幅が大きなときは二進木の方がアルゴリズミックに生成したアレイよりもレイテンシが小さくなっていることを示している。これは、 4 倍精度は部分積の数が多いので、クリティカルパスを通るカウンタの数が多くなることが原因である。この線幅では、相互接続によるレイテンシの寄与は小さい。大きなカウンタ数の結果として、クリティカルパス中に含まれるバッファの数が大きくなる。二進木は、 (3,2) アレイの設計におけるバッファによる遅延と、我々のアルゴリズムの単純さによる遅延とに対抗できる。しかしながら小さな線幅の時は、相互接続は全体の遅延に大きく影響する。我々の単純なアルゴリズミックアプローチでも、カウンタの引き回しが長いために起こる遅い入力と、速い入力とを結合することで、相互接続の遅延を隠すことができるため、二進木に匹敵するレイテンシを提供することができる。

表 1 は、線幅 0.3 ミクロンのときの仮数精度とエンコード法をパラメータとし、図 5 と図 6 に基づいたパフォーマンスの結果を示している。この表は二進木配列に比べてアルゴリズミックに設計した配列の方が、小さなレイテンシになっていることを示している。故に、 (3,2) カウンタをベースとした部分積アレイの生成と相互接続を行う、より洗練されたツールやアルゴリズムの設計に関して、更なる研究を行うことを勧める。

表 2 は、線幅 0.3 ミクロンで、各エンコード法と Booth 2 法との比較をまとめたものである。この表は、仮数が増加しても Booth 2 法はレイテンシが最小になるような選択であることを示している。大抵の場合において、 Booth 2 から Booth 3 に移行することによる被加算数の減少は、 Booth 3 で必要な困難な積 (3x) を生成するのに要する余分な遅延を埋め合わせることができない。故に、我々は、レイテンシを最小限にするよう設計するならば、部分積の生成には Booth 2 法の使用を勧める。

全ての乗算器のインプリメンテーションでレイテンシを最小化を要求されているわけではない。そのようなケースにおいては、レイテンシとエリアサイズのバランスをとって最適にデザインする。表 3 は、レイテンシとエリアサイズの積を最小化するための選択をまとめたものである。

単精度では、非 Booth 法と booth 2 法のレイテンシとエリアはほとんど同じである。結果として、遅延とエリアの積はどちらも等しくなる。インプリメンテーションの単純さからいって、このケースでは非 Booth 法が推奨される。それ以外の精度は、 Booth 2 法に比べて Booth 3 法の乗算器が 10〜15%サイズが小さく、かつ、速度が 5〜20%遅くなっている。従ってこの精度では、もしエリアサイズを最重要視するならば、 Booth 3 法を推奨する。

4 浮動小数点除算

今日の FPU において重視してきたことは、より高速な加算器及び乗算器の設計であり、除算器についてはあまり注意を払われていなかった。現在のアプリケーションやベンチマークは、除算は遅いもので出来るだけ使用しないようにという仮定に基づいて、プログラムを書かれている。浮動小数点を積極的に使用するアプリケーションでも、除算は頻繁に起こる演算ではないが、それでも、それを実装しなければ、システムパフォーマンスの低下を引き起こすことになる。従って、ハイパフォーマンスな FPU には高速かつ効果的な加算器、乗算器、除算器が不可欠である。パフォーマンスとエリアサイズについて、最適な浮動小数点除算器の設計法を選択することは、除算器のデザインスペースが大きく、また、除算アルゴリズムが 5 つの異なるクラスから構成されているため、難しい問題である。そのクラスとは、基数再帰、機能反復、高基数、早見表、可変レイテンシである。この節では、浮動小数点除算器に求められるパフォーマンスを調査し、 FL と VLA の組み合わせでそれを実現する幾つかのテクニックを提案する。

4.1 パフォーマンスとエリアのトレードオフ

我々は、浮動小数点除算器のレイテンシとシステムパフォーマンスの関係について詳しく調査した。システムパフォーマンスの評価は、 SPECfp92 ベンチマークから 11 のアプリケーションを用いて行った。これらのアプリケーションは、 DECstation 5000 の MIPS C および Fortran で O3 最適化コンパイルを行った。フレキシブルなプログラム解析ツールである pixie と pixstats が利用できるという理由から、 MIPS アーキテクチャ上での結果を示した。また、倍精度浮動小数点の加算は 2 サイクル、乗算は 5 サイクル、除算は 19 サイクルのレイテンシがあると仮定した MIPS R3000 マシンモデルにて評価取得を行った。

コンパイラだけで、どれくらいシステムパフォーマンスを改善できるかを知るために、最適化オプションのレベルとインターロック距離の関係を調べた。図 7 は、 O0 と O3 の両方の最適化でコンパイルした全アプリケーションの平均インターロック距離を示している。コンパイラがインテリジェントスケジューリング、ループ・アンローリングを行うことによって、アプリケーション中の命令レベル並列性を抽出し、その結果、インターロック距離が増加する。図 7 から、コンパイラ最適化オプションによっては、平均インターロック距離が 10 以上になることがわかる。従って、スカラプロセッサにおいては、 10 サイクル以下の除算のレイテンシを許容しなければならない。

除算のレイテンシが全体のシステムパフォーマンスに与える影響を決定するため、除算によるパフォーマンスの低下を調べた。低下の度合は、エクセス CPI、または、インターロックによる CPI というもので表現される。 1 から 20 サイクルの間の除算レイテンシによるパフォーマンスの低下を、図 8 に示した。この図では、 8 サイクル以上は SRT 法、 4〜8 サイクルはセルフタイム SRT 法、 4 サイクル以下は、巨大な初期値テーブルを必要とする高基数除算法でインプリメントした。

図 8 はまた、サイクル当りに発行する命令数が、除算によるエクセス CPI に与える影響も示している。命令発行の違いによる効果を調べる、ベースとなるモデルを仮定する必要がある。ここでは、命令発行レートを最大に保てるような理想的なスーパースカラプロセッサを仮定する。発行レートの値は、適切にインターロック距離を相殺するために用いられている。更に同図は、機能ユニットのレイテンシの減少によって、どのくらいエリアが増加するかを示している。エリアサイズの見積もりは、全てが 1 ミクロンスケールのスケーラブルな CMOS レイアウトルールで正規化された、既に報告されているレイアウトに基づいている。

4 サイクル以下のレイテンシを持つ除算器は目立ったシステムパフォーマンスの向上も無い上、エリアサイズが膨大になり、割に合わない。しかしながら一方では、サイクル当りの発行数を増やすことにより、除算の出力の緊急性が求められている。即ち、将来のマイクロプロセッサは、除算器のレイテンシが 10 サイクル以下であることが推奨され、更に強力な多重命令発行を行うマルチプロセッサはより高い性能の除算器を要求することになるだろう。

4.2 除算における高いパフォーマンスの達成

現在の浮動小数点除算器のインプリメンテーションは SRT 法によるものである。 SRT 法は、オペランド長が短いときに利用される除算アルゴリズムであり、各イタレーションの商ビットをたてる桁数が固定のアルゴリズムである。拡張倍精度や 4 倍精度のような長いフォーマットのオペランドでは、線形よりも速い収束が必要とされることは明白である。更に、 3D グラフィックのような、非常に重要な特定用途のアプリケーションでは、除算の高いスループットが要求される。しかし、シーケンシャルな SRT 除算器では、一度に 1 つのオペレーションしか処理されない。故に SRT 法は、高精度で高いスループットを目指す除算には適していない方法であるといえる。高いスループットを要求しないとき、単精度や倍精度のような短いフォーマットでならば、積極的に低基数 (基数 2 から基数 4) の回路テクニックとして SRT 法を認めてもいい。図 8 において、典型的な SRT のアルゴリズムでは、エリアサイズが小さく、レイテンシが 15 サイクル以上かかることを示している。

レイテンシを抑え、高いスループットを持つ高精度の除算器のインプリメンテーションは、機能反復法により実現できる。この実装法は、既にある浮動小数点乗算器を再利用することができる。そのため、エリアサイズとパフォーマンスの両方を考慮したインプリメンテーションにおいて、魅力的な方法である。 Newton-Raphson 法と級数展開 (Goldschmidt) 反復法は、機能反復法による高速除算のインプリメンテーションとして、どちらも有効な方法である。どちらのアルゴリズムも、 2 つの乗算と、 (しばしば単純な 1 の補数に置き換えることができる)2 の補数からイタレーションが構成されている。級数展開法では 2 つの乗算は互いに独立で、並行に処理が可能であるが、 Newton-Raphson 法の乗算は互いに依存関係が存在する。そのため、級数展開法はパイプライン化された乗算器の利点を活かして、 1 オペレーションあたりのレイテンシを低くし高いパフォーマンスを得ることができる。 Newton-Raphson 法は、パイプライン化されている乗算器が使われていないサイクルの時に、それ以外の除算命令を並行に処理することで、高い除算スループットを得ることができる。

4.3 高速な機能反復法

反復法による除算に必要とされるイタレーションの数は、初期値の近似の精度と密接に影響している。正確な初期値/近似値を得るために、通常は特別なテーブルが使われる。テーブルの設計で重要なことは、トータルのエリアサイズを最小にしつつ、近似の精度を最大にすることである。そのため、この領域は今でも非常に重要な研究分野である。

機能反復法に適用される VLA のテクニックとして、レシプロカルキャッシュの使用がある。結果キャッシュの使用は、 Richardson によって議論された。整数除算における、小容量レシプロカルキャッシュの使用については、参考文献 [19] で議論されている。レシプロカルキャッシュは、反復法による除算器のインプリメンテーションにおいて、浮動小数点除算の平均のレイテンシを下げるのに効果的な方法であることを示した。このテクニックは、実行時間とメモリ領域の増加の関係によって多くのアプリケーションに存在する、レシプロカル操作の冗長的な性質を利用したものである。ある値について 1 回計算がなされると、その値はレシプロカルキャッシュに収納される。そして除算命令が始まると同時に、レシプロカルキャッシュは、既に計算された値をチェックするためにアクセスする。その値が利用可能であるならば、値はキャッシュから取り出され、それを被除数と掛け合わせることで商を導く。利用可能でないときは、除算演算が続けられて、イタレーションが完了するときにその値がキャッシュに書き込まれる。 [S9] の研究では、 SPECfp92 と NAS のアプリケーションで解析が行われた。レシプロカルキャッシュを用いると、全体の記憶容量を標準的な 8 ビットの初期値検索表 (16Kb) のおおよそ 8 倍にすることで、浮動小数点除算の平均パフォーマンスが 2 倍になることが示されている。

機能反復法による除算の大きな欠点は、最終の剰余が欠如しており、正確な丸めが困難であるということである。商に対して正確な丸めを行うために通常は、商と除数に対して余分な乗算を行い、その積から被除数を引いて、最終の剰余を導くことが必要とされる。従って、 2 次収束アルゴリズムは正確に丸められた商を求めるために、 1 回ずつの乗算と減算のレイテンシペナルティを負うことになる。レイテンシペナルティを減らすために用いられる VLA のテクニックは、丸め前の結果に、適当に余分な保護ビットを持たせるというものを含んでいる。 Schwarz[20] は、丸め前の結果に、 1 ビットの保護ビットを付加することを提案している。これによって、戻り乗算及び減算が、平均的には、半分のケースにおいてのみ必要になった。 [S1] はこのテクニックを拡張して、更にレイテンシぺナルティを減らしている。保護ビットと丸めのモードに関して、あらゆるケースにおける徹底的な分析を行った。丸め前において、余分に m ビット精度を高めることで、戻り乗算と減算が必要なケースが全体の 2^{−m}になり、これにより、機能反復法を用いて商を正確に丸めを行い、平均レイテンシを減らすことができる。 RN においては、マシンで表現できる値と値の中間に極めて近いときは、無限大の精度で表現されている真の結果が、中間より大きいか小さいかを性質を決定するのに戻り乗算が必要になるが、そうでないときは、乗算の必要はない。 RZ、 RM、 RP の各モードについては、マシンで表現できる値に極めて近いときは、無限大の精度で表現されている真の結果が、どちらの機械数で表現されるべきかという性質を決定するために乗算が必要で、そうでないときは必要ない。

丸め前の結果に僅かな保護ビットを付加し、レシプロカルキャッシュをつけた、少量でも正確な初期値テーブルを使用することで、浮動小数点乗算のレイテンシを著しく減らすことができる。

5 まとめ

この論文のまとめとして、ハイパフォーマンスな FPU の構成の一例を図 9 に示す。

この FPU 中のパイプライン化された浮動小数点加算器は、図 2 の VLA のテクニックを用いている。パイプライン化された乗算器は、 (3,2) カウンタを用いた、アルゴリズミックデザインによる Booth 3 乗算器が示されている。このような乗算器のインプリメンテーションはパフォーマンスとエリアサイズのバランスがとれいている。除算は、 Newton-Raphson 法で計算が行われていて、これは、 1 つ以上の除算を同時に実行中にすることができ、それによって、高い除算のスループットを得ることができる。ハードウェアは、高精度な近似値を提供しなければいけない。少量のレシプロカルキャッシュは小さなレイテンシで、頻繁に利用される値を返す。このインプリメンテーションでは、 VLA の正確な丸めをサポートし、丸め前の商において保護ビットを付加して、に要求されているよりも高い精度で計算する乗算器を使用する。その結果、平均のレイテンシを下げている。この論文は、 FL のみによるインプリメンテーションよりも VL 法を用いた機能ユニットがパフォーマンスが高いことを示した。次世代のパフォーマンス指向のプロセッサには、 VL による、 FPU のベストパフォーマンスが得られる、フレキシブルかつロバストなマイクロアーキテクチャが要求される。スーパースカラプロセッサがより複雑になって、多重命令発行数の増加に伴い、プロセッサは、個々の浮動小数点機能ユニットのレイテンシがますます重要になってくるので、 VL 機能ユニットを組み入れることが必須となる。