FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

高性能プロセッサの分岐予測のサーベイ論文を読んで分岐予測について学ぶ (7. 予測精度を上げるためのテクニック1)

プロセッサアーキテクチャについて再度復習その7。分岐予測の続き。

読んでいるのはA Survey of Techniques for Dynamic Branch Predictionという論文で、新規技術の解説ではないのだが、現在の有名どころの分岐予測技術についてまんべんなく解説してくれている論文だ。

  • A Survey of Techniques for Dynamic Branch Prediction
    • Sparsh Mittal

https://arxiv.org/pdf/1804.00261.pdf

6. 分岐予測の精度を上げるための技術

この章では、分岐予測器の精度を向上させるためのいくつかのアプローチについて説明する。

  • 履歴やパス長の動的な調整(セクション6.1)
  • エイリアシングの削減(セクション6.2-6.4)
  • マルチスレッドおよび短命スレッドの存在下での精度の向上(セクション6.5)
  • 不正パス実行からの学習(セクション6.6)。

表6.1に、エイリアシングを削減するための手法についてまとめる。

手法 論文
タグの使用 [2, 27, 33, 34, 62, 73, 75, 88, 92]
高度なインデックス関数の使用 [88]
複数のインデックス関数を使用 [47, 86]
分岐アドレスと分岐履歴をXORする [81]
損害を与える相互干渉を解消させる。 [19]
分岐予測器内で、最も最近の分岐のみを格納する。 [17]
異なるバイアスの分岐を別々に格納する。 [33, 80]
ユーザプロセスとカーネルプロセスの分岐予測器を分離する。 [71]

6.1 履歴長とパス長を調整する手法

Juanらの提案[13]。分岐履歴の最適な履歴長というのは、そのプロセス、入力、コンテキスト切替の頻度などに依存する。そのため、それぞれの状況にお維持て最適な分岐履歴長を設定するのが望ましい。

彼らの提案は、アプリケーションに使用される履歴ビット数と2レベル分岐予測器の入力データを動的に変更するというものである。gshare分岐予測の場合、異なる実行インターバルにおいて、PCと異なる履歴長とXORを計算する。その実行インターバルは、動的分岐命令が固定回数実行される時間である。

各履歴長に応じた分岐予測の失敗回数はテーブルに記録される。各実行インターバルについて、既存のインターバルの誤予測の回数がテーブル内の誤予測の回数よりも多いならば、履歴長は増加または減少し、最適な履歴長に向かって移動することになる。

この手法の問題は、履歴の長さの変化の後にPHTの状態の大部分を失ってしまい、再び学習する必要があるということである。これによりエイリアシングが発生して誤予測が増加する。

この誤予測による影響を削減する雨に、履歴長が変化すると、ご予測のカウンタは次の1回の実行インターバルまでは更新されない。これらの技術により、コンテキストの切り替えが発生する場合と発生しない場合の両方において、履歴長が最適な場合の予測精度に近づくことができることを示している。

グローバルの分岐履歴とPCを組み合わせるタイプの分岐予測器(例えば、agree [19]、bimodal [80]、gselect [81]、gshare [81]、e-gskew [86])ならば、どれでもこの技術を使用することができる。

Starkらの提案[67]。パスベースの分岐予測器では、予測を行うテーブルのインデックスを計算するために、K個のの最近のターゲットアドレスをハッシュする。ここでの提案は、各分岐に対して異なる経路長(K)を使用することができる2レベル分岐予測器を提案した。図25に示すように、最新のK個の分岐のジャンプアドレスは、レベル1の履歴の形成に使用される。

アドレスの下位Lビットは「ターゲット履歴バッファ(Target History Buffer:HTB)」に格納される。

$A_j$が最新から$j$番目に格納されているTLBのアドレスを参照するものとする。レベル1のテーブルからLビットのインデックスは、Predictorテーブルに格納されている2番目の分岐履歴にアクセスるためのインデックスとして使用される。

