BHT（ビーエイチティー）
英語表記: BHT (Branch History Table)
概要
BHT（分岐履歴テーブル）は、CPUの制御装置が命令を効率よく処理するために用いる、過去の分岐命令の実行結果を記録した小さなメモリ領域です。これは、コンピュータの処理速度を大きく左右するパイプライン処理において、条件分岐（「もしAならばBを実行せよ」といった命令）が発生した際に、次に実行すべき命令を推測するために不可欠な仕組みです。制御装置がBHTを参照することで、命令の解釈と実行の停止を防ぎ、処理の流れを途切れさせないようにサポートしています。
詳細解説
BHTは、「コンピュータの構成要素」のうち、特に命令の流れを司る「制御装置（命令の解釈と制御信号）」の効率を極限まで高めるための技術、「分岐予測と投機実行」の土台となる重要なデータ構造です。
BHTの目的と制御装置における役割
現代のCPUは、複数の命令を同時に、またはオーバーラップさせて実行するパイプライン処理を採用しています。これにより高いスループットを実現していますが、条件分岐命令に遭遇すると問題が発生します。分岐の結果（次に進むべき命令アドレス）が確定するまで待ってしまうと、パイプラインが停止し、性能が大幅に低下してしまうのです。
この性能低下を防ぐため、制御装置は命令を解釈する段階で、BHTを参照し、「過去の経験」に基づいて分岐の方向を予測します。この予測に基づき、制御装置は、結果が確定する前に後続の命令を先回りして実行します。これが「投機実行（Speculative Execution）」です。BHTは、この投機実行の精度を高めるための「過去のデータ」を提供する役割を担っています。
構成と動作原理
BHTは基本的に、分岐命令のアドレスをインデックス（キー）とし、そのアドレスに対応する「履歴情報」を格納するテーブルです。
- 履歴情報の形式: 最も単純なBHTは、分岐が「取られた (Taken)」か「取られなかった (Not Taken)」かを1ビットで記録します。しかし、ループ処理のように「何回か連続で分岐し、一度だけ分岐しない」といったパターンを正確に捉えるためには、より高度な予測が必要です。
- 飽和カウンタ（Saturation Counter）: 多くの高性能CPUでは、予測精度を高めるために「2ビット飽和カウンタ」が使用されます。これは、00, 01, 10, 11の4つの状態を持ちます。
- 例えば、状態が「11」（強く分岐すると予測）のとき、一度分岐しなかったとしても、すぐには予測を覆さず「10」（やや強く分岐すると予測）に状態が遷移するだけです。これにより、一時的な例外的な挙動に惑わされず、安定した予測を維持できます。
- 予測と更新: 命令が実行フェーズに到達すると、制御装置はまずBHTを参照して予測を行います。実際に分岐の結果が判明した後、その結果に基づいてBHT内の対応するエントリ（履歴カウンタ）を更新します。予測が当たればそのまま処理を続行し、外れた場合は、投機的に実行した命令を破棄し（ロールバック）、正しい経路からパイプラインを再スタートさせます。このペナルティ（ミスペナルティ）を最小限に抑えることが、BHTの最大の目的です。
BHTは、制御装置が命令の解釈を終えた直後、次の命令をフェッチするタイミングで参照されるため、パイプラインの途切れを防ぐ「制御信号」を迅速に生成する上で、欠かせないデータソースとなっているのです。
具体例・活用シーン
BHTの働きを理解するために、日常生活における予測のアナロジーを考えてみましょう。
アナロジー：ベテランの交通整理員
あなたは、交通量の多い交差点の信号機（CPUのパイプライン）の処理をスムーズにするベテランの交通整理員（制御装置）だと想像してください。この交差点には、頻繁に右折（分岐命令）する車線があります。
BHTの役割:
あなたの手元には、過去1時間分の右折車線の利用状況を記録した「履歴ノート」（BHT）があります。
- 履歴の記録: 履歴ノートには、「前回この車が来た時は右折した」「その前は直進した」といった情報が記録されています（履歴カウンタ）。
- 予測: 新しい車が右折車線に近づいてきたとき、あなたは履歴ノートを見て、「この時間帯、この種類の車は9割の確率で右折する」と予測します。
- 投機的行動: 信号がまだ青（分岐結果未確定）であっても、あなたは「どうせ右折するだろう」と確信し、すでに右折後の車線に次の車（次の命令）を誘導し始めます。これが投機実行です。
- 結果と学習: 実際に車が右折した場合（予測成功）、処理はスムーズに進みます。もし直進した場合（予測失敗）、あなたは誘導していた次の車を急いで停止させ、正しい車線に戻すペナルティが発生します。そして、履歴ノートを「今回は直進だった」と更新し、次回の予測に活かします。
この履歴ノート（BHT）がなければ、あなたは毎回信号が完全に変わるまで待つ必要があり、交差点全体が渋滞してしまいます。しかし、BHTがあるおかげで、あなたは高い精度で予測を行い、交通の流れ（命令の流れ）をほぼノンストップで維持できるのです。
活用シーン
- 大規模なループ処理: プログラムコードの中で、
for文やwhile文によるループ処理は、非常に頻繁に分岐が発生します。BHTは、ループが継続している間は「分岐を取る」と正しく予測し続け、最後の1回だけ「分岐を取らない」と予測が外れる、という挙動をサポートします。これにより、ループ全体の実行時間を大幅に短縮できます。 - OSやライブラリの呼び出し: 頻繁に実行されるシステムコールや関数呼び出しの分岐パターンを学習し、予測精度を維持することで、OSレベルでの高速化に貢献しています。
資格試験向けチェックポイント
BHTや分岐予測の概念は、特に基本情報技術者試験や応用情報技術者試験の計算機アーキテクチャ分野で頻出します。
| 試験レベル | 頻出パターンと対策 |
| :— | :— |
| ITパスポート | 直接的な出題は少ないですが、「パイプライン処理」と「投機実行」の関係を理解しておくことが重要です。CPUが命令を効率よく処理するために、予測に基づいて先回りして実行する仕組みがある、という概要を押さえましょう。 |
| 基本情報技術者 | 「パイプライン処理のハザード（障害）」対策として、分岐予測が必要であることを問われます。BHTが「過去の履歴」を基に予測を行うテーブルである、という定義を正確に覚えましょう。また、予測が外れた場合のペナルティ（ミスペナルティ）が発生し、その回復に時間がかかるという事実も重要です。 |
| 応用情報技術者 | より詳細な仕組みが問われます。「制御装置」の高度な機能として、BHTと組み合わせて使用される飽和カウンタ（2ビット予測器）の動作原理が出題されることがあります。2ビットカウンタがどのように履歴を保持し、予測の安定性を高めているかを理解することが求められます。また、BHTとBTB（分岐先バッファ）の違いを明確に区別できるようにしておくと万全です。 |
| 全レベル共通 | この技術は「コンピュータの構成要素」のうち、「制御装置」の性能を向上させるためのものであり、命令の解釈と制御信号の生成を助ける機能である、という文脈を絶対に忘れないようにしてください。 |
関連用語
BHTは単独で使われるよりも、他の予測機構やバッファと組み合わされて、制御装置の性能を最適化するために機能します。
- BTB (Branch Target Buffer): 分岐命令のアドレスと、その分岐命令が取られた場合に次に実行されるべき命令の目標アドレスを格納するバッファです。BHTが「分岐するか否か」を予測するのに対し、BTBは予測が当たった場合に「どこへジャンプするか」を迅速に提供します。
- PHT (Pattern History Table): BHTが単純な履歴情報を保持するのに対し、PHTはグローバルな分岐履歴や、より複雑なパターン認識を行うために使用されるテーブルです。BHTとPHTを組み合わせることで、より高精度な予測器（二段階予測器など）が構築されます。
- 投機実行 (Speculative Execution): 分岐予測が提供する予測結果に基づき、命令の結果が確定する前に、その命令を実際に実行してしまう技術です。予測が外れた場合は、実行結果を破棄します。
- パイプライン処理 (Pipeline Processing): 命令の実行を複数のステージ（命令フェッチ、デコード、実行など）に分割し、異なる命令を同時に異なるステージで処理することで、CPUの処理効率を高める手法です。BHTはこのパイプラインの停止を防ぐために存在します。
関連用語の情報不足
現在、これらの関連用語に関する詳細な情報（定義や動作原理）は、このBHTの記事内には含まれていません。読者がこれらの用語について深く知りたい場合は、それぞれの専門的な記事を参照する必要があります。特に、BTBとPHTはBHTと密接に関連しており、制御装置における分岐予測の全体像を理解するためには、これらの用語の詳細な解説が不可欠であると言えます。
