分岐予測の評価キット 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と呼ばれる予測器の派生形である。