FPGA開発日記

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

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

プロセッサアーキテクチャについて再度復習その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.3 カーネルモード実行でのエイリアシングの削減

これまでの提案手法は、すべてユーザモードでの測定であったが、Chenらの提案[70]では、

  • ユーザーモードの命令が全命令の95%以上を占める場合、ユーザーのみとシステム全体の誤予測率はほぼ一致する。

  • ユーザーモードの指示が90%未満の場合、システム全体の結果が反映されない。

したがって、ユーザー専用の分岐トレースに対する最適な分岐予測器は、フルシステムトレースに対するものと同じではない可能性がある。さらに、カーネル分岐を含めると、予測される静的分岐の数が増えるため、エイリアシングが悪化する。これにより、分岐予測器の有効サイズが小さくなる。エイリアスの影響は、ローカル深度の短い分岐予測器を使用する分岐予測器よりも、長い履歴を持つ2レベルの分岐予測器の方が高くなる。さらに、Nair et al。によって示唆されているように、定期的に分岐履歴をフラッシュする。 [26]は、カーネルや他のプロセスが常に分岐履歴状態をフラッシュするとは限らないため、ユーザーとカーネルの対話の影響を正確にはモデル化していない。また、フラッシュは大きなテーブルサイズの分岐予測器にとって特に有害である。

Liらの提案[71]に示すところでは、ユーザコードとカーネルコードの分岐の傾向はそれぞれ異なるので、それぞれが同時に実行されると分岐エイリアシングにより分岐ミスが増大してしまう。また、カーネルコードの多くは、分岐の傾向を把握することが難しい。これは分岐予測器のバッファのサイズを大きくしても問題は解決しない。

そこで、彼らの提案では、2つの手法を紹介している。

  1. 2つの分岐履歴レジスタを用意し、ユーザコードとカーネルコードの分岐情報を分離する。
  2. 1の手法ではPHT内で再度ユーザ・カーネルエイリアシングが発生するので、分岐履歴レジスタとPHTも分離してしまう。
    • カーネルコード内のアクティブな分岐の数はユーザコードの分岐の情報よりも少ないため、カーネルモードのPHTはユーザモードのPHTよりも小さくできる。

6.4 コンフリクトが削減されるインデックス関数の使用

Maらの提案[88]では、分岐予測器のテーブルエイリアシングを削減するためにインデックス関数を評価する。評価に使用したインデックス関数は表7に示している。

マッピング手法 インデックス関数
Modulo  \text{index} = x = A \mod 2^ k
Bitwise-XOR  \text{index} = x \oplus y
規約多項式(Irreducible Polynomial) インデックスの2進数表記 :  R(x) = A(x) \mod P(x), R(x) = a _ {n-1} R _ {n-1}(x) + \cdots +a _ 1 R _ 1(x) + a _ 0 R _ 0(x) ここで R_ i(x) = x^ I\mod P(x) は、規約多項式 P(x) の選択後に事前計算ができる。
Prime-Modulo  index = A\mod p \mod 2^ k  p 2 ^kに最も近い 2 ^kよりも小さな数。
A-prime-Modulo  index = A \mod p \mod 2^ k  pは最も小さいテーブルエントリ数以上の素数
Prime-displacement  index = (T * p + x) \mod 2^ k ,  p素数(例えば、17など)
  • 分岐予測器テーブルには2^ kのエントリがある。
  • Prime-Moduloマッピングはすべてのエントリを利用するわけではない。
  • A-Prime-Moduloマッピングでは、すべてのテーブルエントリが使用されるが、一部のエントリの使用頻度が高くなるという特徴がある。
  • 異なる分岐予測器バンクにおける異なるインデックス関数の使用を試行している。

