TAGE系分岐予測器のTAGEではない部分に関するメモ

（主にAndré Seznec氏が開発している）TAGE系分岐予測器は、TAGE部分以外の工夫にいろいろなバリエーションがあります。 しかしそれらは謎の短い略語で区別されており、覚えるのが困難です。 それに関するまとめのメモです。

cbp1（2004/12/5, 37th MICRO併設ワークショップ）

André Seznec氏はOGEHL分岐予測器を、Pierre Michaud氏はPPM-like分岐予測器を、それぞれ提出しました。 OGEHL分岐予測器は、GEHLパーセプトロン分岐予測器（hashed perceptron分岐予測器）の改良です。 GEHLは、GEometric History Length（幾何級数的履歴長）の略です。 PPM-like分岐予測器は、予測アルゴリズムがTAGE分岐予測器とほぼ同じで、学習アルゴリズムが微妙に異なるものです。 OGEHL分岐予測器は2位、PPM-like分岐予測器は5位でした。

cbp1の後

cbp1開催後にAndré Seznec氏とPierre Michaud氏が共著でTAGE分岐予測器を提案しています (2006年2月、JILP vol. 8)。

この提案されたTAGE分岐予測器は、cbp1の公開データセットで最もいい性能を示す分岐予測器（これはOGEHL分岐予測器なのですが）を上回る性能を示しました。 これがTAGE分岐予測器の原点となります。

この論文では、TAGE, ITTAGE, COTTAGEを提案しています。 ITTAGEはIndirect Target TAGEの略で、間接分岐予測器です。 COTTAGEはCOnditional and indirect Target TAGEの略で、TAGEとITTAGEを統合した分岐予測器です。 この時点でUSE_ALT_ON_NA（最近確保された(newly allocated)エントリの提供する予測を使うくらいなら第二最長一致に基づく予測(altpred)をしたほうが良いかを判断する超単純メタ予測器）が含まれています。

cbp2（2006/12/9, 39th MICRO併設ワークショップ）

今見たらウェブページが死んでいました。

André Seznec氏は現実的部門にL-TAGE分岐予測器を、非現実的部門にGTL分岐予測器を、それぞれ提出し、どちらの部門でも優勝しました。

L-TAGE分岐予測器は、TAGE分岐予測器に"L"を加えたものです。 ここで、"L"はループ予測器を意味します。 ※"L"はローカル予測器の一種です。ローカル予測器は禁忌です。

GTL分岐予測器は、GEHLパーセプトロンとTAGEのハイブリッド分岐予測器に、"L"を加えた分岐予測器です。 つまり、以下からなります。

  • GEHLパーセプトロン分岐予測器
  • TAGE分岐予測器
  • どちらを選ぶべきかを予測するメタ予測器
  • "L"（"L"は予測の確信度を同時に出力するので、メタ予測器は不要です）

cbp3（2011/6/4, 38th ISCA併設ワークショップ）

André Seznec氏は方向分岐予測部門にISL-TAGE分岐予測器を、間接分岐予測部門にITTAGE間接分岐予測器を、それぞれ提出し、どちらの部門でも優勝しました。

ISL-TAGE分岐予測器は、TAGE分岐予測器に"I"と"S"と"L"を加えたものです。 ここで、"I"はImmediate Update Mimickerで、"S"はStatistical Corrector予測器で、"L"は前と変わらずループ予測器です。 Immediate Update Mimickerは、まだ解決していない予測の情報を取り込むためのものです（他の分岐予測の大会ではそもそも一瞬で学習が行われるので不要だと思います。この大会はちゃんとパイプラインをシミュレーションしていたっぽいです）。 Statistical Corrector（統計的補正）予測器は、分岐履歴とあまり強い相関がない分岐への対処です。 TAGE分岐予測器は最長一致を採用するため、分岐履歴とあまり強い相関がない場合には予測ミスが多く発生します。 これに対しては長めのカウンタを使ってどの方向の頻度が高いかの統計的情報を収集するのがよく、それを実現するのが統計的補正予測器です。 統計的補正予測器は短めの分岐履歴を使うGEHLパーセプトロン分岐予測器であり、TAGE分岐予測器の予測に強く反対した（パーセプトロンの出力の和の絶対値が大きい）場合にのみその予測が採用されます。 パーセプトロンなので、いろいろな他の情報を取り込むことが簡単にできます。 ISL-TAGEではTAGE分岐予測器で予測に使われたエントリの3bitカウンタの値を正規化した後8倍してパーセプトロンの和に算入しています。 また、バンクインタリーブが導入されています。

ITTAGE間接分岐予測器は、2006年に提案されたものとほぼ同じです。 "I"とバンクインタリーブが導入されているほか、分岐先の上位ビット（あまり種類がない）を別のテーブルに覚える容量最適化(region table)を行っています。

cbp3の後

