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

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

A Survey of Techniques for Dynamic Branch Prediction
- Sparsh Mittal

5 ハイブリッド分岐予測とは

複数の分岐予測器を使って、最終的に1つの分岐予測を決める手法であるが、方法としてはいくつか存在しており、

何個の分岐予測器から最終的な予測を選択するか
- 2, 3, 全体
選択予測器(Choice Predictor)への入力
- 分岐アドレスのみ
- 分岐アドレス、グローバル分岐履歴
各分岐予測器から最終的な予測を選択する指針
- 各分岐のバイアス
- 選択予測器の指示に従う
- 多数決
- 最も長い履歴を持つタグ付された分岐予測器
- 最も自信のある予測器を使う。
- ...
- 各分岐予測器の結果を複合する方式

5.1 Tagged Hybrid 分岐予測器

Edenら[33]の提案。通称YAGS。gshareとBimodalの分岐予測器のハイブリッドである分岐予測器を提案している。彼らの技術は、図20に示したとおり、

PHTを2つに分割する。Taken用のPHTとNot Taken用のPHTに分割し、それをChoice PHTに格納する。これにより、Direction PHTの情報量が少なくなｆｇり、サイズをChoice PHTより小さくすることができる。そのような発生をDirection PHTで識別するために、それらは各エントリ内のタグとして分岐アドレスの最下位6～8ビットを記憶する。これらのタグによって、特にコンテキストの切り替え後に、エイリアシングをほぼ完全に取り除くことができる。

f:id:msyksphinz:20190726001921p:plain — 図は本論文より抜粋

まずChoice PHTにアクセスし、結果が”Not Taken"である場合は、"Taken"のキャッシュが参照される。TakenキャッシュがHitもしくはMissであれば、その結果そのものか、Choice PHTのどちらかが最終的な予測として使用される。Choice PHTがTakenであれば、その逆が実行される。つまり、Not Takenのキャッシュの結果と、Cache PHTのどちらかが最終的な予測として使用される。

Takenキャッシュが更新される条件 : Takenキャッシュの値が予測に使用された、もしくはChoice PHTの値が予測に使用され、予測がNot-Takenであったが最終的な結果はTakenであった場合。
Not Takenキャッシュが更新される条件 : Not Takenキャッシュの値が予測に使用された、もしくはChoice PHTの値が使用され、予測がTakenであったが最終的な結果がNot Takenであった場合。

上記のように、TakenキャッシュとNot Takenキャッシュに分離することにより、エイリアシングの発生を防ぐことができる。この技術では、Bimodalの分岐予測器と比較して高い精度を達成することができる。

5.2 Selection-based Hybrid BPs

チャンら[64]の提案。分岐予測器にはそれぞれ特徴があり、予測が得意な分岐とそうでない分岐があるため単一の分岐予測器ですべてをカバーすることはできない。

そこで、彼らは複数のハイブリッド分岐予測器設計を提案し、評価している。

偏り付き分岐と非偏り付き分岐にそれぞれ短いBHRと長いBHRが使用されているGA 分岐予測器
偏り付き分岐にはプロファイルガイド分岐予測器、非偏りベースにgshare [81] 分岐
2bc + gshare
PA + gshare
偏り付き分岐の場合はプロファイルガイド分岐予測器、偏りなしの分岐の場合はPA + gshareハイブリッド

彼らは、これらのハイブリッド分岐予測器が単独分岐予測器よりも高い精度を提供することを示している。また、偏りのかかった分岐に静的分岐予測器を使用すると、動的分岐予測器により少ない記憶領域で高い精度を達成することができる。

Seznecら[31]の提案。2つのハイブリッド分岐予測器を提案する。

2bc + gskew : 4つの予測器バンクから構成される (図21(a))
- 3-bankの e-gskew [86]の3つのバンク
- メタ予測器 : 分岐アドレスとグローバル履歴の組み合わせを使用してアクセスされる。予測は、e-gskewの3つのバンクが誤った場合に更新される。
正しい予測については、予測がバイモーダル分岐予測器によって提供された場合はこれのみが更新されるが、e-gskewによって提供された場合は、予測を提供したバンクのみが更新される。

メタ予測器は、2つの予測器が一致しない場合にのみ更新される。彼らは、他の２つのバンクが更新されず、従って正確な予測のためにGHRの使用を必要としない分岐によって汚染されないためにBimodal分岐予測器が大部分の予測を提供するので2bc＋ gkewがe-gkewより高い精度を提供することを示す。また、ほとんどの場合、バイモーダル分岐予測器とe-gskew 分岐予測器は一致しているため、メタプレディクタは必須でも更新もされていない。したがって、メタプレディクタのエイリアシングによって精度が損なわれることはありません。
2bc + gskew + pskew (図21(b))
- e-pskew : グローバル履歴ではなく、アドレス毎の履歴から恩恵を受ける分岐を正確に予測するためのアドレスごとの履歴分岐予測器。
  
  したがって、2bc + gskew + pskewには3つの構成要素から構成される。
  - Bimodal
  - アドレスごとの履歴
  - およびグローバル履歴
  このため、2bc + gskew + pskew 分岐予測器は、2bc + gskew 分岐予測器よりも高い精度が出るが、レイテンシも伸びる。

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

Seznecら[1]の提案。352Kbの容量を必要とするAlpha EV8プロセッサにおける分岐予測器の設計に実際に使用されている。

Alpha EV8は各サイクルで最大2つの8命令ブロックをフェッチするため、各サイクルで最大16の分岐を予測する必要がある。

