The ITTAGE indirect branch predictor

2025-07-05

ITTAGE間接分岐予測器

原文は Nelson Elhage により 2025-07-05 に公開されました。このブログを購読する

新しいPython 3.14の末尾呼び出しインタプリタの性能を調査していた際に、（Sam Gross氏による非常に有益なコメントを通じて）私にとっては新しい性能トリビアを知りました。現代のCPUは、従来型のバイトコードインタプリタループ内にあるバイトコードディスパッチの間接ジャンプの予測に、もはやほとんど苦労しないということです。定常状態では、バイトコード自体が十分安定していれば、現代のCPUはたとえ素のwhile / switchスタイルのインタプリタループであっても、非常に高い精度でディスパッチを予測します¹！

興味を惹かれた私は、分岐予測器がどのようにしてこの偉業を成し遂げているのかについて、少し時間をかけて調べてみました。答えはとても興味深いものだったので、私なりの理解に基づいて、その重要な高レベルなポイントを共有してみたいと思います。また、それに関連して浮かんできた興味深いつながりやアイデアについても触れていきます。

ひとつ断っておきます。私はハードウェアエンジニアでもCPU設計者でもなく、ここでは自分が面白いと感じた高レベルなアイデアに焦点を当てます。そのため、間違っている部分もあるかもしれません。実際に詳しい人によるCPUの分岐予測の入門をお求めであれば、Dan Luu氏による記事を参照してください。

TAGEとITTAGE分岐予測器

一般に、現代の最先端CPUは分岐予測器についてあまり詳細を公開していないため、実際の最先端CPUで分岐予測がどうなっているのかは、少なくとも私が簡単に調べた限りではよく分かっていません。しかし、少なくとも1つ、実用的でありながらバイトコードインタプリタループを予測できる公開されたアルゴリズムが存在します。それがITTAGE間接分岐予測器であり、今回の主題です。この予測器の作者は論文でバイトコードインタプリタにおける予測を検証し、自身のITTAGEがIntel Haswell CPUと同等の性能を示したことから、Haswellがその派生版を使っているのではないかと示唆していますが、確かなことは分かっていません。

ITTAGEはTAGE予測器の派生です。TAGEが条件分岐のtaken/not-takenを予測するのに対し、ITTAGEは間接ジャンプの飛び先を予測します。両者の構造は非常に似ているため、この記事の大半では両者をまとめて扱います。

概要

詳しい話に入る前に、これから向かう先を簡単にまとめておきます。TAGEとITTAGEはどちらも次のように動作します。

(PC、PC履歴) -> 過去の挙動というマッピングから分岐の挙動を予測し、未来が過去と同様であることを期待する
履歴長の等比数列を用いて、そのようなテーブルを多数保持する
分岐ごとに適切なテーブル（履歴長）を動的に選択しようとする
予測を外した際にはより長い履歴へ適応的に移行し、慎重な置換ポリシーによって有用なエントリを優先的に保持することでそれを実現する

では、より詳しい話に入りましょう。あるいは、この概要で十分という方は、このトピックを特に面白いと感じる理由や関連する考察へ進んでください。

動的分岐予測の基礎

多くの動的分岐予測アルゴリズムは、単純な前提に基づいて動作します。何らかの形で履歴データのテーブルを保持しておき、分岐を予測する際に「前回」何が起きたかを参照し、同じことが繰り返されると仮定するのです。C++風の疑似コードで考えると、このアプローチは次のようなものとして捉えることができます。

struct BranchDetails {
  // The information we use to identify a branch
};

struct BranchHistory {
  // The information we store about eaach branch

  // Predict the outcome of a branch based on past state
  bool predict() const { /* ... */ };

  // Update our state based on a resolved branch
  void update(bool taken) { /* ... */ };
};

// We store a mapping from one to the other. This is a fixed-size chunk of
// hardware, so it stores a fixed number of entries. We'll talk a bit about
// replacement strategy and some details later on.
using PredictorState = FixedSizeMap<BranchDetails, BranchHistory>;

