プロセッサアーキテクチャについて再度復習その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ビットカウンタ分岐。
- 基本的なもの : 2-bit×1次元の分岐予測テーブル。テーブルのインデックスは分岐アドレスビットを使用する → 分岐成立・不成立を予測する。
- Section 3.1 : 2レベル分岐予測 : 分岐履歴と現在の分岐アドレスを両方使用して分岐成立・不成立を予測する。
- Section 3.2 : テーブルインデックスの取得方法 : 様々な要素と方法でインデックスの計算を行う。
- Section 3.3 : 複数のインデックス計算アルゴリズムを使い、複数の分岐予測テーブルにアクセスする。
- Section 3.4 : Biased Branchを使用する。
- Section 3.5 : 幾何履歴長分岐予測器を使用して、非常に大きな履歴を追跡する分岐予測器。
3.1 2レベル分岐予測器
使用するもの : 分岐履歴レジスタ(Branch History Register : BHR) , 分岐パタン履歴テーブル(Pattern History Table : PHT)
分岐パタン履歴テーブル PHT : 2ビットカウンタが並んだテーブル。どのインデックスを参照するかは、分岐履歴レジスタと現在のプログラムカウンタを使用する。分岐レジスタは同一のPHTを参照するため、グローバルPHTと呼ばれる。PHTがビットであったとすると、最近の
回の分岐結果が格納されている。過去の
回の分岐履歴を使って予測が行われる。例えば
で最近の分岐結果が
であり、
であったとすると
分岐履歴レジスタ BHR : Pビット定義されているとすると、PHTは だけエントリが用意される。
PHTでは、これらの個の分岐の与えられたパターンの最近の発生に対する分岐動作が格納され、そのうちの
個の分岐結果が予測に使用される。分岐は、パターンの最近のインスタンスに対する分岐応答を見ることによって予測されます。たとえば
で、最後の
回の分岐結果は1010011である場合(1=taken、0=not taken)を考える。
で、それぞれの最後の5回のそれぞれにおいて過去7つの分岐がパターン1010011を示し、分岐結果が取られたものと取られなかったものとの間で切り替えられた場合、レベル2履歴は10101となり、BPの次の分岐予測は"not-taken"となる。
Yehらは、分岐予測の実装として以下の3つの方式を提案した。
- GAgスキーム : グローバルBHRを1つ、グローバルPHTを1つ用意する。もっとも単純な方式だが、BHRとPHTで最も高い確率でエイリアシングが発生する。
- PAgスキーム : 分岐命令のアドレスに応じて複数のBHRから1つを選択し、BHRのビット列に応じてPHTを選択する。グローバルBHRの衝突によるエイリアシングの確立を削減することができるが、PHTのエイリアシングは削減することはできない。
- PApスキーム : 分岐命令のアドレスに応じて複数のBHRから1つを選択し、さらに分岐アドレスに応じて複数のPHTテーブルセットからPHTテーブルを選択する。PHTのエイリアシングも削減することができる。
PAgおよびPApでは、BHRテーブルはセットアソシアティブまたはダイレクトマッピングとして実装できる。
結果：
Yehら[16]はこれらをさらに一般化し、
- GHRの配置の方法 : G/P/S
- 割り当ての方法 : g/p/s
として、合計で9つの分類を行ってみる。
| Level-1 | GA | PA | SA |
|---|---|---|---|
| k分岐の格納 | Global Address History 最後のk回の分岐結果が見える |
Partial Address History 同じ分岐に対する最後のk回の分岐結果が見える |
Per-Set History 同じセットの最後のk回の分岐の結果が見える |
| Leve-2 | g | p | s |
|---|---|---|---|
| PHTの参照元 | すべての分岐命令から参照される | 各分岐命令から参照させる | 分岐のセットから参照される |
- Global History BPでは、必要なBHRは1つだけである。
- GAg : グローバルBHRを1つだけ持つ。Global PHTを持ち、BHRの値から参照するPHTを決定する。
- GAs : グローバルBHRを1つだけ持つ。Global PHTを複数持ち、分岐命令の分岐アドレスに応じてどのPHTにアクセスするかはセットアソシアティブにより決める。例えば、1KBのブロックを1セットとすると、ブロック内の分岐命令(最大256命令)は同じセットのメンバーとして構成される。
- GAp : グローバルBHRを1つだけ持つ。Global PHTを複数持ち、分岐命令の分岐アドレスをダイレクトマップしてどのPHTセットにアクセスするかを決める。
結果 : グローバル履歴分岐予測は効果的であることは間違いないが、エイリアシングを削減するために長いBHRが必要になるのでハードウェアコストとしては他の方式よりも効率が悪い。 PA(Per Address)分岐予測は、ループ毎に確実にBHRに分岐履歴を記録できるため精度が高い。また、エイリアシングが削減されるためにテーブルサイズを削減することができる。 SA(Per-set History)分岐予測はより高い精度を実現することができるが、Set毎にPHTを用意する必要があるため、ハードウェアコストがより大きくなる。
Skadronら[6]の提案 : BHRとPHTの分岐予測を使用しただけでは、グローバルな分岐(ループに関連しない分岐)とローカルな分岐(ループに関連する分岐)を区別することができず、そこで余計なエイリアシングや分岐予測の失敗が発生する可能性がある。これを防ぐために、PHTを参照するためのインデックの計算として、BHRのの結果に加えて、GHR(Global History Register)の値を結合したうえで算出する方法を提案した。GHRはすべての分岐予測の結果を格納しており、この値をPHT参照のためのアドレスインデックスに付け加えることで、グローバルな分岐とローカルな分岐を区別して分岐予測の失敗を防ぐことができる。これを、Yehらの用語を拡張して、「インデックスのMerge」の意味でMA分岐予測と呼んでいる。 さらに、BHRとPHTを用いる方式の問題点として、まずはBHRにアクセスした後PHTにアクセスするという2段階のシリアルアクセスが発生するというものである。このため全体のオーバヘッドが大きくなってしまうので、BHRとPHTに並行してアクセスする方法を考える。図5(b)のように、まずはGHRと分岐アドレスを使用してPHTのインデックスを計算し、可能性のあるすべてのPHTにアクセスする。同時にBHRにアクセスして、実際に使用するPHTの場所を計算する。最後に、複数のPHTの中からBHRに基づいて必要な分岐予測を取り出す、という方式である。この方式だとBHRとPHTに同時にアクセスできるが、PHTを分割したことによるオーバヘッドと、最後に結果をマルチプレクスする回路面積のオーバヘッドが問題となる。しかし、小規模なデザインでは、この方式はより高い精度を提供できる。
Sechrestらによると、規模の小さな分岐予測器の場合、エイリアスの影響により分岐予測の精度が大幅に低下してしまう。このため、gshare[91]やGA[16]の相関関係を利用する分岐予測の利点を無効化してしまうことがある。したがって、グローバル履歴ベースの分岐予測の場合は十分に大きなサイズを確保する必要がある。PAなどのローカル履歴ベースの分岐予測器の場合は、BHRの方がPHTよりも干渉が大きくなる傾向があり、全体としては、BHR、PHTのどちらも十分な容量を確保する必要が生じる。
Panら[79]の研究によれば、分岐予測はターゲットとなる分岐命令そのものだけでなく、その前に実行された分岐命令の結果によっても予測が可能であるということである。例えば、図6(a)では分岐B3は分岐B1とB2に相関しており、B1とB2の条件が真であれば分岐B3は分岐しないと正確に予測することができるが、図6(c)のように自分の履歴のみを用いたBPではそれを実現することはできない。B3の履歴を、図6(b)に示すように4つの可能性について分類することでより正確に予測することができるようになる。図6(d)は (過去2回の分岐履歴を使用する)、
(2ビット飽和カウンタの分岐予測器を使用する)の場合を示しており、
個の
ビット分岐予測器の結果から、1つの分岐予測を取り出すという方式を示している。この手法により、わずかなハードウェアオーバヘッドで高精度な分岐予測を実現することができる。
Chenら [82]はデータ圧縮をベースとする分岐予測の概念モデルを提案しており、データ圧縮の研究に基づく分岐予測の新たな利点について示している。2レベルもしくは相関を用いるBPは、データ圧縮における最適な予測器である"Partial Matchに基づく分岐予測"(PPM)の単純なものであるとしている。この分岐予測では、PPMが小規模のBTBを用いた2レベル予測器よりもわずかに高い精度を持っていると報告している。
