プロセッサアーキテクチャについて再度復習その8。今回からニューラル分岐予測器。ニューラルネットを用いた分岐予測器の続き。
読んでいるのは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
7. ニューラル分岐予測器と実装テクニック(続き)
Jimenez[51]は、パーセプトロンと経路ベースの分岐予測器の一般化である区分線形分岐予測器を示している[48, 49]。すべての分岐Bについて、それらの分岐予測器はBに至るすべてのパスのコンポーネントを追跡する。それはBの結果と一致するために履歴内の特定の位置での分岐の可能性を追跡する。予測は、現在のパスのすべてのコンポーネントの相関を集約することによって行われる。全体として、それらの分岐予測器は、予測された非分岐を予測された分岐から分離するために現在の分岐への各経路に対して１つずつ、複数の線形関数を生成する。したがって、それらの分岐予測器は、図32(c)に示すように、線形的に分離不可能な分岐に対して有効だ。ストレージの予算や待ち時間に制約がないと仮定すると、それらの分岐予測器は他の分岐予測器よりも高い予測精度を達成する。彼らはさらに先読みパイプラインと小さな履歴長の値を使用する彼らの分岐予測器の実用的な実装を提案する。また、パス履歴における分岐先アドレスおよび分岐先アドレスは、それぞれモジュロN, Mとして記憶される。パーセプトロンベースの分岐予測器 [48]は分岐(M = 1)に単一の線形関数を利用し、パスベースのニューラル分岐予測器 [49]はすべての分岐(N = 1)を予測するために単一のグローバル区分線形関数を利用する。区分線形分岐予測器の特殊な場合がある[51]。彼らは彼らの分岐予測器の実用的なバージョンも他の予測器よりも優れていることを示している。
Jimenezら[28]の提案。単層パーセプトロンベースの分岐予測器とは異なり、バックプロパゲーションベースの分岐予測器を備えた多層パーセプトロンは線形分離不可能な関数を学習できるため、パーセプトロン分岐予測器よりも高い「漸近的」精度を提供することが期待される。しかし、実際には、逆伝播ニューラル分岐予測器はトレーニングと予測の両方に非常に長い時間がかかるため、精度とパフォーマンスが低くなり、逆伝播ベースの分岐予測器は実行不可能で無効になる[53]。
Tarjanらの提案[23]。gshare, パスベース、パーセプトロン分岐予測器のアイデアを使用した、ハッシュ化パーセプトロン分岐予測器を提案する。この手法では、パーセプトロン分岐予測器は、分岐の相関を測定するためにそれぞれの重みを使用しており、これは使用する履歴の量がが増えるとテーブルと加算器の数が線形に増加し、またそれぞれのカウンタは十分に大きく取り、重みがいくつかの他の重みをオーバライドすることができるようにする。グローバル分岐履歴のセグメントをPCとXORすることによって、複数の分岐に同じ重みを割り当てる分岐予測器を提案している。グローバル分岐/パス履歴との単一の一致を行う代わりに、それらは複数の部分一致を実行するためにそれを複数のセグメントに分割する。さらに、パス履歴を使用する代わりに、分岐PCのみを使用する。ハッシュインデックスでは、すべてのテーブルが小さなgshare 分岐予測器として機能するため、それらの分岐予測器は同じ重みにマッピングされた線形的に分離不可能な分岐も予測できる。また、パスベースの分岐予測器と比較して、分岐予測器は同じ履歴の長さに使用する重み数を少なくする。これにより、相関のない複数の重みが強い相関を持つ1つの重みを上書きする可能性が低くなる。グローバルまたはパスベースの分岐予測器と比較して、それらの分岐予測器はチェックポイントが取られる状態の量を減らす短いパイプラインを持っている。 分岐予測器の待ち時間を減らすために、彼らは先送りパイプラインを使用する。パスベースおよびグローバルニューラル分岐予測器と比較して、加算器の数を減らしながら、分岐予測器は精度を大幅に向上させる。
Gaoらの提案[22]。パーセプトロンベースの分岐予測器では、パーセプトロン重みの値が相関強度を示すことに注意する。たとえば、図34は4つの分岐を示している。分岐1は2つのランダム変数によって決定され、分岐2は分岐1と同じ確率変数(k1)を使用しているため相関する。分岐3は分岐1の逆であり、分岐4はXORで分岐2と分岐3と関連している。パーセプトロン分岐予測器は、各分岐に8ビットGHRのパーセプトロンが1つ使用されている場合に使用される。 100M命令シミュレーションのパーセプトロン重み(w1-w8)と予測ミス率は、図34の右側に表示されている。明らかに、Branch1は前の分岐と相関がないので、その重みはわずかなランダム性を持つ。Branch2は、Branch1との相関および小さいランダムw2-w8値のために、大きなw1(GHR [0]との強い相関)を持つ。Branch3の結果はBranch1の結果によって正確に判定できるので、Branch3は単一の大きな重みw2(GHR [1]との強い相関)を持つ。Branch4は、前の分岐と非線形に相関するため、重みが大きくなる。
さらに、分岐予測器の入力を再組み立てすることによって、その精度を改善することができ、例えば、最近の2つの分岐のみがNのうち最も相関が高い場合、パーセプトロンサイズをNから2に減らすことができる。また、弱い相関をより強い相関に置き換えることができ、例えば冗長履歴を使用することができ、これは線形的に分離不可能な分岐を処理するのに役立つ。彼らは、各ワークロードタイプに適した入力ベクトルを見つけるために静的プロファイリングを使用する。これはアプリケーションタイプに基づいて実行時に選択される。さらに、入力および位相挙動の変化を説明するために、相関強度は実行時に定期的にテストされ、弱い相関の入力は強い相関の入力によって置き換えられる。彼らの技術は分岐予測器の正確さを著しく改善する。
Akkary[24]らの提案。パーセプトロンベースの分岐信頼度推定器(Confidence Estimator:CE)を提案する。パーセプトロンへの入力は、T/NT分岐がそれぞれ1 / -1として記録されるグローバル分岐履歴だ。信頼推定量の訓練は、リタイア時に(すなわち、非投機的に)行われる。 p(=1は正しく予測された分岐、-1は誤って予測された分岐)とc(1は高い信頼度が割り当てられた分岐、-1は低い信頼度が割り当てられた分岐)とが異なる符号を有する場合、重みは$$w[i] += p ∗ x[i]$$として更新される。正しい/誤った予測を使用して彼らの分岐予測器を訓練することは、分岐/非分岐の結果を使用するより高い精度を達成する[48]。また、彼らのCEは、予測ミスされた分岐の妥当な範囲を提供する。さらに、彼らは、CEの非バイナリ出力を2つの領域に分ける。強い自信と弱い自信がなく、それから分岐反転とパイプラインゲーティングをそれぞれ適用する。これにより、単一のハードウェアを使用して分岐予測器およびパイプラインゲーティングを向上させることができる。図35に示すパイプラインゲーティングアプローチでは、複数の信頼度の低い分岐がフェッチされると命令のフェッチが停止する。これにより、誤った命令がパイプラインに入るのを防ぎ、エネルギーを節約する。