各Predictorテーブルは2ビットの飽和カウンタを使用しており、長さ$j$のパス($\text{PATH}j$)はTLBないの最新の$j$個のアドレスを持っており、これによりK個の異なるハッシュ関数($\text{HASH}j$)を生成する。プロファイリングに基づいて、すべての分岐に対して、その分岐の最高の精度を提供するためのハッシュ関数が一つ選択される。

f:id:msyksphinz:20190727142304p:plain
本論文より抜粋

6.2 分岐履歴のフィルタリング

履歴の長さを長くすることにより、より昔の分岐命令との相関関係を利用することができ、一般的に精度が向上するが、逆に創刊のない分岐が含まれてノイズが発生することがある。これを防ぐため、分岐履歴をフィルタリングする技法が提案されている。

Porterら[76]の提案では、分岐の相関に限界の存在するコード領域(ZLBC : Zones with Limited Branch Correlation)で、GHRにさらに多くの情報を格納すると精度が落ち、トレーニング時間の増加とエイリアシングの増大を招いてしまう。

図26では、gccのベンチマークの一部である。Branch1は関数内の最初の分岐であり、NULLポインタのチェックである。100M命令の実行では、この分岐は2455回実行されるが、分岐がTakenになる事は無い。この分岐は208個の異なる16bitの履歴を使用し、予測を外す確率は9％である。このようなシナリオの分岐予測の精度を向上させるために、彼らは利益の少ない、相関の少ない分岐命令をGHRから除去するという方法を提案している。一方で、相関の強い分岐命令はGHRに残すことで、精度を向上させる。

static void sched_analyze_2 (rtx x, rtx insn) {
  register int i, j; register char *fmt;
  if (x ==0) // Branch1
     return;
  // more code
}

命令の実行シーケンスがあるリージョンから別のリージョンに移動する場合、これらのZLBCのゾーン間で相関関係はない。ZLBCの識別方法は、制御フロー命令、後方への分岐、関数呼び出し、関数からの戻り」などを検出して認識する。

  • 後方への分岐のとられていない経路は一般にループ出口を示す。
  • ループ後の分岐はループ内の分岐との相関が限定されていると予想される。

これらのZLBCを認識するとGHRをリセットする。この方式を利用することで、上記のサンプルプログラムではご予測率がわずか1％まで減少させることができる。

Xieらの提案[38]。分岐予測器の分岐相関(すなわち、ノイズ)の影響を軽減するための技術。

元の分岐予測器を2つのサブ予測器、すなわち従来型分岐予測器(Conventional BP : CBP)と履歴変動型分岐予測器(History Variation BP : VBP)に分割する。この2つは、分岐履歴の更新方法が異なること以外は基本的に同一である。

Xieら[38] は、分岐予測器における無用な分岐相関(すなわち、ノイズ)の影響を軽減するための技術を提示している。それらは、CBPは分岐がコミットされるまで分岐履歴を保存するが、VBPは履歴スタックを使用してループや関数の分岐履歴を削除する。

ループまたは関数に入る間、現在の履歴は履歴スタックにPushされ、ループを終了すると履歴がPopバックされる。プロセッサ内に存在するRASおよびループ予測器は履歴スタックで増強され、それらを使用して関数およびループが検出される。以前の分岐の実行履歴に基づいて、VBPまたはCBPのいずれかがセレクタテーブルを使用して選択される。

図27にこれらの技術を要約した。図27(a)は典型的なソースコードを示している。

関数に入る前に、CBPとVBPの両方のGHRは1110である。

  • VBPは : 関数に入ったり出たりする間に、それぞれ履歴をPush/Popする。
  • CBP :従来の分岐予測器と同じように機能する。

したがって、分岐を予測する一方で、CBPとVBPは異なる履歴を持ち、したがって、異なる予測が生成される。セレクタによって最終的な予測が決定される。この場合は"Not Taken"であるが、実際の結果は"Taken"ことが起こるので、CBPとVBPはどちらも"Taken"方向に学習し、セレクタは正しい予測を提供するのでVBPを選択するように訓練される。彼らのアプローチをgshare、パーセプトロン、およびTAGE分岐予測器と共に使用することによって、分岐予測器精度が改善する。

f:id:msyksphinz:20190727131423p:plain
本論文より抜粋