void on_resolve_branch(PredictorState &pred, BranchDetails &branch, bool taken) {
  pred[branch].update(taken);
}

bool predict_branch(PredictorState &pred, BranchDetails &branch) {
  return pred[branch].predict();
}

では、BranchDetailsやBranchHistoryには何を使うのでしょうか。おそらく最も単純な選択肢 — 初期のCPUの一部で使われていたものです — は、分岐を識別するために分岐アドレスだけを使い、履歴としては1ビットの情報だけを使う方法です。つまり、プログラムテキスト内の分岐命令ごとに状態を追跡するということです。

struct BranchDetails { uintptr_t addr; };
struct BranchHistory {
  bool taken_;

  bool predict() { return taken_; }
  void update(bool taken) { taken_ = taken; }
};

次に単純な戦略では、分岐ごとの状態であるboolを小さなカウンタ（わずか2ビットでも）に置き換えます。これによりヒステリシスを持たせることができます。分岐が解決されるたびにカウンタをインクリメントまたはデクリメントし、その符号を予測に使います。多くの分岐はどちらか一方に強く偏っている — たとえば分岐成立率が50%よりも10%や90%の方が一般的です — ことが分かっており、わずかなヒステリシスでも、たまに現れる外れ値の挙動を吸収しつつ、これまでの学習を忘れずに済むのです。

struct BranchHistory {
  int2_t counter_;

  bool predict() { return counter_ >= 0; }
  void update(bool taken) {
   saturating_increment(&counter_, taken ? 1 : -1);
  }
};

PCだけを超えて

PCで分岐をインデックスするのは単純で効率的ですが、限界もあります。多くの分岐は動的でデータに依存した挙動を示すため、より高い精度を求めるなら、何らかの方法でより細かく区別する必要があります。

分岐予測器はCPUのフロントエンドに存在し、命令が実際に実行される — あるいは完全にデコードされるよりも — はるか前に予測を行わなければならないため、予測に使える他のCPU状態へのアクセスはあまりありません。しかし、実質的に「無料」でアクセスできるコンテキストが1つあります。それは履歴、すなわちプログラムカウンタと直近の分岐の履歴です。なぜなら、予測器自身がそもそもそれらの生成を手伝っているからです！

そこで分岐予測器は、一定サイズの循環バッファを維持し、何らかの形で「分岐履歴」や「PC履歴」をローリングしながら保存し、その状態を使って異なる分岐を区別することができます。最も単純なケースでは、直前の分岐ごとに1ビットを保存し、分岐成立なら「1」、不成立なら「0」と書き込みます。より洗練された予測器では、無条件分岐を含めたり、PC値の数ビットを履歴に書き込んだりすることもあります。

constexpr int history_length = ...;

struct BranchDetails {
  uintptr_t pc;
  bitarray<history_length> history;
}

分岐履歴のサイズをどう決めるか

どの程度の大きさの履歴を使うべきでしょうか。大きければ大きいほど良いのでしょうか。

より長い履歴は、より多くのパターンやより複雑なパターンを学習することを可能にします。プログラムの挙動が安定している場合、定常状態では、より大きな履歴によってプログラムの挙動をより多く学習し、異なる状況をより細かく区別できる可能性があります。

しかし、履歴が長くなると、単純なパターンを学習するのにもテーブルにより多くの空間が必要になり、潜在的により多くの時間もかかります。なぜなら、取りうる状態が増え、それぞれを個別に経験して学習する必要があるからです。次のような単純な関数を想像してみてください。

bool logging_active;

void log(const char *msg) {
  if (logging_active) {
    printf("%s\n", msg);
  }
}

この関数がインライン展開されず、実行ファイル内の多くの異なる場所から呼び出されるとします。

logging_activeが実行時に静的、あるいはほぼ静的であると仮定すると、この分岐は非常に予測しやすいものです。単純なPCのみの予測器でも、ほぼ完璧な精度を達成できるはずです。しかし、分岐履歴も考慮すると、予測器はこの分岐を単一のものとして「見る」ことがなくなります。代わりに、この分岐命令に至るすべてのパスを個別に追跡する必要があります。最悪の場合、kビットの履歴を保存すると、この1つの分岐のために2^k個もの異なるテーブルエントリが必要になるかもしれません。さらに悪いことに、各状態を個別に経験する必要があり、異なるパスから互いに何も「学習」できないのです。

