分岐予測器は、短い履歴相関(直近の局所性)と長い履歴相関(長距離依存)を同時に扱う必要がある。この要請は自然に「複数コンポーネント(複数テーブル)を持つ予測器」を導くが、そこで重要になるのがコンポーネント出力の合成(combining function)である。
adder tree(加算器ツリー)による合成
GEHL / O-GEHL 系は、履歴長の異なる複数テーブルが出力する 符号付きカウンタ値(スコア)を加算し、合計の符号で taken/not-taken を決める。加算を高速に行うため、加算器を木構造に組む(adder tree)。
- 各テーブル TiT_iTi は
ci(signed counter)を返す - 合計 $S = \sum_i c_i$
- $S \ge 0$ なら taken、$S < 0$ なら not-taken
この合成は「重み付き投票」に相当し、履歴長ごとの寄与を統合できる一方、毎予測で複数テーブル参照と加算が必要になる。
O-GEHLの設計観：幾何級数履歴長
O-GEHLは、履歴長を幾何級数(geometric series)で配置する。短い履歴のテーブルに容量を割きつつ、長い履歴相関も取り込めるため、限られたストレージ予算で精度を引き上げる設計になっている。
TAGEの立場：幾何級数履歴長を “タグ付き選択” で使う
TAGE(TAgged GEometric history length)は、幾何級数履歴長という設計観は共有しつつ、合成関数を「加算」ではなく タグ付きテーブルのヒット/ミスによる“選択”へ置き換える。
- T0：タグなしのベース予測器(bimodal)
- T1..TN：タグ付きテーブル群(履歴長は幾何級数)
- 予測は原則として「ヒットした中で最長履歴のテーブル」を採用(ヒット無しならT0)
この枠組みは “PPM-like(最長一致を選択)” と呼ばれる系統に属する。TAGEの論文は、従来PPM-likeタグ予測器の弱点を 更新(update policy)に求め、更新・割当(allocation)を再設計することを重要な貢献としている。
