プロセッサアーキテクチャについて再度復習その10。ニューラル分岐予測器の続き。
- A Survey of Techniques for Dynamic Branch Prediction
- Sparsh Mittal
https://arxiv.org/pdf/1804.00261.pdf
パーセプトロン分岐予測器に対して、そのレイテンシの問題を改良した「高速パスベースニューラル分岐予測器」について論文を読む。 最初は何のことかわからなかったけど、しっかり読んでみると確かに面白いアイデアだなと思う。
論文 : Fast Path-Based Neural Branch Prediction
ニューラルネットワークに基づくマイクロアーキテクチャの分岐予測は、近年注目を集めている。 しかし、従来の分岐予測器よりも優れた精度というだけでは、高いレイテンシによるコストを相殺するにはまだ不十分であり、ニューラル予測は実用的ではない。 本論文では、両方向から問題を解決する新しいニューラル分岐予測器を提案する。これは、以前のニューラル予測器よりも正確ではるかに高速です。 分岐予測器は、パスとパターン履歴を組み合わせて、以前の分岐予測器に固有の制限を克服することにより精度を向上させる。 また、以前のニューラル予測よりもレイテンシがはるかに短くなる。 その結果、従来の分岐予測器よりもはるかに優れた精度を備えた分岐予測器がであり、またレイテンシはインダストリアルな分岐予測器に匹敵します。 私たちのシミュレーションは、パスベースのニューラル分岐予測器が、アグレッシブに高速化されるマイクロアーキテクチャのサイクルごとの命令(IPC)レートを元のパーセプトロン分岐予測器よりも16%向上させることを示している。
3. パスベースのニューラル分岐予測器
本節では、これまでのニューラル分岐予測器について簡単にレビューを行い、パスベースのニューラル分岐予測器について直感的な動機を与える。その後、パスベースのニューラル分岐予測器について詳細を説明する。
3.1 パーセプトロンを用いた分岐予測器
パーセプトロンの学習を用いたパーセプトロンの分岐予測器は、条件分岐命令における分岐の方向を予測するために使用される。まずは、パーセプトロン分岐予測器の設計について、Algolライクな疑似コードを用いて説明する。
パーセプトロンの分岐予測器は、グローバル履歴を保持するためのシフトレジスタを持っており、実行された分岐の結果を保持しているという面では他の分岐予測器と同一である。
パーセプトロンの分岐予測器は、ビットの整数重みビット]を保持している。は設計におけるパラメータである。重みは通常8ビットである。行列の行は長であり、重みベクトルと呼ばれる。各重みベクトルは1つのパーセプトロンの重みを保持しており、この単位でパーセプトロンの学習が行われる。重みベクトル]では、最初の重み]はバイアスである。Booleanベクトル\in {1..h}\times {\text{taken}, \text{not taken}}]が、グローバル履歴レジスタである。
3.1.1 予測とアップデートのアルゴリズム
図2では、オリジナルのパーセプトロンの分岐予測器についての疑似コードを示している。予測アルゴリズムはアドレスに対してBooleanの値を返す。
分岐の結果が分かれば、学習アルゴリズムが動作し分岐予測がアップデートされる。トレーニングアルゴリズムは整数パラメータが渡さる。はロングた無の精度とフェーズ動作のトレードオフのための値であり、 が最適な値であると言われる。したがって、は履歴長によって与えられる固定値である。一度分岐の結果が分かると、パーセプトロン分岐予測器がアップデートされる。
3.1.2 実装
パーセプトロン分岐予測器の実装方法についていくつか検討した。
行列はタグのないダイレクトマップメモリとして実装した。個のブロックを持ち、番目のブロックには個の8ビットの重みベクトルが格納されている。したがって、分岐予測が必要な時には、アドレスpcに該当するメモリブロックが呼び出される。
重みデータの符号を反転させる必要がある場合、ビット全体のビット反転に置き換えても性能に対する影響はあまりない。これにより予測の計算に必要なレイテンシを削減することができる。
の計算にはWallaceツリーの加算器を使用した。通常の加算器を用いるとの遅延が必要だが、の遅延で完了させることができる。
3.1.3 パーセプトロンベースの分岐予測器の弱点
パーセプトロン分岐予測器の弱点はその長いレイテンシである。高速な演算器を使用しても、の計算に必要なレイテンシは、一般的な不快パイプラインを持つマイクロアーキテクチャに必要な演算回路のレイテンシよりも長くなる。このようなパイプラインでは、分岐予測器の性能が非常に重要[8]で、レイテンシを隠ぺいするために特殊な方法が使用されている[7]。
3.2 パスベースのニューラル分岐予測器
パーセプトロン分岐予測器の代替手法として、ニューラル分岐予測器を提案する。この分岐予測器は重みベクトルの選択を分岐のパスに応じて選択する。これまでは分岐アドレスのみに基づいて重みを選択していたが、これよりも分岐の精度を高めることができる。この手法は2つの利点を持つ。まず、の計算は分岐予測よりも前に完了するためレイテンシを短縮できる。また、パスの要素が実行されると、すぐに次のステップに進むことができる。次に、分岐予測器にパスの情報が埋め込まれるので、予測精度を向上させることができる。
3.2.1 直観的な説明
新しい分岐予測器の構成は、パーセプトロン分岐予測器の構成と非常に似ている。行列に重みベクトルを保持し、分岐命令がフェッチされて分岐予測が必要な場合、1つの重みベクトルがから読み込まれる。しかし、0番目の重み、つまりバイアス重みのみが現在の分岐予測に使用さえっる。最後の回の分岐に基づいて分岐予測の加算が行われ、各課sんは前の分岐予測の最中に実行される。
図3はパーセプトロン分岐予測器(a)と新しい分岐予測器(b)の違いを示している。この図では、2つの分岐予測器が分岐からまでを通過するにあたり、どのように予測を行っているかを示している。縦の軸は各ステップにおいてアクセスされる要素を示している。各予測器は分岐履歴をまで保持できる。各予測では、分岐の予測に使用される重みは]である。パーセプトロン分岐予測器は、時間においてベクトルにアクセスし、各重みを足し合わせて一度にを計算する。一方で、新しい分岐予測器の]の重みは、これまでの分岐からに関連づいた主mいの要素によって組み立てられる。阿多アリ氏分岐予測器では、の計算中にその被加数は保持される。時間において、残りの被加数は重みバイアス]のみである。分岐によって生成された予測は、にとっては番目に最近の投機ヒストリビットであることに注意する。図3では、重みの位置]と]は過去の分岐との計算に使用されていることに注意する。
2つの分岐予測器のもう一つの違いは、予測に使われる重みの探索である。オリジナルのパーセプトロン分岐予測器では、重みベクトルの各重みはに属しており、の予測に使用されている。新しい分岐予測器では、のためにフェッチされた重みベクトルの番目の重みは、分岐の予測のために使用されるということである。
3.2.2 予測アルゴリズム
図4は現在の分岐と以降の個の分岐を予測してアップデートするためのアルゴリズムを示している。はこれまでに定義した。]と]を、個の整数のベクトルとする。の最初のカラムはバイアス重みである。]には現在のものから番目に後の分岐予測に使用される被加数である。は投機的アップデートされる。はアップデートアルゴリズムにて説明するが、投機的でないの値を保持している。は部分和を保持するためのキューであると考える。
3.2.3 アップデートのアルゴリズム
パスベースのニューラル分岐予測器の更新は、概念的には元のパーセプトロン分岐予測器の更新に似ている。 ただし、新しい更新アルゴリズムは、各重みベクトルが元の分岐予測器のように1つの分岐ではなく、複数の分岐に関連付けられているという事実に対処する必要がある。 分岐が完了し、その結果を使用して分岐予測器を更新する準備ができている場合、に関連付けられている重みベクトルのほとんどは、まだ完了していない将来の分岐を予測するために使用されるため、更新できない。 したがって、行列を個の独立にアドレス指定可能な高速メモリとして設計する。分岐予測器が更新されると、対応する重みに個別にアクセスできる。 バイアスの重みを持つメモリは、低レイテンシで最終的な値を計算する論理に最も近い場所に位置される。