TAGEアルゴリズム：大きなアイデア

これでTAGE予測器の概要を説明するために必要な背景が揃いました。

TAGEはこれまでに説明したように分岐履歴を追跡しますが、より単純な予測器とは異なり、数百ビット、時には数千ビットもの履歴を追跡し、非常に長いスパンにわたるパターンを学習できる可能性があります。

この大量の履歴を状態爆発を起こさずに活用するために、TAGEは複数の履歴テーブル（おそらく10〜20個程度）を保持し、等比数列の履歴長でインデックス付けします（すなわち、テーブルNは履歴長 \( L_n ≈ L_0\cdot{}r^n \)（rは何らかの比率）を使用します）。そしてTAGEは、分岐ごとに、良い予測を行うのに十分な最短の履歴長（および対応するテーブル）を適応的に選択しようとします。

それをどのように行うのでしょうか。以下が中核となるアイデアです（私の理解する限り）。詳細を知りたい方向けに、後ほど論文やコードへのリンクを紹介します！

各テーブルのタグビット

これまで、これらのルックアップテーブルが実際にどのように実装されているか、特に「与えられたキーを持つエントリをルックアップする」ことを具体的にどう実装しているかという問題を完全に省略してきました。

多くの単純な分岐予測器では、履歴テーブルは自身がどのキーを格納しているかを「知らず」、キーの一部のビットに基づいて直接インデックス付けするだけです。

たとえば、PCでインデックス付けされる予測器では、\(2^k\)個のカウンタの配列を持ち、PCの下位\(k\)ビットを使ってエントリを選択するかもしれません。2つの分岐が\(2^k\)で割った余りのアドレスが同じであれば、衝突して同じテーブルエントリを使用することになりますが、衝突を検出したり異なる動作をしたりする努力はしません。この選択によりテーブルは極めて安価で効率的になり、多くの場合において良いトレードオフとなることが分かっています。直感的に言えば、分岐予測器が間違うことはそもそも想定内であり、そのような衝突は間違うもう一つの理由に過ぎません。衝突を検出して対応するには、より多くのハードウェアとストレージが必要になりますが、そのリソースを他の方法でエラー率を下げるために使った方が良いということが分かっているのです。

しかしTAGEは複数のテーブルを保持し、分岐ごとに異なるテーブルを使う必要があるため、あるキーに対してどのテーブルが実際に情報を保持しているのか、衝突したキーなのかを知る必要があります。そこで、他のペイロードに加えて、各テーブルエントリはどのキーがエントリに格納されているかを記述する追加のメタデータであるタグを保持します。

（PC、分岐履歴）のタプルTが与えられたとき、TAGEはテーブルごとに2つの異なるハッシュ関数H_indexとH_tagを使用します。分岐の状態Tは、インデックスH_index(T)の位置にタグ値H_tag(T)とともにテーブルに格納されます。ルックアップ時には、H_index(T)の位置にある値をチェックし、タグをH_tag(T)と比較します。

タグが一致しなければ、このエントリは現在他の分岐に関する情報を格納しており、使用しません（ただし上書きすることはあるかもしれません）
タグが一致すれば、この状態が自分たちの分岐と一致すると見なし、使用・更新します。ただし、依然としてハッシュのみをチェックしているため、両方のハッシュで別の分岐と衝突している可能性もありますが、実際には十分稀になるようにハッシュを設計しサイズを選択します。

このタグビットがTAGEの「TA」の由来であり、「GE」は履歴長の等比数列に由来します。

基本的な予測アルゴリズム

この前提のもとで、TAGEの基本的な予測アルゴリズムはかなり単純です。各テーブルエントリは、上で説明したようなカウンタ（論文ではctrと呼ばれます）を保持します。これは「分岐成立」でインクリメントされ、「不成立」でデクリメントされます。

