BHT (Branch History Table)（BHT: ビーエイチティー）

2025年10月23日

BHT (Branch History Table)（BHT: ビーエイチティー）

英語表記: BHT (Branch History Table)

概要

BHT（Branch History Table）は、CPUが命令を効率よく処理するために用いる「分岐予測」を実現する重要な内部テーブルです。このテーブルは、過去に実行された分岐命令の履歴（どの方向に分岐したか）を記録し、次に同じ命令が出現した際に、その履歴に基づいて分岐の方向を予測するために利用されます。これは、CPUの高速化技術であるパイプライン処理において、分岐命令による処理の停滞（ストール）を防ぎ、処理速度を維持するために不可欠な仕組みです。

詳細解説

分岐予測とBHTの役割

私たちが今扱っているテーマは、「CPUの仕組み（命令セット, パイプライン） → 分岐予測と投機実行 → 分岐ターゲット制御」という極めて技術的な文脈にあります。CPUが高速に動作するために採用しているパイプライン処理は、複数の命令を同時に並行して処理する仕組みですが、プログラムには必ず「if文」や「ループ」といった分岐命令が含まれます。

分岐命令に遭遇すると、CPUは次にどの命令を実行すべきか（分岐先の命令アドレス）が確定するまで待たなければなりません。この待ち時間が発生すると、せっかくのパイプライン処理が中断され、性能が大幅に低下してしまいます。これを「ストール」と呼びます。

このストールを回避するために導入されたのが「分岐予測」です。BHTは、この分岐予測の精度を飛躍的に向上させるための鍵となるコンポーネントです。

BHTの構造と動作原理

BHTは、主に分岐命令のアドレス（プログラムカウンタ: PC）の一部をインデックスとして使用し、そのインデックスに対応するエントリに「過去の分岐の結果」を格納しています。格納される情報は、単なる「分岐した」「分岐しなかった」という二値の情報だけでなく、予測の確信度を高めるために「2ビットカウンタ」を用いるのが一般的です。

2ビットカウンタによる確信度管理

2ビットカウンタは、00から11までの4つの状態を持ちます。

00（強く分岐しないと予測）: 過去に連続して分岐しなかった履歴がある。
01（弱く分岐しないと予測）: 直近で分岐しなかったが、次は分岐する可能性もある。
10（弱く分岐すると予測）: 直近で分岐したが、次は分岐しない可能性もある。
11（強く分岐すると予測）: 過去に連続して分岐した履歴がある。

分岐命令に遭遇した際、CPUはPCアドレスを使ってBHTを参照し、この2ビットカウンタの値を確認します。例えば、値が11であれば「強く分岐する」と予測し、実際の分岐結果がどうなるかを待たずに、予測に基づいて次の命令の実行を先に開始（投機実行）します。

BHTと分岐ターゲット制御

BHTは「分岐するかどうか（方向）」の予測を担いますが、この情報だけでは次に実行すべき命令の「アドレス（ターゲット）」はわかりません。ここで、BHTはBTB（Branch Target Buffer：分岐ターゲットバッファ）と連携します。

BTBが「この分岐命令は、過去にこのアドレス（ターゲット）にジャンプした」という情報を保持しているのに対し、BHTは「この分岐命令は、過去にこの方向に進んだ」という履歴を提供します。

BHTが「分岐する」と予測した場合、CPUはBTBを参照して、予測されたターゲットアドレスを取得し、そのアドレスから命令の読み込みを開始します。このように、BHTは分岐の方向を予測することで、BTBが提供するターゲットアドレスが有効であるかどうかを判断し、結果として「分岐ターゲット制御」の精度と効率を大幅に高めているのです。この連携こそが、現代の高性能CPUの根幹を支えていると言えるでしょう。

具体例・活用シーン

BHTの役割を理解するためには、私たちの日常の意思決定プロセスに置き換えて考えると非常にわかりやすいです。

アナロジー：常連のレストランでの注文

あなたが週に3回通う定食屋を想像してください。

分岐命令（今日の注文）: 店に入り、メニューを見ます。「今日は何にしようかな？」という決定が分岐命令です。
BHT（あなたの過去の履歴）: 店員さんはあなたの常連としての履歴を暗黙的に覚えています。過去10回のうち9回は「カツカレー」を注文しています。BHTはこの「カツカレーを注文する」という強い履歴（例えば2ビットカウンタが11の状態）を保持しているのと同じです。
分岐予測（店員の行動）: 店員さんはあなたが席に着くやいなや、「いつものカツカレーですね！」と確認することなく、調理場に「カツカレー」のオーダーを通します（投機実行）。
分岐ターゲット制御（実際の料理）: もしあなたが本当にカツカレーを注文した場合、料理はすでに準備段階に入っているため、待ち時間がほとんどなく提供されます。もし「今日は日替わり定食にする」と予測が外れた場合（ミス予測）、店員さんはすぐに調理をストップし、日替わり定食の調理を始めます（パイプラインのフラッシュ）。

この例では、BHTが提供する「強い履歴」のおかげで、店員（CPU）は待ち時間（ストール）を最小限に抑えることができています。CPU内のループ処理（例えば、100回繰り返される計算）は、まさにこの「常連客の注文」と同じで、BHTが「今回もループするだろう」と予測し続けることで、命令の先読みが途切れることなく高速に実行されるのです。

活用シーン：大規模なデータ処理

大規模なデータ処理やAI処理では、非常に多くの条件分岐や繰り返し処理が発生します。BHTの予測精度が高いほど、これらの処理におけるパイプラインのストールが減少し、結果としてアプリケーション全体の実行速度が向上します。特に、現代のマルチコアCPUでは、BHTの設計と実装が、チップ全体の性能を決定づける重要な要素となっています。高性能なゲーミングPCやサーバーCPUが誇る処理速度は、このBHTをはじめとする分岐予測技術の進化の上に成り立っていると言えるでしょう。

資格試験向けチェックポイント

IT資格試験、特に基本情報技術者試験や応用情報技術者試験では、CPUの構造と性能に関する問題が頻出します。BHTに関する知識は、CPUの高速化メカニズムを理解しているかを確認する上で非常に重要です。

パイプライン処理との関係: BHTの最大の目的は、パイプライン処理の効率を最大化し、分岐命令によるストール（パイプラインの停止）を回避することです。この目的を必ず覚えておきましょう。
分岐予測の手段: BHTは「分岐の方向（取った経路）」の履歴を保持し、予測を行うテーブルであると理解してください。単に「予測」するだけでなく、「履歴に基づいた予測」であることがポイントです。
BTBとの区別: BHTは分岐の方向（する/しない）を予測しますが、BTB（Branch Target Buffer）は「分岐先の命令アドレス（ターゲット）」を保持します。両者は密接に連携しますが、役割が異なるため、試験で問われた際に混同しないように注意が必要です。
投機実行（Speculative Execution）: BHTによる予測が成功した場合、CPUは予測された命令を「投機的に」実行します。予測が外れた場合は、その投機実行の結果を破棄する（パイプラインをフラッシュする）処理が発生することも、関連知識として重要です。
2ビットカウンタの理解: 予測の確信度を高めるために2ビットカウンタが使用される仕組みは、知識として押さえておくと、より深い理解を示すことができます。