- 1993年の Intel Pentium は、浮動小数点乗算を高速化するために3倍値を生成する専用の ×3 回路 を搭載しており、この小さな回路だけで数千個のトランジスタを使用していた
- Pentium は、64ビット乗算で加算する項を64個から22個に減らすため radix-8 乗算 を採用しているが、この方式では ×3 の倍数を高速に生成する必要がある
- ×3 の計算自体は
x + 2x の加算だが、残りの乗算段階がこの結果を待つため、carry lookahead や Kogge-Stone といった高速加算器の手法が必要になる
- 回路は8ビットブロック8個と上位 lookahead を組み合わせた階層構造で、オーバーフローと丸めのために実際の出力は 69ビット に拡張されている
- 約 9000個のトランジスタ が1つの ×3 回路に使われていることは、Pentium 世代で性能のためにどれほど複雑なハードウェア最適化が投入されていたかを示している
Pentiumが ×3 回路を別に用意した理由
- Pentium の 浮動小数点乗算器 は、2つの64ビット数を radix-8 方式で乗算する
- 通常の2進乗算では、各ビットごとに0または被乗数を加えるため、64ビット乗算では64個の項が必要になる
- radix-8 方式では、乗数を3ビットずつまとめて 0〜7 のいずれかを掛けるため、加える項は22個に減る
- 0〜7 の倍数のうち、いくつかはハードウェアで比較的簡単に生成できる
- ×2 は1ビット左シフトで処理できる
- ×4 は2ビット左シフトで処理できる
- ×6 と ×7 は Booth 乗算アルゴリズム により、次の radix-8 桁の +1 と現在の桁の減算を組み合わせて処理できる
- ×5 は ×8 から ×3 を引くことで得られる
- 結局、厄介な倍数は ×3 であり、Pentium はこれを浮動小数点乗算器内部の専用回路で解決している
単純な加算がボトルネックになる箇所
- 3倍値は、入力値と1ビット左にずらした入力値を加えることで作れる
- ボトルネックは加算過程の carry 伝播 にある
- リップルキャリー加算器では、下位ビットで発生した carry が上位ビットまで順番に伝わらなければならない
- ×3 の結果が準備できるまで残りの乗算処理を開始できないため、遅延を減らす必要がある
- Pentium は carry を逐次伝播させずに並列計算するため、carry-lookahead adder を使用する
- 各ビットで carry generate と carry propagate の信号を作る
- generate は、その位置で carry が生成される場合を表す
- propagate は、入ってきた carry が外へ伝わる場合を表す
- carry が並列に計算されれば、sum ビットも並列に計算できる
Kogge-Stoneと2段階 carry lookahead
- carry lookahead を単純に直接実装すると、ビット数が増えるほど回路と配線の負担が大きくなる
- ビット位置が上がるほど論理が複雑になる
- 入力数の多いゲートは電気的な理由で遅くなる
- Pentium は、8ビット単位の Kogge-Stone 並列プレフィックス加算器 を使用している
- Kogge-Stone は propagate/generate 信号を範囲単位で統合し、carry を並列計算する
- 中間結果を再利用して、遅延と回路規模を管理する
- 64ビット全体を1つの Kogge-Stone で処理せず、2段階の階層構造 に分けている
- 下位層では、8個の8ビット Kogge-Stone 回路で各ブロック内部の carry を計算する
- 上位層では、各8ビットブロックを1つの単位として見なし、ブロック間の carry を計算する
- 2つの階層を組み合わせることで、64ビット和に必要な carry を高速に供給する
- 回路は64ビット用と見なせるが、実際にはオーバーフロー防止と丸め用の余剰ビットを含めて 69ビット出力 を生成する
carry-selectで待ち時間を減らす
- 各8ビットブロックには carry-select adder が含まれている
- carry-in が 0 の場合と 1 の場合の和を、あらかじめ両方計算しておく
- 上位の lookahead 回路が実際の carry-in を知らせると、マルチプレクサが正しい結果を選択する
- この方式は、ハードウェアを余分に使う代わりに時間を節約する
- 2つの adder と、結果選択用のマルチプレクサが必要になる
- 和の計算と carry の計算を重ねることで、全体の遅延を減らす
- 最下位の8ビットブロックには carry-in がないため、carry-select 回路は不要である
- このブロックの出力ビットは XNOR ゲート で計算される
8ビットブロックの内部で起きていること
- ×3 回路の各8ビットブロックは、入力線を左側の adder と右側の経路に分岐させる
- この分岐構造によって、入力値と1ビット左にずらした入力値を加え、×3 を実現する
- ブロック上部は、propagate/generate 信号を作る回路で構成されている
- これらの信号は8ビット Kogge-Stone lookahead 回路に入力される
- Kogge-Stone 部分はビット位置ごとに複雑さが異なるため、繰り返しブロックのようには見えず、不規則に見える
- ブロック下部は carry-select adder 領域である
- 2つの和を事前に計算し、carry-in に応じてマルチプレクサが選択する
- carry-select adder ブロックは周辺回路より狭く配置されており、上位 Kogge-Stone 回路の一部が入る空間を作っている
- 各ブロックは、出力ビットを次の乗算器回路へ送る前に ドライバ回路 で増幅する
XNORゲートとトランジスタレベル実装
- 下位ビット領域の XNOR ゲートは、Pentium では マルチプレクサ として実装されている
- Intel 386 は XOR を AND-NOR ゲートで実装しており、Z-80 はパストランジスタを使っていたが、Pentium のアプローチは異なる
- 該当する XNOR 回路は、4つのインバータとパストランジスタ・マルチプレクサで構成される
- 入力 B が、マルチプレクサの2つの入力のうち入力 A または反転した A を選択する
- その結果として XNOR 関数が実現される
- チップ写真の解析では、上位2層の金属層を除去して、下位金属層 M1 とドープされたシリコン領域を観察している
- ポリシリコン配線がドープされたシリコンを横切る地点がトランジスタのゲートになる
- CMOS 回路は、上側の NMOS と下側の PMOS トランジスタで構成される
BiCMOS出力ドライバ
- ×3 回路の出力には 大電流 が必要となる
- 各 ×3 信号は、浮動小数点乗算器内で最大22個の項を駆動できる
- 行き先の回路が ×3 回路から離れている場合がある
- 長い配線と多数のトランジスタゲートにより静電容量が大きくなり、信号を高速に切り替えるには大きな電流が必要になる
- Pentium は、同一チップ上で bipolar transistor と CMOS を組み合わせた BiCMOS プロセスを採用していた
- Pentium は信号遅延を最大35%削減するために BiCMOS 回路を広範囲に使用していた
- Intel は Pentium Pro、Pentium II、Pentium III、Xeon にも BiCMOS を使用していた
- チップ電圧が低下するにつれて bipolar transistor の利点が薄れ、BiCMOS は最終的に使われなくなった
- ×3 回路のドライバは、BiCMOS ドライバがさらに第2の BiCMOS ドライバを駆動する構造になっている
- 大電流インバータのトランジスタゲートが大きいため、それを駆動する中間段が必要になる
- 小さな信号を複数段で増幅すると、全体の遅延を減らせる
- BiCMOS ドライバの NPN トランジスタは、一般的な MOS トランジスタとは異なり、大きな箱状に見える
- インバータは、PMOS で出力を高くし、NMOS で出力を低くする標準的な CMOS 構造を使用する
- 一部のインバータは、強い high または強い low 出力を出すよう、非対称な電流特性で設計されている
乗算ハードウェアが示す複雑化
- コンピュータの乗算ハードウェアの歴史は1950年代までさかのぼる
- Booth 乗算法 は1951年に説明された
- 並列乗算器は1960年代半ばに Wallace と Dadda が提案した
- 初期のマイクロプロセッサでは、ハードウェアによる乗算支援は限定的だった
- 6502 のようなプロセッサには乗算ハードウェアがなく、ユーザーがシフトと加算でソフトウェア実装する必要があった
- Intel 8086 はマイクロコードで低速な shift-and-add ループを実行していた
- 386 は multiply unit を備えていたが、乗算命令には最大41クロックサイクルかかった
- Pentium の時代には数百万個のトランジスタを搭載できるようになり、より複雑な性能最適化が可能になった
- Pentium の浮動小数点乗算は3クロックサイクルかかり、乗算回路はそのうち2サイクル使用される
- 整数乗算
MUL は11サイクルで、はるかに遅い
- 2008年の Nehalem マイクロアーキテクチャでは、浮動小数点乗算時間が1サイクルまで短縮された
- Pentium の ×3 乗算器には約 9000個のトランジスタ が含まれている
- これは1976年の Z80 マイクロプロセッサ全体より少し多い
- ×3 回路は、Pentium の浮動小数点ユニット内にある浮動小数点乗算器のほんの一部にすぎない
1件のコメント
Hacker Newsのコメント
かなり枝葉の話だけど、ずっと前に三進コンピュータのエミュレーションをしていたとき、3のべきで割る演算をビットシフトと加算の級数に変換する閉形式の変換を見つける、ちょっと気の利いた小技を使ったことがある。
まず
1/3 - 1/2 = 2/6 - 3/6、つまり1/3 = 1/2 - 1/2 (1/3)と見ればよい。この式を右辺に無限に代入すると、
1/3 = -(-1/2)^Nの形になり、Nは1..infの範囲になる。2と3のべきの組だけでなく、ほかの基数でも同じようなことができる。
要するに、2のべきに近い値については、加算器と減算器だけで一定時間の定数除算回路をかなり簡単に作れるということ。
Cinematronicsのアーケードゲーム用プロセッサには12ビットアキュムレータが2つある。
乗算命令はこの2つを1つの24ビット値のように右シフトし、最下位ビットに1が出たらメモリ内容を加算する。
だから上位半分をクリアし、下位半分にある値をロードし、もう一方のオペランドのメモリアドレスをどう設定していたかは忘れたけれど、1ビット乗算を何度も連続実行した。
こうして24ビット積を得られるが、私が見たコードはたいてい8回の乗算を連ねて使っていて、最も一般的な用途はゲームオブジェクト座標の回転のための2x2行列乗算だった。
1970年代半ばの既製7400シリーズ部品で作られていて、最大スループットは5MIPSだった。
この20年のあいだに固定小数点演算をやらなければならなかったことが何度かあるけど、前の世代のプログラマへの敬意が増した。
carry lookaheadやKogge-Stone additionのような手法の話が出ていたけど、ここでのKoggeはPeter Koggeのこと。Stanfordで博士研究を行い、スペースシャトル関連の仕事をし、IBM Fellowで、最初のマルチコアCPUを発明した人物だ。
「マルチコアCPU」自体は、厳密には1つの発明というよりアイデアに近い。半導体の歴史のある時点まで来ると、かなり明白でありふれたアイデアでもある。
マルチコアCPUを実際に動くものにするのは些細なことではないが、それも単一の発明ではないし、その時点では開発チームの規模が非常に大きく、1人ですべての問題を解決したと言うのはむしろ侮辱的ですらある。
Koggeが最初のマルチコアCPU開発を主導したのかもしれないし、ほかの人が可能だと考える前に推し進めた先駆者だったのかもしれないが、どちらにせよ彼が1人で発明したわけではない。
このアプローチは知的には十分に説得力がある。中央計算機へデータを送るのに遅延やコストがあるなら妥当で、私たちの場合は宇宙ベースのセンサだったので、そうした理屈を立てられた。
ただ、私の知るかぎり、この種の処理方式が宇宙ベース処理システムで体系的に採用されたことはなく、レーダーのような多くのシステムではセンサ近傍のハードウェアで一時的なデータ削減を行ってはいる。
そのつながりを教えてくれてありがとう。
筆者です。質問があれば答えます。
x4をx7から引いてx3を得る、というようにはできないのだろうか。何か見落としている気がする。
×2は 6x = 8x - 2x を使えるくらい簡単に計算できて、×4も 4x = 4x として簡単に計算できるなら、なぜ3xを 2x + 1x の和や 4x - 1x の差として計算するのが、それより難しいのか分からない。
それに、×6を何らかの方法で簡単に計算できるなら、その値を右シフトして×3にできない理由も気になる。追加のステップではあるけれど、その追加ステップはシフトだ。
小学校式の筆算の掛け算を思い浮かべればいい。
各項は計算がごく簡単でなければならず、項を得るためにシフトや符号反転はできても、さらに別の加算はできない。
要点は、×3を1回あらかじめ計算しておけば、その後必要な22個の項のどこにでもそのまま入れられるということ。
項の中で×2と×1を入れて×3を作ることはできない。そうすると各項ごとにもう1つ加算器が必要になる。
つまり欲しいのは**×3を計算する回路1つ**であって、22個の回路ではない。
×6の質問については、この値は項に負の×2を入れ、概念的に次の桁の数字に1を足して×8を得ることで計算される。この×8の値はまったく別の項の一部なので、右シフトすることはできない。
数字や和がたくさん行き来して複雑だけど、こう考えると筋は通るはず。
3倍乗算は実際によくある演算で、特にアドレス計算ではシフトと加算でインデックスに3を掛けることが多い。
素朴に実装すると遅延がかなり増える。しかしこの回路を使えば、LEA（Load Effective Address）命令を1サイクルで処理できるので、ここにその程度のトランジスタ予算を使うのは十分に妥当な選択だった。
LEAは、アドレッシングモードが計算したアドレスを、そのアドレスからデータを移す代わりに出力オペランドへ入れる命令にすぎず、LEAでできるアドレス計算はMOV命令でもすべて可能である。
x86でMOVやLEAが使うインデックス付きアドレッシングモードはスケール係数3をサポートしておらず、1、2、4、8のような2のべき乗しか使えない。したがって、アドレス生成で3倍乗算を使う場面はない。
記事は、3倍乗算器が浮動小数点乗算器の一部だとはっきり述べている。
「この×3乗算器にはおよそ9000個のトランジスタが含まれており、Z80マイクロプロセッサ全体（1976年）よりわずかに多い。×3乗算器はPentiumの浮動小数点ユニット内にある浮動小数点乗算器のごく一部にすぎないことを覚えておいてほしい。つまり、1つの機能の小さな断片が、17年前のマイクロプロセッサ全体よりも複雑であり、これはプロセッサの複雑さがどれほど途方もなく増大したかを示している。」
このような性能向上のペースが、今日のソフトウェア肥大化を生んだ。翌年の性能向上が、アルゴリズムやデータフローの文脈・局所性を批判的に考えなかった罪の大半を覆い隠してくれたからだ。
今日では、私が読む限り、シリコン半導体技術と現在の物理理解で合理的に実現できることの実質的な限界に達している。いまや振り子は逆方向に振れるべきであり、コンピュータはより力任せにではなく、より賢く働く必要がある。
ただし、ソフトウェア肥大化のほうがさらに速く進んでいると思う。
goto/jmpによる命令移動 → vtable参照 → 辞書でのハッシュ計算と検索 → 大規模言語モデルの実行「7を掛ける代わりに、数値の8倍を足してからその数値を引くことで7倍を得る。2段階必要に見えるかもしれないが、左側の桁で1をさらに掛ける工夫によって、追加の段階なしに8倍係数を得る。」
これは、主乗算器部分に数値を入れる前に、「次の桁」に1を足す加算器があるという意味なのか？ それ自体、キャリー予測回路に似ているように見える。
いつこれが必要になるのかも考えさせられる:
7 = 8-1,6 = 8-2,5 = 8-3,4 = 8-4最後のケースは記事でやるとは書かれていないが、3ビット値の最上位ビットで次の桁に1を足すべきかを判断すれば、ゲートをいくつか節約できそうだ。
×3回路を必要とする基数8 Booth乗算器を選んだのは興味深い。最大周波数を引き上げるための面積/性能トレードオフのように見え、同じことはより深いパイプライニングでも可能だったはずなので、遅延サイクルの制約があったのだろう。
パイプライニングは厄介で、乗算アレイを2つに分割するのにちょうどよい位置がないからだ。
https://github.com/EI2030/Low-power-E-Paper-OS/blob/master/P...
8086: 29,000
386: 275,000
486: 120万
Pentium: 310万
私の記憶では、NSAは2000年以降のどこかの時点でこの分野に参入した。