Huangらの提案[39]。エイリアシングは分岐予測器の有効性を著しく低下させる。

  • ループ内のホット分岐はループ外の分岐の履歴を除去してしまう。これにより長いグローバル履歴を維持する利点を打ち消す。

この愛ではでは、単一のグローバル履歴を使用するのではなく、分岐アドレスの下位ビットに基づいてグローバル履歴ビットを複数のグループに分割する。エントリ内のすべての履歴ビットを連結することによって、最終履歴が形成される。

このアプローチによって、同じハードウェアコストでより長い相関履歴を追跡することができるようになる。

例えば、図28(b)では、4ビットGHRが使用され$A_i$-$F_i$は、図28(a)に示されるコード内の対応する分岐の履歴ビットを示している。ここで、$D_4$がいったんコミットされると、それはGHRにシフトされ、$A_0$は追い出される。

この分岐予測器は下位2ビットによって4つのグループに分岐を分ける。各ビットには1ビットの履歴のみが保存されるため、合計の保存コストは同じである。ここで、$D_4$がコミットされると、図28(c)に示すように、$D_4$は$A_0$ではなく$D_3$を追い出す。彼らは、パーセプトロン予測因子を用いた彼らのアプローチの使用が誤予測率を有意に減少させることを示している。

この技術の問題は、ローカル情報を制限してしまうことであり、ローカル履歴とグローバル履歴を使う場合よりも性能が悪化してしまう恐れがある。

f:id:msyksphinz:20190727142358p:plain
本論文より抜粋

Gopeらの提案[17]。偏りのある分岐は、偏りのない分岐の予測に対しt絵影響を与えないため、偏りのない分岐のみを分岐相関履歴に格納する手法を手案する。

彼らの提案では、有限状態ステートマシンを使用して動的に分岐の偏った性質を検出する。

条件付き分岐は、最初は"Not Taken"状態であり、初めてコミットされると"Taken"もしくは"Not Taken"状態に移行する。何度か実行している中でこの予測が逆方向になると、ステートマシンは非バイアス状態に移行する。この偏っていない分岐命令は、今後の分岐履歴からは除外される。

彼らの研究では、繰り返し分岐の複数の結果によって更なる価値が発生することはほとんどないと述べている。彼らはRecency-stackを使用しt偏っていない分岐の最新の結果のみを記録し、その結果との相関を見つけようとしている。

参考文献

  • [13] T. Juan, S. Sanjeevan, and J. J. Navarro, “Dynamic history-length fitting: A third level of adaptivity for branch prediction,” in ISCA, 1998, pp. 155–166.
  • [17] D. Gope and M. H. Lipasti, “Bias-free branch predictor,” in International Symposium on Microarchitecture (MICRO). IEEE, 2014, pp.521–532.
  • [19] E. Sprangle, R. S. Chappell, M. Alsup, and Y. N. Patt, “The agree predictor: A mechanism for reducing negative branch history interference,” in ISCA, 1997, pp. 284–291.
  • [38] Z. Xie, D. Tong, and X. Cheng, “An energy-efficient branch prediction technique via global-history noise reduction,” ISLPED, 2013.
  • [39] M. Huang, D. He, X. Liu, M. Tan, and X. Cheng, “An energy-efficient branch prediction with grouped global history,” in ICPP, 2015, pp. 140–149.
  • [67] J. Stark, M. Evers, and Y. N. Patt, “Variable length path branch prediction,” in ASPLOS. ACM, 1998, pp. 170–179.
  • [76] L. Porter and D. M. Tullsen, “Creating artificial global history to improve branch prediction accuracy,” in ICS, 2009, pp. 266–275.
  • [80] C.-C. Lee, I.-C. K. Chen, and T. N. Mudge, “The bi-mode branch predictor,” in MICRO, 1997, pp. 4–13.
  • [81] S. McFarling, “Combining branch predictors,” Digital Western Research Laboratory, Tech. Rep., 1993.
  • [86] P. Michaud, A. Seznec, and R. Uhlig, “Trading conflict and capacity aliasing in conditional branch predictors,” in ISCA, 1997, pp. 292–303.