予測を行うために、TAGEは適切な履歴長を使ってすべてのテーブルをチェックします。一致するタグを持つすべてのテーブルエントリを考慮し、その中で最も長い履歴長に対応する一致エントリからの予測を使用します。

ベース予測器 — 最も単純なケースではPCのみでインデックス付けされるテーブル — はタグビットを使用しないため、常に一致し、より長い履歴で一致するものがなかった場合のフォールバックとして使われます。

予測を外したらより長い履歴へ移行する

分岐が解決して正解が分かると、予測器を更新する必要があります。

TAGEは予測に使用されたエントリのctrフィールドを常に更新します。しかし、予測が間違っていた場合、より長い履歴長を使用するテーブルのいずれかに新しいエントリを割り当てようとも試みます。こうして、うまくいく長さが見つかるまで、動的により長い履歴を試していくことが目標となります。

テーブルエントリの有用性を追跡する

テーブルエントリがタグ付けされているため、新しい分岐のためにテーブルエントリをいつ置き換えて再利用するかを決める方法が必要になります。予測器がうまく機能するためには、将来有用な予測をもたらす可能性が高いエントリを保持し、そうでないものを破棄することを目指します。

その目標を近似するために、TAGEはどのエントリが最近有用であったかを追跡します。タグとカウンタに加えて、各テーブルエントリはu（「有用」）カウンタ（通常はわずか1ビットまたは2ビット）も持ち、そのテーブルが最近有用な予測を生成したかどうかを追跡します。

上で説明したように新しいテーブルエントリを割り当てる際には、u=0のスロットのみを上書きし、新しいスロットはu=0で初期化します。したがって、新しいエントリはその価値を証明しなければ置き換えられるリスクがあります。

uカウンタは、あるテーブルエントリが以下の条件をすべて満たすたびにインクリメントされます。

予測に使用され、
その予測が正しかった、かつ
そのエントリからの予測が、次に長い履歴を持つ一致エントリによる予測と異なっていた

したがって、エントリが正しい予測をもたらすだけでは十分ではありません。反事実的に考えてもしそのエントリがなければ間違っていたであろう正しい予測をもたらす必要があります。

さらに、uカウンタはエントリが永遠に残り続けるのを防ぐために、何らかの形で定期的に減衰（あるいは単にゼロにリセット）されます。正確なアルゴリズムは公開されているバージョン間で大きく異なります。

TAGEからITTAGEへ

ここまでTAGEの挙動について説明してきました。TAGEは条件分岐について1ビットの情報（taken/not-taken）を予測します。間接分岐のターゲットを予測するITTAGE（そもそも私がこのシステムについて書いている理由です！）は、ほぼ同一です。主な変更点は次の2点のみです。

各テーブルエントリが予測されるターゲットアドレスも保持する
ctrカウンタは保持されますが、「信頼度」カウンタになります。「正しい予測」でインクリメントされ、「誤った予測」でデクリメントされます。誤った予測の際には、ctrが最小値にある場合に限り、予測ターゲットを新しい値に更新します。したがって、ctrはこの特定のターゲットアドレスに対する信頼度を追跡し、uは予測器全体の文脈におけるこのエントリ全体の有用性を追跡します。

実際、同じテーブルを組み合わせて、論文では「COTTAGE」と呼ばれる統合予測器にすることもできます（論文参照）。

参考文献

TAGEやITTAGEについて書かれたものはそれほど多く見つかりませんでしたが、興味があって詳細を掘り下げたい方向けに、ここで見つけた最良のリンクを紹介しておきます。これらの論文を読んで特に印象に残ったのは、正しい高レベルなアイデアを持っているだけでは十分ではないということです。高性能なTAGEやITTAGE（あるいはあらゆる分岐予測器）の実装は、優れた設計と、膨大な綿密な調整やトレードオフのバランスの結果なのです。リンクは以下の通りです。