したがって、ローカル履歴分岐予測器は多くのリソース(例えば、16ポート予測テーブル)を必要とし、非常に複雑(例えば、異なるスレッドからの予測エントリの競合)であるため、その代わりにGH分岐予測器を使用する。

彼らの分岐予測器は2bc + gskewハイブリッド分岐予測器に基づいている[31]。

このハイブリッド分岐予測器では、偏った分岐はバイモーダル予測器によって正確に予測されるため、そのような分岐では他のテーブルは更新されない。この部分更新方式は、偏った分岐によるエイリアシングを回避し、さらに実装を単純化する。これにより、予測器とヒステリシスの配列を分離することができ、面積と予算を満たすために、メタ予測器とG1予測器のヒステリシス配列(図21(a)を参照)が半分のサイズに縮小される。

部分更新を使用すると、ヒステリシス配列への書き込みが減り、エイリアシングの影響が少なくなる。また、G0よりもG1の方が長い履歴長を使用し、G0、G1、およびメタ予測器よりもバイモーダルの方が小さい予測テーブルを使用する。

分岐予測器はシングルポートメモリセルを有する4ウェイバンクインターリーブとして実施され、２つの連続するフェッチブロックが異なるバンクにアクセスすることを確実にするようにバンク番号を計算することによってバンク競合が完全に回避される。彼らは、実装上の制約にもかかわらず、それらの分岐予測器の精度は他の等サイズのGHベースの分岐予測器と同等であることを示している。

5.3 Fusion-based hybrid BPs

Lohら。 [68] 1つの分岐予測器から最終予測を選択するハイブリッドBPは、選択されていない分岐予測器からの情報を完全に無視してしまう。彼らは、すべての分岐予測器からの情報に基づいて最終的な予測を行うフュージョンアプローチを提案している。これらのアプローチを図22(a)と22(b)に示す。。

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

それぞれの分岐予測器の結果を最終的な予測に変換するために、"Vector of Mapping Tables(VMT)"を使用している。図23がそれにあたる。

VMTには2N個のマッピングテーブルであり、各エントリは飽和カウンタとなっている。

ステップ1. まず、各分岐予測器にて予測を行い、それと同時に分岐履歴とアドレスビットに基づいてVMTから1つのマッピングテーブルを選択する。

ステップ2. 選択されたマッピングテーブルの2N個のカウンタのうちの1つが選択される。

最終的に選択されるVMTエントリのカウンタのMSBビットが、その分岐予測器の予測となる。

テーブル探索のためのレイテンシ(4サイクル)と大きいが、分岐予測器の精度は高い。

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

5.4 Multi-Hybrid 分岐予測器の設計

Eversらの提案[20]。2つ以上の分岐予測器を組み合わせることにより、より精度を高める。

2ビットカウンタを使用し、それらのカウンタの初期値は3である。予測に成功した分岐予測器のカウンタはデクリメントされ、そうでない場合はカウンタがインクリメントされる。

この分岐予測器の方式の特徴は、相対的にそれぞれの分岐予測器でどれが優位であるかを比較することができる。分岐履歴の長いが学習に時間のかかる分岐予測器と、性的分岐と短い分岐履歴で学習時間の短い分岐予測器を用意し、それをハイブリッドで使い分けるという方式があり得る。

5.5 Prophet-critic hybrid BP

Falconらの提案[55]。図24(a)に示すように、Prophet(預言者)とCritic(批評家)と呼ばれる2つの分岐予測器を使用する手法を提案する。

Prophetは現在の分岐履歴に基づいて予測を行い、予測された経路をたどり、元の分岐に対して「分岐の未来」を形成するさらなる予測を行う。

この情報に基づいて、Criticは過去と未来の両方と相関し、Prophetのそれぞれの予測について賛成/反対意見を批評します。将来のコードの振る舞いを使用することで、より正確な予測が行われるため、Criticの予測は分岐にとっての最終的な予測となる。

例えば、図24(b)では、正しいパスが影付きブロック(A,C,G,I)で示されている。Aの歴史は、その前の分岐V→W→X→Y→Zという分岐結果によって形成され、この歴史はProphetがAを予測するために使われる。

すべての分岐が正しく予測されると、分岐A→C→G→I(結果NNTT、N = Not Taken / T = Taken)によってAの未来を形成する。もしAの予測が誤っているならば、赤い破線によって示される誤った経路で進行する。

ここで、Prophetは分岐A、B、D、Hを予測し、それらの予測はCriticの分岐結果レジスタに格納されます。したがって、Criticは分岐履歴(V→W→X→Y→Z)と分岐未来(A→B→D→H)の両方を持っている。

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

分岐Bについて、ProphetがP個の余分な分岐を観察した後に予測を行う場合、Prophetによって使用される将来のビット数はPであると言われる。例えば、図24では、P = 4である。間違った道に沿ってより多くの進歩を検出する。

Prophetが初めて分岐を誤って予測したとき、Criticはこの出来事を検出し、同じ状況下でProphetが再びその分岐を誤って予測したとき、CriticはProphetの予測に反対する。Prophet/CriticのBPは独立して働き、既存のBPはそれらのために使用することができます。パフォーマンスを向上させるために、Prophetは90％以上の分岐を正しく予測するべきであり、Criticは残りの分岐だけを予測する責任がある。従来のハイブリッドBPとオーバーライドBPの両方で、コンポーネントBPは同じ情報に基づいて同じ分岐を予測するが、分岐予測器では、異なる時点で2つの予測が発生する。