- 1993年に登場した Pentium は、Intel 486より高速な浮動小数点除算のためにSRT方式を採用したが、1994年にFDIV命令の誤りが公表されると、Intelはすべての欠陥チップの交換に同意し、費用は 4億7,500万ドル に達した
- 欠陥は除算用 ルックアップテーブル を実装したPLAにあり、Intelはスクリプトのミスで5項目が抜け落ちたと説明したが、ダイ解析では16項目の欠落と、そのうち5項目が実際の誤動作を引き起こしていたことが示された
- radix-4 SRT除算 は1段階で商2ビットを生成できるため高速だが、部分剰余と除数を2048個のP-Dテーブルに対応付けたうえで112行のPLAに圧縮する複雑な構造を持つ
- 根本原因はcarry-save adderのために参照インデックスが実際の部分剰余より1セル低くなる可能性があるのに、Intelが +2 領域の上限境界に誤った数学的補正を適用し、一部セルを 0 のまま残したことにあった
- 修正版Pentiumは欠けていた5項目だけを埋めたのではなく、未使用のテーブル領域をすべて 2 で埋めて境界を単純化し、PLAの使用行数も120行中74行へ減って、欠陥版PLAより約1/3小さくなった
FDIVバグが公になった経緯とコスト
- Intelは1993年に高性能 Pentium プロセッサを発売し、従来のIntel 486より高速な浮動小数点除算アルゴリズムを搭載した
- 1994年5月、Intelの社内テストでPentiumの浮動小数点除算がごくまれに不正確になることが判明した
- Intelは90億回に1回程度しか問題を起こさないとして軽微な問題と判断した
- それでもPentiumの回路はひそかに修正された
- 1994年10月、Thomas Nicely教授は双子素数の逆数を研究している最中に誤った計算結果を発見した
1/824633702441 の計算が別々のPentiumコンピュータ3台で誤っており、以前のコンピュータでは正しい答えが得られた- Intelの技術サポートから十分な対応を得られなかったため、Nicelyはコンピュータ雑誌や個人に電子メールを送った
- このメールはCompuserveフォーラムに掲載され、Electronic Engineering Times は11月7日に Intel fixes a Pentium FPU glitch を掲載した
- 当初Intelは、精度が必要だとエンジニアを説得した顧客にのみ交換を提供しようとし、ユーザーはcomp.sys.intelのようなオンライン掲示板で不満を表明した
- 11月22日のCNN報道後に一般の関心が高まり、12月12日にIBMがPentium搭載コンピュータの出荷停止を発表して事態は悪化した
- Intelは12月19日、すべての顧客に欠陥チップを交換すると発表した
- リコール費用は 4億7,500万ドル
- 現在の価値では10億ドルを超える額である
Pentiumが採用したSRT除算
- 一般的な2進長除算は、商の各ビットごとに1クロック必要なため遅い
- Intel 486やそれ以前のプロセッサはこの方式を使っていた
- Pentiumは SRT アルゴリズムをradix-4、つまり2ビット単位で使用した
- 1段階で商を2ビット生成するため、通常の2進除算より2倍高速である
- 各商桁の値は
-2, -1, 0, 1, 2 のいずれかになる
- SRTは負の商桁値を許容するため、ある段階で少し大きい値を選んでも、次の段階で負の桁値によって補正できる
- 商桁値は厳密に1つへ決定される必要がないため、ルックアップテーブル で高速に選択できる
- 部分剰余と除数の一部ビットだけを使うことで、テーブルサイズを実用的な範囲に抑える
- この方式は高速だが、ルックアップテーブル、
1 または 2 倍を加減算する回路、標準的な商表現へ変換する回路が追加で必要になる
2048項目のテーブルを112行PLAに圧縮した構造
- PentiumのSRTルックアップテーブルは、部分剰余
p と除数 d を入力として受け取り、適切な商桁値を出力する
- テーブルは 2048項目 で構成される
- 除数は1から2の間にスケーリングされ、X軸座標となる
- 部分剰余は-8から8の間の値で、Y軸座標となる
- 除数は
1.dddd のうち、先頭の常に1であるビットを除いた4ビットが使われる
- 部分剰余は7ビットのsigned値
pppp.ppp に切り詰められる
- 合計11ビットのインデックスで
2^11 = 2048 項目を指す
- テーブルには商桁値
+2, +1, 0, -1, -2 に対応する5つの領域がある
- 上下の一部領域はSRTの数学上、使用されない
- 元の欠陥テーブルでは未使用項目が0で埋められていた
- 問題となった5つの赤い項目は
+2 であるべきだったが、0のまま残っていた
- PentiumはこのテーブルをROMではなく PLA(Programmable Logic Array) で実装していた
- テーブル全体をROMで保存すると2048行が必要になる
- テーブル構造に規則性があり空白領域も多いため、PLAでは112行だけで済んだ
- PLAはAND planeとOR planeから構成される
- AND planeは入力ビットとその補数ビットの組み合わせから論理項を生成する
- OR planeはそれらの項を合成して、商が
1 か 2 かを示す出力ビットを作る
- 顕微鏡でPLAのトランジスタパターンを抽出すると、各PLA行の論理式を復元できる
- PLA行はテーブルの1マスではなく、複数マスを一度に覆う長方形領域のように働く
- 特定のテーブル境界がギザギザしているほど、より多くのPLA行が必要になる
数学的境界と誤った +2 領域
- SRT除算の核心となる段階は、部分剰余
p を除数 d で割った比 p/d に基づいて商桁値 q を選ぶことだ
p/d の許容範囲は数学的理由から [-8/3, 8/3] の中になければならない
- 商桁値を選んだ後、
q*d を引いて4を掛け、次段階の部分剰余を作る
- この過程を繰り返せるためには、新しい範囲が元の範囲と同じ大きさである必要がある
- SRTには冗長性があるため、一部区間では2つの商桁値のどちらかを選べる
- しかし
q=2 でなければならない場所で 0 を選ぶと、次の部分剰余が許容範囲の外に出て、アルゴリズムが回復できなくなる
- FDIVバグはこのケースに該当する
- PentiumのP-Dテーブルは、この数学的境界をセル単位に量子化したものである
- 対角線の境界によって、どのセルが必ず
+2 か、+1 または +2 でもよいか、必ず +1 かなどが決まる
- ダイ解析の結果、欠陥テーブル上部の magentaの境界線 は本来、黒い数学的境界線より上になければならないのに、繰り返しその線を横切っていた
- その結果、必ず
+2 であるべき一部セルが0のまま残った
- これらのセルがFDIVバグを引き起こした欠落項目である
carry-save adderがエラーをまれだが致命的にした仕組み
- Pentiumの除算回路は加算と減算を高速化するために carry-save adder を使用していた
- carry-save adderは桁上がりを即座に伝播させず、別のワードに保持するため、複数回の加算が必要な除算に有利である
- 最後には保持した桁上がりを合成するための遅い加算が必要になる
- ルックアップテーブルのインデックスには部分剰余が必要だが、carry-save adderは部分剰余をsumビットとcarryビットに分けて保持する
- Pentiumはテーブルインデックスに必要な7ビットだけを高速に計算するため、carry-lookahead adder を使用した
- この回路は各桁のcarryを並列に計算する
- 大きなワードには複雑すぎるが、7ビット値には実用的である
- 問題は、部分剰余が64ビットなのに対し、テーブルインデックス計算では7ビットしか使わない点にあった
- 残りのビットが合算前に切り捨てられることで、インデックス用の部分剰余が実際の値よりわずかに低くなることがある
- 具体的には、正しいセルより1つ下のセル、つまり
1/8 のオフセットが生じうる
- この効果により、一部の境界線は下方向へ
1/8 移動させる必要があるが、すべての境界線が移動してよいわけではない
- 上側の
+2 境界は下げてはならないのに、Intelはこれを誤って下げたテーブルを生成した
- このcarry-save効果は、当時のSRT除算に関する論文でも言及されていた既知の現象だった
Intelの説明とダイ解析が食い違う点
- Intelのホワイトペーパーは、テーブルをPLAへ入れるスクリプトに問題があり、いくつかの項目がPLAから欠落したと説明している
- IntelはこれをProgrammable Lookup Arrayと呼んだが、実際の構造はProgrammable Logic Arrayである
- ダイ解析では、欠落項目は単純なコピー漏れよりも 数学的境界の誤り と整合しているとみられる
- テーブル生成プログラムが境界条件を誤って定義していた可能性がある
- 「スクリプト」という表現は、Cプログラムでテーブルを生成していたという意味では技術的に正しいかもしれないが、問題の本質は誤った数学的境界にあるという解釈だ
- Robert Colwellの The Pentium Chronicles は別の説明を提示している
- Pentiumの設計はもともと486と同じルックアップテーブルを使っており、発売直前にダイ面積節約の圧力で最適化する中でエラーが生じた、という説明である
- この説明には合わない点がある
- Pentiumは最初から486とは異なる除算アルゴリズムを使用している
- Pentiumはradix-4 SRTを使い、486は標準的な2進除算を使う
- 486には該当するルックアップテーブルが存在しない
- 欠陥PLAには8本の未使用行が残っており、単に回路を減らしたかっただけなら、まずそれらの行を削除できたはずである
修正版PLAがさらに小さくなった理由
- 当時の報道では、Intelは欠陥修正のためにPLAへ数十個のトランジスタや追加のgate sequenceを加えたと伝えられた
- ダイで確認された修正版PLAは、むしろ正反対の姿を示している
- PLAサイズは元と同じである
- およそ1/3の項が削除されている
- 120行のうち74行だけが使われ、残り46行は空いている
- 元の欠陥PLAで空いていた行は8行だった
- Intelの修正は、欠けていた5項目だけを
2 で埋めたものではない
- 未使用だったテーブル項目全体を 2 で埋めた
- これにより、誤って空項目へアクセスする可能性がなくなった
- 未使用領域を2で埋めると、テーブル境界は単純化される
- ギザギザの境界は多くのPLA項を必要とする
- 大きな長方形領域は1つのPLA項で覆える
- そのため、より多くのテーブルセルを埋めたにもかかわらず、PLAの論理式はむしろ単純になった
- 修正版PLAの論理項は元のPLAと完全に異なるため、どのトランジスタ数個がバグを修正したのかを特定するのは難しい
実際の影響と論争
- ランダムな除算で欠陥が発生する確率は約 90億分の1 と非常に低い
- 誤った除算結果も通常は小数第9位または第10位で差が出る程度である
- まれな最悪ケースでは、有効数字4桁目で誤差が生じる
- Intelのホワイトペーパーでは、一般ユーザーが問題に遭遇する可能性は2万7,000年に1回と見積もられていた
- 大半のユーザーには問題にならず、科学・工学や金融工学の一部利用者には修正版プロセッサまたはソフトウェア回避策が必要になる可能性があるとされた
- IBMは独自分析で、顧客が数日おきに問題を経験しうると判断し、Pentiumの販売を停止した
- IBMは当時、競合プロセッサのPowerPCも持っていた
- 分析上、実使用でバグを発見した人物はNicely教授1人だけだったように見える、という評価もある
- IBMの分析は、エラーを誘発しやすい数字を意図的に選んだ面があるとも評価される
- ほとんどのユーザーはバグに遭遇せず、遭遇しても小さな浮動小数点精度低下が問題にならない可能性が高い
- それでもFDIVバグは 決定的 に再現する
- 特定の被除数と除数が問題を起こすと、100%誤った結果になる
- 顧客が自分のコンピュータ上で簡単に再現できたため、Intelが「絶対に遭遇しない問題」だと主張するのは難しかった
その後のプロセッサバグとパッチ可能なマイクロコード
- FDIVバグは最も有名なプロセッサバグの1つだが、Intelには他にも重要なバグがあった
- 初期の386の一部プロセッサには32ビット乗算の問題があった
- 特定の温度、電圧、周波数条件で予測不能な誤結果を出した
- 原因は電気的マージンが不足したレイアウト問題だった
- Intelは欠陥チップを16ビット市場向けに限定して販売し、
16 BIT S/W ONLY と表示した
- Pentiumの別の問題として、1997年に発見された F00F bug がある
F0 0F で始まる特定の命令シーケンスが、再起動するまでプロセッサを停止させた- オペレーティングシステムの更新で解決された
- PentiumのマイクロコードはROMにハードコードされていたため、FDIVバグをマイクロコード更新で修正することはできなかった
- Intelは1995年のPentium Proでパッチ可能なマイクロコードを追加した
- 当初の目的はチップのデバッグとテストだった
- FDIVバグの後、バグ修正にも価値があることが明らかになった
- Pentium ProはROMマイクロコードに加えて、最大60個のマイクロ命令を格納できるSRAMを備え、起動中にBIOSがパッチを読み込める
- 現代のIntelプロセッサのマイクロコードパッチは、Spectre 脆弱性から 電圧問題 まで、さまざまな問題に使われている
複雑化した回路が生んだ失敗
- ムーアの法則に従ってプロセッサのトランジスタ数が増えるにつれ、回路とアルゴリズムも複雑化していった
- 除算支援の変化は、そのことをよく示している
- Intel 8080は1974年に6000個のトランジスタを使い、ハードウェア除算や浮動小数点演算をサポートしていなかった
- Intel 8086は1978年に2万9000個のトランジスタを使い、整数除算はマイクロコードで実装していたが、浮動小数点には8087補助プロセッサが必要だった
- Intel 486は1989年に120万個のトランジスタで浮動小数点機能をチップへ統合した
- Pentiumは1993年に310万個のトランジスタで、より高速だが複雑なSRT除算アルゴリズムを採用した
- Pentiumの除算PLAだけでも約 4900個のトランジスタサイト を持つ
- これはMOS Technology 6502プロセッサ全体より多い
- Pentiumの除算回路の一構成要素だけで、1975年のプロセッサ全体より多くのトランジスタを使っていたことになる
- FDIVバグの長期的影響については議論がある
- AMDのような競合は、Pentium問題を揶揄する広告で利益を得た
- Robert Colwellは、FDIVバグがPentiumという名前の認知度を大きく高め、Intelがそのブランドを支えることを示したため、純効果はむしろプラスだった可能性があると見ている
- IntelはFDIVバグを乗り切ったが、この欠陥は、複雑な数学、回路圧縮、検証限界が重なると、極めてまれなエラーでも大きな信頼問題へ発展しうることを示した
1件のコメント
Hacker News のコメント
著者です。Pentium に関する質問があれば答えられます :-)
このバグについての Mastodon スレッドが数週間前に HN に上がっていたので見覚えがあるかもしれませんが、いまは詳しいブログ記事を書き上げました。以前の HN 投稿にもかなりコメントがあります: https://news.ycombinator.com/item?id=42391079
Intel 内部にももっと深刻なエラーはありましたし、他社にもありましたが、そうしたものは完全に忘れ去られています。Pentium の浮動小数点ユニットの値スタック、正確な名称は分かりませんが、その再設計が気になります。昔の話ですが、初期形態の レジスタ・リネーミング(register renaming) のようなことをしていて、
fxchgを注意深く手動で管理しなければならなかったのではないでしょうか？マイクロコードをビットストリームとして「ダンプ」するのはどれほど難しいのでしょうか？ 高解像度のダイ写真からプログラムで可能でしょうか？ もちろん、そのビットストリームが何を意味するのかをリバースエンジニアリングする作業に比べれば、それは簡単な部類かもしれません
「顕微鏡で PLA を注意深く調べた」という部分も気になります。こうした作業は自宅でやっているのか、研究室にはどんな機材があるのか、こうした技術をどう身につけたのか知りたいです
振り返ると、ルックアップテーブルの未使用部分を最初から 2 と -2 で埋めておかなかった理由が気になります
バグ自体も面白いですが、Intel の対応もそれ自体として興味深いです。望んだ全員に欠陥のないプロセッサへ交換したわけではなかったようで、その結果、ものすごい悪評を受けました
比較すると Amazon Colorsoft の発売をよく思い出します。一部の端末、私の端末も含めて黄色い帯の表示問題がありましたが、Amazon は1日か2日ほど事実関係を確認したあと認め、その後は静かに全品交換してくれました。リコールではなく、依頼すれば新品を送ってくれます。私の交換品は金曜日に届く予定で、解決していることを願っています。発売でつまずいたとき、返品/サポート体制が非常にしっかりしていることは、分析で予想するよりはるかに大きな利点であるのは明らかに思えます
同じように、数年前の Apple AirPods Pro のノイズ問題も、最近はそれほど大きく報道されませんでした。私の AirPods は2回交換する必要がありましたが、Apple も静かに交換してくれました。サポート能力は表には見えにくいものの、かなり強力に機能しているという印象でした
Colorsoft: https://www.tomsguide.com/tablets/e-readers/amazon-kindle-co...
AirPods Pro: https://support.apple.com/airpods-pro-service-program-sound-...
Apple 側では、iPhone 4 アンテナゲートの方がよりよい比較対象です。そこで同等の解決策は、売上の中核であるフラッグシップ製品を無料交換することだったはずですが、Apple はそうしませんでした
一方 Intel は、最終的には希望した誰にでも無料交換を提供し、大きな財務的打撃を受け入れました
そのように製品に責任を持つ Apple の姿勢は、本当に尊敬に値するものでした
コンシューマ向け Apple の「影の保証」のような状況を経験しているので言いたいことは分かりますが、Intel が直面した IT 危機とは非常に異なっていたと思います。当時は「IBM がそう言った」という言葉が IT の世界でとてつもない重みを持っていました
Intelのホワイトペーパーでは、一般ユーザーがこの問題に遭遇するのは27,000年に1回で、DRAMのビット反転のような他のエラー原因に比べれば無視できるものだとしていた。一方でIBMは、自社の分析で顧客が数日ごとに遭遇し得ると見ていた。
この2つの数字は、見た目ほど大きく離れていないのかもしれない。Intelは単一ユーザーを基準に見ていたようで、IBMはサポート問い合わせの観点で考えていた可能性がある。
職場で似たような問題を経験した。1日に1億リクエストを処理すると、10億分の1の問題でも月に数回は発生する。顧客、あるいはもっと悪ければ管理者が気づく類いのものなら、人々は分母を無視して、全員が無能なのではないかと疑う。月4回は、人間の経験バイアスの中では「いつも」に翻訳され得る。週3回の統計的なクラスターが2度起きれば、誰かは爆発する。
さらに、人々が使う数値はIntelの一様分布の数値よりもエラーを引き起こす可能性が90倍高いと見ていた。そのため、ユーザー1人が24日ごとにエラーを経験するという結果になった。
「実使用中にこのバグに気づいた人は1人、Nicely教授だけのようだ」というくだりがある。
昔、学生に数学の授業用の電卓を配った研究を思い出す。その電卓は誤った結果を出すように細工されていて、研究者たちは、学生が異常に気づくには電卓がどれほど間違っていなければならないかを知りたがっていた。
答えは2倍だった。
エラーに気づくことと、エラーの影響を受けることはまったく別の話だ。コンピューターの出力が正しいか確認する人がどれほどいるだろうか。ものすごく、ものすごく、ものすごく少ないと思う。私もBoeingで工学計算をしていたとき、出力が入力と合っているか確認するために方程式を逆向きに回した1件を除けば、やっていなかった。
結局のところ、文脈と、計算している人が内容をどれだけ理解しているかに大きく左右される。
PentiumでFDIVを使っていたもののうち、マルチメディアではなく数値的に重要な出力のためだった部分はどれほどあったのだろうか。
そのバグは覚えている。顧客がどのCPUで実行するかを制御できなかったので、ライブラリに欠陥のあるFPU検出コードを入れ、回避コードを実行しなければならなかった。このコードはIntelが提供していた。
つまりIntelの問題が私の問題になったということだ、うう。
当時出回っていたジョークを思い出す。90年代のいろいろな空気をよく捉えていた。
I AM PENTIUM OF BORG.
DIVISION IS FUTILE.
YOU WILL BE APPROXIMATED.
Kenによるまた別の素晴らしい記事だ。特に記憶に残っているのは、自分のお金で買った初めてのPCに、影響を受けるCPUが入っていたからだ。それ以前は、PCは「本物の」ソフトウェアを動かせなかったので、あまり関心がなかった。
だがWindows NTがそれを変えた。Cutlerには感謝している。台湾製の安価なマザーボードのおかげで、自分でマシンを組み立てることも現実的になり、今でも多くの人がそうしている。Kenは、ユーザーが自分のCPUが影響を受けているかを確認しやすかった点を指摘していた。Excelに魔法の数字を含む除算式を入力するくらい簡単だったと記憶している。Microsoftがバグを回避するExcel版を出していたら、交換を請求したユーザーはもっと少なかったと思う。
興味深く、本当に粘り強い分析だ。シリコンを分析して結果を共有した努力はすごい。特に、IntelのPRは実際の原因を些細な漏れのように聞こえさせていたが、記事では実際の根本原因を突き止めている点がよかった。
実際には、はるかに許しがたく、より非難されるべき問題だった。テーブル生成アルゴリズムを台無しにしていたのだから。
「Smithはそのメールを1990年代版のソーシャルメディアであるCompuserveフォーラムに投稿した」という文は、妙な気分にさせる。
修正後のテーブルは、範囲外の値を0で返す回路を追加せず、単に2を返すようにして、はるかに単純になっていた。だとすると、なぜ最初からそうしなかったのか気になる。
テーブルを生成した人は、範囲外を2で埋めればより単純なPLAになることを知らず、テーブルをPLAに押し込んだ人は、0が**ドントケア値（don't care）**だと知らず、保持しなければならないと仮定したのかもしれない。
あるいは、PLAが必要なだけ小さくなったと感じた瞬間に最適化を止めたのかもしれない。すでに配置計画を終えていたなら、PLAをさらに小さくしてもチップ全体が小さくなるわけではなかっただろうし、エンジニアリング時間は別の場所に使うほうがよかったはずだ。
ほとんどのソフトウェアと同じように、期限内に誰も思いつかなかったために残された最適化があったということだ。そしてこの時代のCPUはパッチを当てられなかった。