プロセッサアーキテクチャについて再度復習その2。分岐予測の続き。
読んでいるのは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
プロセッサアーキテクチャについて再度復習その2。分岐予測の続き。
読んでいるのは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
3.2 グローバルヒストリと分岐アドレスの両方を利用する方式
Mcfarling [81]らの報告:
- 同一のBPサイズに対して、グローバル履歴BPはローカル履歴BPよりも精度が低い
- BPサイズが1KBを超える場合にのみ、バイモーダルBPよりも高い精度が得られる。
- 小さいBPサイズの場合、バイモーダルBPで採用されている分岐アドレスビットが異なる分岐を効果的に区別できるため
- カウンタの数が増えるにつれて、頻繁に発生するすべての分岐が異なるカウンタにマップされるため、非常に大きなテーブルでは、分岐アドレスビットの情報値はゼロに近づく。
テーブルサイズが大きくなると、グローバルBPは異なる分岐命令を区別できるようになるが、分岐命令を区別したいならば、分岐命令の分岐アドレスを使用したほうが効果的。
Mcfarling[81]の提案した、グローバルなBHRのビットと分岐アドレスの下位ビットを活用する方式を提案した。
- gselect : 分岐アドレスの下位ビットとグローバルBHRのビットを連結してPHTの参照アドレスを算出する。
- gshare : 分岐アドレスの下位ビットとグローバルBHRのビットのXORを取ってPHTの参照アドレスを算出する。
表3は、それぞれ2つの共通グローバル履歴のみを持つ2つの分岐の例を示している。gselectは4つの場合を識別することはできていないが、gshareは4つの場合を識別することができる。ただし、テーブルのサイズが小さい場合はグローバル履歴を追加してしまうとエイリアシングが派生しやすくなってしまうため、gshareの精度は低くなる。
さらに、
- gshareとgselectの両方を実行して最良のBPを選択するというメタ分岐予測
- 2コンポーネントを仕様するハイブリッドBP(例えば、Bimodal[80] ＋ gshare)を提案する。
| Branch address | Global history | gselect index (4b+4b) | gshare index (8b XOR 8b) |
|---|---|---|---|
| 00000000 | 00000001 | 00000001 | 00000001 |
| 00000000 | 00000000 | 00000000 | 00000000 |
| 11111111 | 00000000 | 11110000 | 11111111 |
| 11111111 | 10000000 | 11110000 | 01111111 |
3.3 複数のインデックス関数の使用
Michaudら[86]の提案は、BPテーブルのエイリアシングはキャッシュミスと似ているので、エイリアシングはキャッシュ内のものと似ている競合、容量、および強制として分類することができることに注意してください。エイリアシングを除去するためのタグの使用は大きなオーバーヘッドを導入するので、「スキュー」BP設計を提案します。これは、スキューアソシアティブキャッシュ設計[87]と同様のメカニズム。衝突の正確な発生はマッピング機能に依存するので、それらのBPは複数の奇数(例えば、３)のBPバンクを使用するが、同じ情報(例えば、グローバル履歴および分岐アドレス)から得られる異なるハッシュ関数を使用する。各バンクはタグなしの予測器として機能し、並行してアクセスされます。すべてのバンクが予測を提供し、1つのバンクに干渉するバンクが他のバンクではそうしそうにないという考えに基づいて、多数決投票を使用して最終予測が選択されます。複数のバンク/テーブルに分割されたBPの場合、使用するインデックス機能[86、88]またはそれらによって使用される履歴の長さ[20、27]が異なる場合があることに注意してください。
BPを更新するために、彼らはすべてのバンクが更新される「全更新」方針と最終予測が正しいが最終予測が不正確であるときに間違った予測を提供するバンクが更新されない「部分更新」方針を考える。バンクが更新されます。 3バンクのBPは、1バンクの大規模BPと同じ精度を達成しながら、ほぼ半分のストレージリソースを必要とします。これは、競合するエイリアシングを減らしながらキャパシティエイリアシングを増やす複数のテーブルを使用することで、偏ったBPが冗長性を増すためです。さらに、不正確な予測を提供するバンクを更新しないことがそれがBPの全体的な有効性を増大させる他の何らかの流れに対する正しい予測に寄与することを可能にするので、部分更新方針は全更新方針よりも良好に機能する。
3.4 偏った分岐の強化
Changら[64]の提案。分岐を異なるストリームに分類する。
- 利用率に基づいて、使用する分岐予測器を分類する。
- 傾向 : 履歴レジスタBHRが小さいほどエイリアシングが減少するPHTの数が多いことから、偏った分岐は短いBHRを持つ分岐予測器によってより適切に予測させることができる。
- 傾向 : 混合分岐、偏りのない分岐は、多くの実行状態を区別できる長いBHRを有する分岐予測器によって正確に予測することができる。
Leeら[7]は、図7に示されている「バイモーダル」BPを提示しています。それらのBPは、レベル2カウンターテーブルを2つの部分に分けています。"Taken"および"Not Taken"の「方向予測器」。どの履歴パターンでも、各部分から1つのカウンターが選択されます。これらの中から、別の「選択予測器」の入力に基づいて、予測を行うために1つのカウンターが最終的に選択されます。選択予測器は、分岐アドレスによってのみ索引付けされます。 2つのグループのGHパターンの分類は、選択予測器のアドレスごとの偏りに基づいて行われます。それらは部分更新ポリシーを使用します。そこでは、選択されたカウンターのみが分岐結果に基づいて更新されます。選択が分岐結果と反対であるが選択されたカウンタの最終予測が正しい場合を除いて、それらは常に選択予測器を更新する。全体として、バイモーダルBPは、負のエイリアシングを示す分岐を分離し、ニュートラル/有益なエイリアシングを示す分岐をまとめます。有害なエイリアシングを除去することによって、それらの技術は高い予測精度を達成する。
Leeら[7]の提案 : Bimodal分岐予測器。レベル2のカウンタテーブルを2つに分ける。
- "Taken"および"Not Taken"の分岐予測器に分ける。どのような履歴パタンでも、各部分から1つのカウンタが選択される。これらは、最終的に選択予測器(choice predictor)によってどちらを使用するかを選択する。選択予測器は分岐アドレスのみで選択される。
- 2つのグループのGHパタンの分類は、選択されたカウンタのみが分岐結果に基づいて更新される。
- 最終的な選択が分岐結果と反対であり、選択されたカウンタの最終予測が正しい場合を除き、分岐予測器が予測を更新する。
- Bimodal分岐予測は、負のエイリアシングを除去し、これにより高い予測精度を達成することができる。
Sprangleら[19]は、PHTエントリの解釈を変更することによって有害な干渉を有益なケースまたは無害なケースに変換する手法を提案します。図8は、合意予測値と呼ばれるBPを示しています。各分岐に対して、分岐の最も可能性の高い結果を予測するバイアスビットを追加します。 (従来の方式におけるように)分岐の方向を予測する代わりに、それらの技術におけるPHTカウンタは、分岐結果がバイアスビットと一致するかどうかを予測する。分岐が解決されると、分岐方向がバイアスビットと一致した場合にPHTカウンタが増加し、逆の場合も同様です。彼らは最初の実行で分岐の方向にバイアスビットを設定します。バイアスビットの適切な選択により、同じPHTエントリにマッピングする2つの分岐のカウンタは、同じ方向に更新される可能性がより高い。状態に同意します。
Sprangleら[19]の提案 : PHTエントリの解釈を変更することによって、有害なエイリアシングを有益な場合と無害な場合に変換する手法。
- 各分岐に対して、分岐の最も可能性の高い結果を予測するバイアスビットを追加する。PHTカウンタは、分岐結果がアイアスビットと一致するかどうかを予測する。
- 分岐が解決されたとき、分岐方向がバイアスビットと一致した場合にPHTカウンタが増加し、不一致の場合はPHTカウンタが減少する。
- バイアスビットを適切に選択することにより、同じPHTエントリにマッピングしている2つの分岐予測のカウンタは同じ方向に更新される可能性がより高い。
- 数学的な説明 : 分岐成立=T, 分岐不成立=NT, 一致=A, 不一致=D の確率を考える。分岐B1と分岐B2を考える。
3.5 Geometric history length BPs
Seznec[27]の提案 : GEHL (Geometric history length : 幾何学的履歴長) 分岐予測器
- 分岐予測器を複数(
)個用意する。分岐テーブルはそれぞれ
と名付ける。
- 分岐予測器の参照インデックス : 分岐アドレスとハッシュされたグローバルパス・分岐履歴から計算する。
- 表4に基づいて、各テーブルの長さを決定する。例えば、
の分岐予測器を仮定し、
かつ
の場合は、テーブルの長さ
となる。
したがって、5つのテーブルは最大で16個の履歴ビットを使用してインデックスされ、それでもなお128ビットの履歴との相関関係を捉えている。
| 予測 | 各テーブル |
| テーブルの参照 | テーブルT0は分岐アドレスを用いて参照される。テーブル |
予測器は、予測が誤った場合、もしくは の絶対値が閾値を下回った場合に更新される。分岐予測器は、履歴長を調整して、更新時のエイリアシングが大きい場合は短い履歴長を使用し、エイリアシングが小さい場合には長い履歴長を使用する。この分岐予測器の問題点は、予測器自体の複雑さと、予測ミスにより復元しなければならない大量の状態をチェックポイントする必要性である。全体的に、GEHL分岐予測器は高い精度を提供することができる。
Seznecら[20]の提案 : 現在のTAGE(tagged geometric history length : タグ付き幾何履歴長)分岐予測器
TAGE分岐予測器の構成要素 :
: 基本予測器。2ビットの倍モーダルカウンタ。
: 部分タグ付き予測器。インデックスに使用するのは
ビット分のグローバル履歴テーブル。以下の要素を持っている。
- 符号付き2ビットカウンタ
- タグ
- U(useful) カウンタ
図9は、5つの成分を含むTAGE BPを示している。
ベースBPとタグ付きBPが同時にアクセスされ、複数のTAG付BPがヒットした場合は最も長い履歴長のものが選択される。
アップデート時には、新たな予測情報が最終的な予測結果と異なる場合、"U"カウンタがアップデートされる。
- 最終的な予測結果と一致した場合 : インクリメント
- 最終的な予測結果と不一致であった場合 : デクリメント
定期的に"U"カウンタはリセットされ、Uselfulフラグは定期的に使用できなくなる。 の"Pred"カウンタは、予想の一致、不一致でアップデートされる。さらに、予測が誤っており、 c<M の場合は、 Tk(c < k < M) エントリに割り当てられる。
コンポーネントの予測が、「新たに割り当てられた」エントリから送られてきたならば、この予測はまだ誤った予測を行う可能性があるため、別の予測器の値が使用される可能性が高い。TAGE分岐予測器はこれまでの分岐予測器よりも性能が高く、従ってこの「幾何履歴長、部分タグ」の方式が、加算器のツリーと比較して最もコスト効率が良い分岐予測器となる。また、8タグ以上の分岐予測器を使用しても性能上意味がない。Tcコンポーネントと予測カウンタを観測することによって、分岐予測ミスが発生する確率を計算することができる。
比較 : ハードウェアの比較として、gshareとパーセプトロンBPはそれぞれ20から60個の分岐記録について相関がある。一方で、GEHLとTAGEは200から2000個の分岐記録について相関がある。単一のBPについては、TAGE分岐予測器は最も精度の高い分岐予測器であると考えられている。また、TAGE分岐予測器は複数のタグ付され予測器を使用するのに対して、他の分岐予測器は1つのタグ分岐予測器を使用する。
過去の記事