A case for (partially) tagged geometric history length branch prediction: 私の知る限り、これがTAGEとITTAGEを提案した論文です
The L-TAGE Branch Predictor: 2007年の分岐予測コンペティション（「CBP-2」）向けのTAGE実装です。
A 64 Kbytes ISL-TAGE branch predictor: 後継のコンペティションである2011年の「CBP-3」向けの更新版の説明です。
A 64-Kbytes ITTAGE indirect branch predictor: 同じコンペティションの間接分岐部門向けのITTAGE予測器の説明です。
The program for JWAC2, which hosted the CBP-3 competition: CBP-3コンペティションを主催したJWAC2のプログラムで、特にそのコンペティションに提出されたTAGEおよびITTAGE実装のソースコード（マイクロアーキテクチャシミュレータ内）へのリンクが含まれています。
BOOM (Berkeley Out Of Order Machine)’s documentation on their TAGE implementation: BOOM（Berkeley Out Of Order Machine）は、マイクロアーキテクチャ研究向けのオープンソースRISC-Vコアです。

なぜITTAGEが面白いのか

一方で、私がITTAGEを面白いと感じるのは、インタプリタループなどのソフトウェアの性能について考える機会がときどきあり、そうした状況での考え方をアップデートする必要がある重要な事例だからです。非常に具体的に言えば、それは前回のCPythonベンチマークに影響を与えました。

しかし、より広い理由からも魅力を感じており、他の関心分野とのつながりもあります。

私は以前書いた記事で、カバレッジガイド付きファザーやトレーシングJITを含む一群のソフトウェアツールについて触れました。これらのツールは、プログラムカウンタの時間的な挙動を見ることでプログラムの挙動を大まかに理解しようとしますが、プログラムの状態が「データの中に隠れて」おり、制御フローだけでは「興味深い」状態の貧弱な代理にしかならないようなインタプリタなどのソフトウェアでは、関連する形で苦労するという話でした。

その記事ではこのつながりについては書きませんでしたが、私は分岐予測器もこの種のツールの仲間だと常々考えてきました。上で述べたように、分岐予測器もプログラムの実行を主に「一連のプログラムカウンタ値」というレンズを通して理解しており、やはり — 少なくとも歴史的には — インタプリタループではうまく動作するのに苦労してきました。

したがって、ITTAGEとそのインタプリタ挙動の予測における成功について学ぶことは、自然と次の疑問を呼び起こします。ITTAGEアルゴリズムから、他のツールについて学べることはないのだろうか、と。

特に気になっているのは…

カバレッジガイド付きファジングやプログラム状態探索のためのITTAGE？

その以前の記事で概説したように、カバレッジガイド付きファジングは、候補となる入力を生成し、どの入力がプログラムに「新しい」挙動を生成するかを観察することで、対象プログラムの挙動を自動的に探索しようとする手法です。

このループを機能させるためには、プログラムの挙動を特徴付けたりバケット分けしたりする方法が必要で、そうすることで何を「新しい」あるいは「興味深い」挙動とみなし、すでに観察済みの挙動と区別できるようになります。私はこの分野の最新の最前線にはついていけていないことを認めますが、歴史的にはこれは「カバレッジ」的なメトリクスを使って行われてきました。これはPC値、あるいは分岐（本質的には(PC, PC’)ペア）の出現回数を数えるものです。これらのカウントはバケット分けされる可能性があり、実行中に生成された[(PC, bucketed_count)]値のリストによって実行を「フィンガープリント化」します。

このアプローチは実際には驚くほど効果的です。しかし、インタプリタを含む特定の形状のプログラムでは苦労することがあります。そこでは「興味深い」状態がプログラムカウンタや分岐の集合とうまく対応しません。この問題のお気に入りの例示の1つがIJON論文で、いくつかの具体的な問題を示し、人手によるアノテーションを用いてそれらに取り組んでいます。

そこで私の疑問は次の通りです。TAGE/ITTAGEのようなアプローチは、カバレッジガイド付きファザーがインタプリタやインタプリタ的なプログラムの状態空間をより良く探索するのに役立つのではないか、ということです。たとえば、既存のコーパスエントリでTAGEのような予測器を学習させ、予測エラーの率に基づいて候補となる変異を優先することはできないでしょうか。これによりファザーが、たとえばインタプリタにアノテーションを加えるだけで、解釈される言語で書かれたコードの状態空間を効果的に探索できるようになるかもしれません。