結果:Moduloマッピングを基準とした場合、

  • gshare 分岐予測器 :
    • XORインデックスは一般的に精度を向上させる。
    • 既約多項式関数は精度が下がる。
    • Prime-Moduloは常に高い精度を提供できるわけではなかった。
    • Prime-displacementは大きな分岐予測器テーブルに対してはXORマッピングよりも優れた正答率を示すが、小さなテーブルに対しては正答率は低い。
  • パーセプトロン分岐予測器
    • すべてのインデックス関数でエイリアシングが大幅に減少した。
    • 小さなテーブルではエイリアシングが大きくなるため、大きなテーブルよりも小さなテーブルのほうが改善率が高くなる。
    • どのようなインデックス関数でも、様々なテーブルサイズにおいて一般的に性能が良い。
    • 大きなテーブルにXORマッピングを使用し、小さなテーブルにPrime-Displacementを使用すると、高い精度を達成しながら複雑さを低く抑えることができる。
    • 高度なインデックス関数が使用されている場合でも、タグを使うことによって除去可能なエイリアシングはまだ存在している。
    • 複数のインデックス関数を使用することも、エイリアシングを減らすのに効果的であることが分かった。

6.5 マルチスレッドへの対応とショートスレッド

スレッド数が増えるにつれて、分岐予測器に必要なテーブルサイズはより大きくなる。

Hilyら[96]の提案。マルチスレッドのワークロードで、各ハードウェアスレッドコンテキスト必要なRASエントリの最大値は12エントリで、それ以上大きくしても効果がない。

  • ワークロード内の異なるアプリケーションにデータ共有がない(マルチプログラムのワークロード)

    • スレッド数を使用してPHT/BTBテーブルのサイズを調整すると、すべてのエイリアスが削除することができる。
  • データ共有を伴う並列ワークロード

    • gshareおよびgselectでは、共有効果によりわずかに精度が向上するが、それ以外の分岐予測器(例えば、2BC)は、スレッド数の増加と共に予測精度が落ちる。

どちらの種類のワークロードでも、BTBのサイズを削減すると、BTBでの競合により予測ミスの数が増える。

Choiら [95]の提案。GHRはスレッド毎に履歴情報を格納していないため、大きな制御フロー履歴を処理している分岐予測器は細かく切り替えが行われるスレッドに対してはうまく機能しない。

  • 提案 : 現在または過去の情報を用いて、予想されるGHRを予測または再現する手法。
    • たとえば、子スレッドは親スレッドのGHRを継承する。
    • 同じスレッドが始まるときはいつでも分岐予測器のための一貫したスタートポイントを提供するだけである。
    • 例えば、投機的スレッドの最初の命令のPCからGHRを作成することによって、一意の初期GHR状態を各スレッドに提供することができる。これらのテクニックが短いスレッドのための誤予測を減らすことによってパフォーマンスを改善することを示した。

6.6 誤ったパス実行の情報を利用する

Akkaryらの提案[97]。制御が独立している場合、間違ったパス上の分岐結果は正しいパス上の分岐結果と一致する。

ただし、現在の分岐予測器は正しいパスでのみブランチ相関を研究するため、誤ったパスの情報を使用しない。彼らの技術は、gshare分岐予測器 [81]と同様のアルゴリズムを使用して、正しいパスと間違ったパスでの分岐の実行の間に相関の存在を見つける。

レベル1では、正しい経路で観測された最後のM個の分岐の結果がBHRに格納される。図30に示すように、誤予測分岐のアドレスはM/2ビット左にシフトされる。次に、2ビット飽和カウンタのためのインデックス計算が行なわれる。

インデックスの計算 : 予測対象の正しいパス上の分岐からのMビットとシフトされた誤予測分岐アドレスからのMビットのに対してXORが取られる。

カウンタ値が1を超える場合、分岐とその誤った経路との相関が存在するとして、誤った経路の結果が、分岐予測器の予測の代わりに最終的に選択される。

f:id:msyksphinz:20190801004621p:plain

カウンタの更新方針について。

  • 正しいパスと間違ったパスの結果が一致し、分岐予測器の予測が誤った場合、カウンタが増加する。
  • 正しいパスと間違ったパスで結果が異なり、分岐予測器が正しく予測していれば、カウンターは減少する。
  • それ以外の場合、カウンタは変更されない。

間違ったパスでの分岐結果はタグ付きバッファに格納される。このバッファ内の分岐結果はせいぜい1回使用されてから追い出されるので、命令ウィンドウ内の分岐のみに対応する必要がある。複数の誤った経路の結果を記憶してもわずかな改善しか得られないため、最新の誤った経路の結果のみが維持される。彼らの技術は、予測ミスを大幅に減らし、パフォーマンスを向上させた。彼らの技術の限界は、それが正しい経路と間違った経路で異なる結果を持つブランチの精度を向上させることができないということである。