FPGA開発日記

FPGAというより、コンピュータアーキテクチャかもね! カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages

高性能プロセッサの分岐予測のサーベイ論文を読んで分岐予測について学ぶ (4. 予測が難しい分岐のための分岐予測器 2)

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

読んでいるのは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


4.4 データの相関に基づく分岐予測

データの差分に基づく分岐予測

Heilら[62]の提案。データの相関に基づく分岐予測を提案した。例えば、図16(a)のようなループを想像してほしい。このプログラムでは平均してループが21回実行されるものとする。これはグローバルBHRのビット長よりも長いため、通常の方法では分岐予測をすることができない。さらに、ループの回数はlenの値に相関するため、分岐予測が難しい。

xlen = len / OPSIZE;
while (xlen > 0) {
    // 何らかの処理
    xlen -= 1;
}

しかし、xlenの値が何らかの値に近づけば分岐を行うわけである。この場合は、いくつかの分岐命令がxlenと0の比較を行い、その結果に基づいて分岐を行っているため、この場合はレジスタの値に分岐の結果が強く相関するわけである。

そこで、履歴テーブルに、分岐命令のレジスタの差分値を保存しておくという方法が考えられる。これを差分分岐予測器 (branch difference predictor) と呼ばれる。図16(b)では、この分岐予測器の構成を示している。

しかし、いくら差分値とは言え保存すべきパタンのサイズは大きくなる。そこで、通常時は"Backing Predictor"を使って差分値を使用しない予測を行い、Backing Predictorと予測が異なる場合のみ予測値を書き換えるための"Rare Event Predictor (REP)"を実装する。REPはタグ付きのキャッシュのような構成をしており、予測が難しいような頻度の低い分岐を予測する。Backing Predictorが予測を外した時にのみREPがアップデートされる。エイリアシングが発生し精度が下がることを防ぐために、Backing Predictorは予測を行った場合のみ更新される。

f:id:msyksphinz:20190708230607p:plain
値の差分に基づく分岐予測器 (本論文より抜粋)

命令のチェーンに基づく分岐予測

Chenら[75]の提案では、値ベースの分岐予測器として、命令のチェーンを記録する方法を取っている。分岐の結果に影響しているすべてのレジスタの値が、まえの分岐実行時と同一であるとしたら、そのまま次の分岐の結果となるはずである。しかし、値ベースの分岐予測を行うためにすべての依存性のあるレジスタの値を使用することは現実的ではないので、データ依存のチェーンを使用することになる。

この方式ではテーブルを用意し、このテーブルを参照するためにPCとレジスタIDを使用する。さらにハッシュとしてレジスタの値を使用することで、値が異なるレジスタの記録同士でテーブルがぶつからないように配慮している。

この手法は、使用するテーブルのサイズを同一とするならば、ハイブリッド分岐予測器よりも高い分岐予測精度を実現する。

インフルエンサー分岐

インフルエンサー分岐は、分岐予測をすべき分岐 B _ {0} に対して、そのオペランドを決定するための分岐 B _ {i} に関する分岐予測手法である。このため、インフルエンサー分岐と呼ばれる。

例として、図17(a)のような制御フローがあり、そのうち網掛けの部分をCPUが通過しているとする。この時B8を予測したいとすると、B8はレジスタR2とR3に依存していることが分かる。

f:id:msyksphinz:20190708230659p:plain
制御フローに基づくインフルエンサー分岐 (本論文より抜粋)

BB3でR2の値が生成され、BB2でR1の値が生成される。R3の値はBB7において生成される。このため、以下のように考える。

この情報を利用して、アーキテクチャレジスタに書き込む最新の命令について、インフルエンサー分岐を追跡し、その情報を「インフルエンサーレジスタファイル (IRF)」に格納する。条件分岐の場合には、インフルエンサー分岐の詳細はそのソースオペランドの生成元から継承される。また、そのソースレジスタのIRFエントリが読みだされ、ORされて、「インフルエンサー分岐ビットマップ(IBB)」が生成される。

この情報に基づいて、2つの手法を提案している。

  • ゼロ化方式(図18(a)) : グローバル履歴内の非インフルエンサービットは、それらをIBBとANDすることによってマスクされる。したがって、インフルエンサー分岐以外のビットはグローバル履歴内ではマスクして見えなくなる。この値に基づきFold演算とOR演算によって予測器のインデックスを参照するために必要なインデックスが生成される。
  • パッキング方式(図18(b)) : ゼロ化方式と似ているが、違いは、インフルエンサーでないビットをマスク後に除去してしまい、インデックスのサイズを減らす。この後にFold演算を行って、Predictorのインデックスに入力する。
f:id:msyksphinz:20190708230741p:plain
インフルエンサー分岐の2種類の構成方法 (本論文より抜粋)