André Seznec氏はTAGE-LSC分岐予測器を提案しました（2011/12/5, 44th MICRO）。 ここで、"LSC"はLocal history Statistical Corrector予測器で、短めのローカル分岐履歴を使うGEHL(LGEHL)パーセプトロン分岐予測器です。※禁忌です

よく読んでいませんが、あとは大体ISL-TAGEと同じだと思います。

cbp4（2014/6/14, 41th ISCA併設ワークショップ）

André Seznec氏は現実的部門と非現実部門にTAGE-SC-L分岐予測器を提出しました。 また、Pierre Michaud氏は非現実的部門にFive poTAGEs and a COLT分岐予測器を提出しました。 さらに、André Seznec氏とPierre Michaud氏は共著で非現実的部門にMulti-poTAGE+SC分岐予測器を提出しました。 なお、Jorge Albericio氏、Joshua San Miguel氏、Natalie Enright Jerger氏、Andreas Moshovos氏は共著で現実的部門と非現実部門にWormhole予測器を提出しました（正確には、提出したのはISL-TAGE + Wormholeです。Wormhole予測器は、Loop予測器と同様に、TAGEの出力を上書きするタイプの予測器です）。

現実的部門の優勝はTAGE-SC-L分岐予測器、非現実的部門の優勝はMulti-poTAGE+SCでした。

TAGE-SC-L分岐予測器は、TAGE分岐予測器に"SC"と"L"を加えたものです。 ここで、"L"は今までと同じくループ予測器であり、"SC"はグローバル履歴もローカル履歴も使うようにしたStatistical Corrector予測器です。※どちらも禁忌です

"SC"はなんでもかんでも突っ込んでいるので、よくわかりませんが、いい感じの予測をするようです。 また、TAGEの出力の確信度とSCの出力の確信度の比較にも工夫が入りました。

残りの説明しないといけない謎の略語は、"po"と"COLT"です。

"COLT"は、Combined Output Lookup Tableの略で、ハイブリッド予測器のメタ予測器に変わる由緒正しい方法（2002/9/25, PACT2002）です。 この方法は、予測器がN個あるとき、2Nエントリの予測テーブルにそれを入力し、その出力を使うという方法です。 メタ予測器による選択のトーナメントを作る方法と比べて、複数の予測器の総合的な意見の調停が可能な点が優れています。 実際にはさらにPCと履歴も予測テーブルのインデクス作成に使われるので、例えば、「このPCと分岐履歴の時は、基本的にはgshareの言うことを信用すればよい」とか「とはいえgshare以外みんなが同じことを言っていれば、そちらを信用するべき」とかを動的に学習可能です。

"po"は、post-predictorで、USE_ALT_ON_NAの発展版です。 "po"も"COLT"と同じように、予測器の出力Nビットを2Nエントリの予測テーブルに入れて、その出力を使うという方法です。 poTAGEは、TAGEの出力（最長一致のカウンタ3bit、第二最長一致のカウンタ3bit、第三最長一致のカウンタ3bit、最長一致のuビット1bit）を"po"に入力した答えを出力する分岐予測器です。

Five poTAGEs and COLT分岐予測器は、普通のグローバル履歴を使うTAGEで作られたpoTAGEと、グローバル履歴以外の不思議な履歴を使うTAGEで作られた4つのpoTAGE、あわせて5つのpoTAGEの出力をCOLT予測器に入れて最終的な分岐予測を行います。

Multi-poTAGE+SC分岐予測器は、Five poTAGEs and COLT分岐予測器の後ろに"SC"をつけたものです。

cbp4の後

André Seznec氏、Joshua San Miguel氏、Jorge Albericio氏は共著で、TAGE-GSC-IMLI分岐予測器を提案しました（2015/12/8, 48th MICRO）。 TAGE-GSC-IMLI分岐予測器は、TAGE分岐予測器に"GSC"と"IMLI"を加えたものです。 ここで、"GSC"はグローバル履歴しか使わないStatistical Corrector予測器、"IMLI"はInner Most Loop Iterationカウンタを用いた予測器です。

著者にJoshua San Miguel氏とJorge Albericio氏が入っていることからわかるように、IMLIはWormhole分岐予測器をより洗練させたものです。 そもそもWormhole分岐予測器は、二重ループ（外側のループカウンタをi、内側のループカウンタをjとします）に関する相関を捉えようとした分岐予測器です。 普通のローカル履歴では、近いjに対する相関を捉えることはできますが、近いiに対する相関を捉えることは困難です。 Wormhole分岐予測器では、二次元的なローカル履歴を持つことで、近いiに対する相関も捉えます。 これにより、例えばi == jの時だけ分岐が成立、とかのパターンを正確に予測することができるようになります。 ※禁忌です

