FPGA開発日記

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

高性能プロセッサの分岐予測のサーベイ論文を読んで分岐予測について学ぶ (8. ニューラル分岐予測器1)

プロセッサアーキテクチャについて再度復習その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. ニューラル分岐予測器と実装テクニック

ニューラル分岐予測器に関しては、 - パーセプトロン[48] - バックプロパゲーション[28、52、53] - 学習ベクトル量子化[52] - その他のニューラル分岐予測器 [28]

を使った分岐予測器が提案されている。

7.1 Neural BPs

Jimenezらの提案[48]。各分岐を表現するために単層パーセプトロン、単純NNを使用するパーセプトロンベースの分岐予測器を提案する。パーセプトロンは、異なる分岐間の相関度を示す複数の重み($w$)を格納するベクトルだ。前の分岐(1 =成立、-1 =成立しない)の結果がパーセプトロンへの入力になる。常に1である入力$x_0$はバイアス入力を提供する。出力$Z$はお元入力のない席として計算され、$Z = w_0 + \sum w_ix_i$である。$Z$が正か負かによって、分岐が成立と予測するか、不成立と予測するかが決まる。分岐結果によって、要素の重みはそれぞれ増加/減少する。図31に、パーセプトロン分岐予測器の機能の例を示す。

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

2レベル分岐予測器のサイズは、分岐履歴レジスタの長さに応じて指数関数的に大きくなるが、パーセプトロン分岐予測器のサイズは履歴の長さに対して直線的にしか増加しない[28]。したがって、これまでの分岐予測器に比較してはるかに長い履歴を保存することができる。

それらの分岐予測器は、多くの「線形分離」可能な分岐を持つアプリケーションに適している。

超平面を使用してすべての偽のインスタンスをすべての真のインスタンスから分離することができるような$n+1$の重みの値が見つかる場合、変数$x_{1...n}$に対するブール関数は線形分離可能だ。

  • AND関数は線形分離可能であるのに対し、
  • XOR関数は線形分離はできない。

これを図32(a) - (b)に示す。パーセプトロン分岐予測器はAND関数ではうまく機能するが、XOR関数ではうまくいかない。したがって、線形分離不可能な関数の場合、パーセプトロン分岐予測器の精度は低くなるが、以前の分岐予測器は十分な時間が与えられれば任意のブール関数を学習できる。したがって、一般的なアプリケーションでは、それらの分岐予測器は単一の分岐予測器としてではなく、ハイブリッド分岐予測器の構成要素として有用だ。彼らの分岐予測器のもう一つの制限は、その長い待ち時間だ。

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

Jimenez[49]は、パスベースのニューラル分岐予測器を提案した。これは「先行パイプライン(ahead pipelining)」アプローチを使用して待ち時間を短縮する。彼らの分岐予測器は、分岐アドレスだけではなく、分岐に至るパスに応じてその重みベクトルを選択する。これはより高い精度を達成するのに役立つ。パーセプトロン分岐予測器と同様に、それらのパスベースの分岐予測器は重みベクトルの行列を維持する。分岐を予測するには、図33に示すように、重みベクトルが読み込まれ、予測を行うためにその偏りの重みだけをRunning Sumに追加する必要がある。このRunning Sumは、複数の前の分岐に対して更新される。したがって、それらの先行パイプライン化アプローチは、時間の経過と共に計算をずらすので、予測が行われる前であっても計算を開始することができる。予測は複数サイクルで完了することができるため、分岐予測器オーバーライドの必要性がなくなる。彼らのアプローチの限界はそれが正確さを減らすことができるその重みを選ぶために分岐のPCを使わないことだ。また、先読みパイプライン化は、古い/部分的な情報で予測プロセスを開始し、予測プロセスで最新の情報を継続的に混合することによって機能するが、先読みパイプライン化アプローチでは限られた新しい情報しか使用できない[23]。さらに、分岐の誤った予測では、大量のプロセッサ状態をチェックポイントにロールバックする必要がある。

Jimenez[51]は、パーセプトロンと経路ベースの分岐予測器の一般化である区分線形分岐予測器を示している[48, 49]。すべての分岐Bについて、それらの分岐予測器はBに至るすべてのパスのコンポーネントを追跡する。それはBの結果と一致するために履歴内の特定の位置での分岐の可能性を追跡する。予測は、現在のパスのすべてのコンポーネントの相関を集約することによって行われる。全体として、それらの分岐予測器は、予測された非分岐を予測された分岐から分離するために現在の分岐への各経路に対して1つずつ、複数の線形関数を生成する。したがって、それらの分岐予測器は、図32(c)に示すように、線形的に分離不可能な分岐に対して有効だ。ストレージの予算や待ち時間に制約がないと仮定すると、それらの分岐予測器は他の分岐予測器よりも高い予測精度を達成する。彼らはさらに先読みパイプラインと小さな履歴長の値を使用する彼らの分岐予測器の実用的な実装を提案する。また、パス履歴における分岐先アドレスおよび分岐先アドレスは、それぞれモジュロN, Mとして記憶される。パーセプトロンベースの分岐予測器 [48]は分岐(M = 1)に単一の線形関数を利用し、パスベースのニューラル分岐予測器 [49]はすべての分岐(N = 1)を予測するために単一のグローバル区分線形関数を利用する。区分線形分岐予測器の特殊な場合がある[51]。彼らは彼らの分岐予測器の実用的なバージョンも他の予測器よりも優れていることを示している。

Jimenezら[28]の提案。単層パーセプトロンベースの分岐予測器とは異なり、バックプロパゲーションベースの分岐予測器を備えた多層パーセプトロンは線形分離不可能な関数を学習できるため、パーセプトロン分岐予測器よりも高い「漸近的」精度を提供することが期待される。しかし、実際には、逆伝播ニューラル分岐予測器はトレーニングと予測の両方に非常に長い時間がかかるため、精度とパフォーマンスが低くなり、逆伝播ベースの分岐予測器は実行不可能で無効になる[53]。

Tarjanらの提案[23]。gshare, パスベース、パーセプトロン分岐予測器のアイデアを使用した、ハッシュ化パーセプトロン分岐予測器を提案する。この手法では、パーセプトロン分岐予測器は、分岐の相関を測定するためにそれぞれの重みを使用しており、これは使用する履歴の量がが増えるとテーブルと加算器の数が線形に増加し、またそれぞれのカウンタは十分に大きく取り、重みがいくつかの他の重みをオーバライドすることができるようにする。グローバル分岐履歴のセグメントをPCとXORすることによって、複数の分岐に同じ重みを割り当てる分岐予測器を提案している。グローバル分岐/パス履歴との単一の一致を行う代わりに、それらは複数の部分一致を実行するためにそれを複数のセグメントに分割する。さらに、パス履歴を使用する代わりに、分岐PCのみを使用する。ハッシュインデックスでは、すべてのテーブルが小さなgshare 分岐予測器として機能するため、それらの分岐予測器は同じ重みにマッピングされた線形的に分離不可能な分岐も予測できる。また、パスベースの分岐予測器と比較して、分岐予測器は同じ履歴の長さに使用する重み数を少なくする。これにより、相関のない複数の重みが強い相関を持つ1つの重みを上書きする可能性が低くなる。グローバルまたはパスベースの分岐予測器と比較して、それらの分岐予測器はチェックポイントが取られる状態の量を減らす短いパイプラインを持っている。 分岐予測器の待ち時間を減らすために、彼らは先送りパイプラインを使用する。パスベースおよびグローバルニューラル分岐予測器と比較して、加算器の数を減らしながら、分岐予測器は精度を大幅に向上させる。

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