FPGA開発日記

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

分岐予測の評価キット Branch Prediction Championship Kit を試す (10. TAGEの基本)

この論文のイントロダクションを見ると、TAGEの発想はPerceptronと似たようなと来ていることが分かる。Hashed PerceptronおよびO-GEHLはGHRの使用する長さをGeometric、つまり等比数列的に伸ばすのが特徴であるが、TAGEのGEも同じようにGeometricであり、等比数列上に履歴を伸ばしていくところがポイントとなっているようだ。歴史的なところがかいつまんで説明してあり面白い。

まず、(当時の)最先端の分岐予測器は、長い相関と短い相関の両方をとらえるために、いくつかの異なる履歴の長さを使用することが挙げられている。

  • [24] : A. Seznec. Analysis of the o-gehl branch predictor. In Proceedings of the 32nd Annual International Symposium on Computer Architecture, june 2005.
  • [26] A. Seznec, S. Felix, V. Krishnan, and Y. Sazeid`es. Design tradeoffs for the ev8 branch predictor. In Proceedings of the 29th Annual International Symposium on Computer Architecture, 2002.
  • [9] D. Jim´enez. Fast path-based neural branch prediction. In Proceedings of the 36th Annual IEEE/ACM International Symposium on Microarchitecture, dec 2003.
  • [11] D. Jim´enez. Piecewise linear branch prediction. In Proceedings of the 32nd Annual International Symposium on Computer Architecture, june 2005.

さらにハイブリッド予測器により、いくつかの異なる予測から選択を行う手法が用いられていた。

  • [19] S. McFarling. Combining branch predictors. TN 36, DEC WRL, June 1993.

このハイブリッド方式の特徴として、複数のコンポーネントをから最終的な予測を選択して決定する方法がいくつか提案された。

  • [21] P. Michaud, A. Seznec, and R. Uhlig. Trading conflict and capacity aliasing in conditional branch predictors. In Proceedings of the 24th Annual International Symposium on Computer Architecture (ISCA-97), June 1997.
  • [18] G. Loh and D. Henry. Predicting conditional branches with fusion-based hybrid predictors. In Proceedings of the 11th Conference on Parallel Architectures and Compilation Techniques, 2002.
  • [6] A. N. Eden and T. Mudge. The yags branch predictor. In Proceedings of the 31st Annual International Symposium on Microarchitecture, Dec 1998.

そして、ニューラルネットワークをベースとするPerceptronベースの予測器が登場する。最終的には、加算ツリーを用いて各テーブルからの重みを結合する手法が提案された。これには当初ハードウェアのロジックの複雑さに関する問題があったが、これは徐々に解決されていった。

  • [7] H. Gao and H. Zhou. Adaptive information processing: An effective way to improve perceptron predictors. Journal of Instruction Level Parallelism (http://www.jilp.org/vol7), April 2005.
  • [3] V. Desmet, H. Vandierendonck, and K. D. Bosschere. 2far: A 2bcgskew predictor fused by an alloyed redundant history skewed perceptron branch predictor. Journal of Instruction Level Parallelism (http://www.jilp.org/vol7), 2005.
  • [17] G. Loh. Deconstructing the franken predictor for implementable branch predictors. Journal of Instruction Level Parallelism (http://www.jilp.org/vol7), April 2005.
  • [14] D. A. Jim´enez. Idealized piecewise linear branch prediction. Journal of Instruction Level Parallelism (http://www.jilp.org/vol7), April 2005.

Perceptronベースの予測手法は、様々な手法を用いて予測精度が改善されていった。

  • [13] D. Jim´enez and C. Lin. Neural methods for dynamic branch prediction. ACM Transactions on Computer Systems, November 2002.
  • [23] A. Seznec. Revisiting the perceptron predictor. Technical Report PI-1620, IRISA Report, May 2004.
  • [30] D. Tarjan and K. Skadron. Revisiting the perceptron predictor again. Technical Report CS-2004-28, University of Virginia, September 2004.

Perceptronのなかで、O-GEHL予測器は長い相関と短い相関を効率的にとらえるためにストレージ効率の良い手法となっている。

  • [25] A. Seznec. Genesis of the o-gehl branch predictor. Journal of Instruction Level Parallelism (http://www.jilp.org/vol7), April 2005.
  • [24] A. Seznec. Analysis of the o-gehl branch predictor. In Proceedings of the 32nd Annual International Symposium on Computer Architecture, june 2005.

ここからTAGEの話となる。TAGEはTAgged GEometric history lengthの略称であるが、PPMと呼ばれる予測器の派生形である。

PPMというのは、Prediction by Partial Mappingの略称らしい。この手法自体は良く分からない。

TAGEはO-GEHLと比較して同じストレージサイズを使用しても予測精度が優れている。

さらに、間接分岐に命令に対しても適用可能なIndirect branch Target TAgged GEometric history length predictor (ITTAGE) も提案されている。間接分岐命令の予測に対して、これまでにない精度を達成している。


で、ここからはTAGEの基本的な話になるのだが、TAGEの予測器は大きく分けて2つの部分から構成されている

  • 基本予測器 (base predictor) : T0
  • タグ付き予測器 (tagged predictor)
    • 複数存在する (T1, T2, T3, T4...)

このうち、T0は非常に基本的なbimodalのテーブルであり、それ以外のTagged Predictorはテーブルに以下のコンポーネントを持っている。

  • 符号付きカウンタ (ctr) : 予測に使用する
  • 部分タグ (tag) : PCとGHRから作成するハッシュと一致するかを確認するタグ
  • 有用カウンタ (u) : 2ビットのカウンタ

複数の予測器において、タグがマッチしたもののみ予測が提供される。さらに、予測はタグが長い方から優先的に提供されることになる。

これらの複数の予測器を用語として2つに分類する。

T2とT4がタグがヒットし、T1とT3のタグがミスした場合、

次にTAGE予測器の更新方法。

有用カウンタは、altpredと最終予測predが異なるときに、providerコンポーネントの有用カウンタを更新する。正しいときはインクリメント、そうでないときはデクリメントされる。

また、有用カウンタは年齢カウンタとして使用され、時々リセットされる。

予測がヒットした場合は、providerコンポーネントの予測カウンタが更新される。

すべての予測が正しくなかった場合、まず、providerコンポーネントの予測カウンタを更新する。providerコンポーネントが最長の履歴を持つコンポーネント (i==M)でない場合、Tiよりも長い履歴を使用するコンポーネントTkにエントリを割り当てる。