IMLIは、Wormhole分岐予測器がやりたいことを、禁忌を犯さずに行うことを可能にします。 IMLIカウンタはその名の通り、内側のループについて何周目であるかをカウントしています。 重要なのは、これはグローバルな値であり、またループ周回数に対して対数ビットで表せるので、グローバル分岐履歴と同様に巻き戻しが容易であるという点です。

この論文では、IMLI-SICとIMLI-OHの二つの部品（hashed perceptronに追加するパーセプトロン）を提案しています。

IMLI-SIC（Same Iteration Count）は、「iには依存せず、jだけに依存している」パターンを捉えるものです。 これは、単にPCとIMLIカウンタを使った予測器を使えば実現可能、つまりローカル履歴は一切不要にもかかわらず、とても効果が高いです。 ループ予測器は、基本的にこれに内包される点もうれしい点です。

IMLI-OH（Outer History）は、Wormholeと同様、二次元のローカル履歴を使い、さらに幅広いパターン（例えばi == jの時だけ分岐が成立、とか、j == K && i % 2 == 0の時だけ分岐が成立、とか）を捉えるものです。 二次元のローカル履歴は、普通に考えると禁忌を犯さずに作ることができませんが、うまい方法があるそうです。 まず、同じi・近いjの分岐に対する相関を捉えるのは、グローバル履歴で代用可能です。 問題になるのは近いが異なるi・近いjの分岐ですが、これは何十命令も前のはずで、もうとっくに確定しているはずです（それより近いならば、グローバル分岐履歴で相関が取れそうです）。 これを利用すると、分岐履歴の投機的更新をサボって、確定時更新としてしまうことができます。 このようにしても「グローバル分岐履歴では遠すぎて（間に余分な分岐命令が入ることで履歴パターンが増えてTAGEでは）相関がとりづらいので二次元ローカル履歴に頼りたい」という場合の威力は衰えないとしています。

このように、禁忌を犯さないことが主眼の分岐予測器なので、Statistical Corrector予測器はグローバル履歴しか使わない"GSC"としています。

cbp5（2016/6/18, 43th ISCA併設ワークショップ）

André Seznec氏は現実的部門にTAGE-SC-L分岐予測器を再び提出し、非現実的部門にはMTAGE+SC分岐予測器を提出しました。 どちらの部門でも優勝しています。

TAGE-SC-L分岐予測器の大枠の構成はcbp4のものと同じです。 ただし、IMLIカウンタを用いたパーセプトロンがSCに追加されています。 IMLIカウンタがあればループ予測器は不要そうですが、なぜか残存していますし、そもそもIMLIはcbp5では役に立たなかったとしています。

MTAGE+SC分岐予測器（名称由来不明。たぶんmulti-TAGEとかだと思いますが）は、以下の要素からなります。

  • Five poTAGEs
  • global backward historyを用いたpoTAGE
  • TAGE prediction combiner（COLTにパーセプトロンを加える改良）
  • いろいろごった煮のSC（Statistical Corrector予測器）

つまり、ほとんどMulti-poTAGE+SCと同じ構成です。 違いは、global backward historyを用いたpoTAGEが追加され、COLTがやや進化し、SCによくわからない部品がいろいろ追加された、ということになります。

まとめ

  • USE_ALT_ON_NA: 最近確保された(newly allocated)エントリの提供する予測を使うくらいなら第二最長一致に基づく予測(altpred)をしたほうが良いかを判断する超単純メタ予測器。PPM-likeとTAGEの主要な違いのうちの一つ
  • "L"（L-TAGE, ISL-TAGE, TAGE-SC-L）: ループ予測器
  • "I"（ISL-TAGE）: Immediate Update Mimicker。まだ解決していない分岐に対する予測を取り込むための機構
  • "LSC"（TAGE-LSC）: ローカル履歴だけを使う統計的補正予測器
  • "S"（ISL-TAGE）, "GSC"（TAGE-GSC-IMLI）: グローバル履歴だけを使う統計的補正予測器
  • "SC"（TAGE-SC-L）: いろいろごった煮の統計的補正予測器
  • "po": post predictor。TAGEの第三最長一致までのカウンタ値と最長一致のuビットの値を総合して予測を出力する予測器。USE_ALT_ON_NAの発展版
  • COLT: Combined Output Lookup Table。多数の分岐予測器の出力を総合して予測を出力する予測器
  • IMLI: Inner Most Loop Iteration。IMLIカウンタを使うとローカル履歴を使わずにローカル予測器と似たことができるのでうれしい
  • "IMLI-SIC": IMLIでSame Iteration Count（内側のループ回数が同じ場合）の相関を取る部品。単にPCとIMLIカウンタでインデクスされた表を使うだけで簡単なのがうれしい。実質的にループ予測器の代替となる
  • "IMLI-OH": Wormhole分岐予測器でとらえられるような、二次元的ローカル履歴を用いた予測を提供する部品

参考文献