多くの実践的な課題はありますが、原理的にはこれにより状態空間のよりニュアンスに富んだ探索が可能になり、長距離の相関やパターンによってのみ識別できる「新しい挙動」を発見できるかもしれません。

TAGE/ITTAGE自体はハードウェアの性能特性やトレードオフを念頭に設計・調整されていることに注意しておきます。ソフトウェアにおける性能の様相は大きく異なるため、もしこのようなアイデアがうまくいくとしても、詳細はかなり異なり、効率的なソフトウェア実装向けに最適化されるでしょう。とはいえ、分岐ごとに履歴長を動的に選択するという中核的なアイデアを借用する余地はあるように思えます。

さらに突飛なアイデアとして、実際のハードウェア分岐予測器を使うというものも考えられます。現代のCPUではハードウェア性能カウンタを通じて分岐予測の精度を観察することができ、既存のサンプルコーパスを実行して分岐予測器を学習させた後、実際のハードウェアの予測ミス数を新規性のシグナルとして観察することが考えられます。このアプローチにも、分岐予測器の不透明さや明示的に制御できないことなど、多くの課題があります。しかし、ソフトウェア予測器よりもはるかに安価になる可能性があるという利点があります。分岐予測器の状態を明示的に公開しているCPU — たとえば「予測器の状態を保存・復元する」操作の形で — が存在するのかどうか、気になるところです。そうしたものがあれば、このアプローチはずっと実現可能になるでしょう。

もしこのような試みを行ったプロジェクトをご存知の方や、実験してみようと思った方がいれば、ぜひ教えてください。

好奇心と強化学習

上記のセクションで概説したように、TAGE/ITTAGEのようなアルゴリズムをファジングに応用する方法についての私の最善の推測は、「予測エラー」を報酬シグナルとして扱い、予測エラーが高い入力に時間を費やすというものです。

そのアイデアについて考えているうちに、ある抽象度ではそれが強化学習の分野における古典的なアイデアであるため、聞き覚えがあることに気づきました！

おそらく最も顕著な例として、2018年にOpenAIは2つの論文で「好奇心駆動学習」に関する手法を発表し、環境からの報酬シグナルがない場合でも探索を促す報酬項を追加することで強化学習を強化する手法を探求しました。2つの論文はアプローチの詳細は異なりますが、基本的なアイデアは共通しています。取るべき行動を決定するポリシーネットワークと並行して、環境の何らかの特徴や行動の結果を予測しようとする予測器ネットワークを学習させます。そして、予測エラーが高い行動や状態を発見したことに対してポリシーモデルに報酬を与えることで、うまくいけば環境の新しい部分の探索が促されるというものです。

私の知る限り、この手法はかなりうまく機能しました。2本目の論文は、強化学習アルゴリズムにとって悪名高く難しいAtariゲームであるMontezuma’s Revengeで最先端の性能を達成しました。このゲームは、スコアを得る前に鍵や装備の広範な探索と操作を必要とするからです。ただし、その研究やアプローチがその後どのような軌跡をたどったのかは、すぐには思い出せません。

私はそれらの論文を認識しており、当時その研究を追っていましたが、「ITTAGE」と「カバレッジガイド付きファジング」のピースを頭の中で組み合わせようとし始めたときには、意識的にそれらを思い出してはいませんでした。この合流は、何かしら得るものがあることを示唆しているように思えます。とはいえ同時に、2025年現在では、カスタム設計・調整された予測アルゴリズムの代わりに、単にニューラルネットを問題に投げ込む方が簡単かもしれません！

各オペコードにディスパッチロジックを複製する「スレッド化」スタイルのインタプリタは、依然として性能向上にはなりますが、古いCPUほどではありません。今日の利点は、主に実行する総命令数、特に分岐数の削減によるものです。詳しくは前回の記事でさらに議論しています。 ↩︎