Alpha EV8の分岐予測機に関する論文を読み始めた。

もう少し真面目に読み直している。第4章のハイブリッド分岐予測についてもう一度真面目に読んでいる。

4. 分岐予測器の構成

ローカル履歴とグローバル履歴のハイブリッド方式となっている。

分岐予測のエイリアシングとは？
- 異なる分岐命令が同じエントリテーブルを使用してしまうこと。性能が悪化する。
- これを解決するために導入されたのが、e-gskew分岐予測器
EV8では、2BC-gskewという方式を取っている。

4.1 2BC-gskew分岐予測器の構成

2BC-gskew分岐予測器の構成

Bimodal分岐予測器(BIM)
e-gskew分岐予測器 (G0)
e-gskew分岐予測器 (G1)
メタ分岐予測器 (Meta)

4.2 Partial Update Policy

そもそもPartial Update Policyと何なのか？

ハイブリッド分岐予測器において、各分岐予測器のアップデートの基準が違うということ？

分岐予測が正しかった場合
- すべての分岐予測器が同じ予測をしていた場合
  - アップデートしない
  - 理論的根拠
    - 目標は、正しい予測で強化されるカウンターの数を制限することである。カウンターが強化されると、他の（アドレス、履歴）ペアがそれを「盗む」ことが難しくなる。しかし、3つの予測器BIM、G0、G1が一致するとき、あるカウンターのエントリーは、多数決予測を破壊することなく、別の（アドレス、履歴）ペアに盗まれる可能性があります。3つの予測子が合意しているときにカウンターを強化しないことによって、そのような盗みが容易になる。(DeepLより)
- 分岐予測器が異なる予測をしていた場合
  - ローカルとグローバルが異なる場合、Meta分岐予測器をアップデートする
  - G0, G1, BIMのうち正しく予測をした分岐予測器をアップデートする：
    - Bimodalが使用されている場合、BIMをアップデートする
    - Majority Voteが使用されている場合、正しく予測した分岐予測器をアップデートする
分岐予測ミスが発生した場合
- 2つの分岐予測器の予測が異なっていた場合、選択回路(chooser)をアップデートし、それに伴い選択回路の新しい値に基づいてすべての分岐を再計算する
  - 最初に選択回路をアップデートする理論的根拠
    - 目標は、間違った予測に書き込まれるカウンターの数を制限することです。回避できる場合は、別の（アドレス、履歴）ペアからテーブルエントリーを盗む必要はありません。(DeepLより)
  - 正しく予測した予測器：すべての参加したテーブルをアップデートする
  - 予測に失敗した場合：すべてのバンクをアップデートする

4.3. 独立した分岐予測とヒステリシスアレイの使用

分岐予測が当たった場合、分岐予測ビットは変化しないがヒステリシスビットは強化される。したがって、正しく予測するためには

フェッチ時に予測ビットをフェッチする
コミット時にヒステリシスビットに書き込み

ということが要求される。分岐予測ミスが発生すると、ヒステリシスアレイを読みだして、予測ビットとヒステリシスビットの両方を更新する可能性がある。

4.4 いくつかのカウンタでヒステリシスビットの共有

EV8では、G1とMetaでヒステリシスビットのサイズを半分に、2つの分岐予測ではヒステリシスビットを共有している。これによりエイリアシングの問題が発生する。

4.5 履歴長

e-gskewの履歴長はG0とG1で変更した方が性能が良くなる。実際、G0は中間ぐらいの履歴長を使用しており、G1はより長い履歴長を使用している。

4.6 異なる分岐予測テーブルサイズ

BIMよりもe-gskewの方がより大きな分岐予測テーブルを使用している。

4.7 EV8分岐予測器のコンフィグレーション

トータルで352kBitsのメモリを使用している。

BIM : 予測16K + ヒステリシス16K
- 分岐履歴4ビットを使用している(理由はSection 7)
G0 : 予測64K + ヒステリシス32K
- 分岐履歴は13ビット
G1 : 予測64K + ヒステリシス64K
- 分岐履歴は21ビット
Meta : 予測64K + ヒステリシス32K
- 履歴長は15ビット

5. パスと分岐の結果情報

分岐予測器の精度は、予測の構成と分岐予測テーブルのサイズと同様に、インデックスに使用する情報ベクトルをどのように構成するかということも重要である。

5.1 3つのフェッチブロック

EV8では、分岐予測アドレスを計算するために3サイクル必要であるため、過去の古い3つのブロックを使用して分岐予測を作成することができない。したがって、それ以降の分岐の予測結果に基づいて次のフェッチブロックを予測することになる。

1サイクルで1つの分岐命令を予測するのならば、履歴ビットは1サイクルで1ビットだけずらせばよいが、EV8のように最大で1サイクルで16個の分岐命令を予測する場合、1サイクルで最大16ビットの履歴をシフトする必要がある。これはクリティカルパス的にも難しいので、より古いブロックの情報を使う必要性が発生する。

その代わりに、フェッチブロック毎に、1ビットのヒストリビットを挿入する。

5.2 過去3つのフェッチブロックからのパス情報

過去の3つのフェッチブロックからの情報 (lghist)

Predictorには使用される
履歴情報としては使用できない

これらのアドレス情報は、分岐予測テーブルを参照するための関数に使用される。

5.3 より長い履歴の使用

現在のコンフィグレーションにおいて、64K 2ビットエントリならば、2BC-gskewの構成において24ビットの履歴長が理想的。しかし、それぞれにおいて異なる履歴長を使用するならば、G0=17, G1=27, Meta=27が理想的だということが分かった。

lghistが使える場合はもっと短くても良いが、今回はそうは行かなかった。

FPGA開発日記

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

Alpha EV8の分岐予測機に関する論文を読む(3. ハイブリッド分岐予測の構成)