FPGA開発日記

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

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

プロセッサアーキテクチャについて再度復習その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ライクな疑似コードを用いて説明する。

パーセプトロンの分岐予測器は、グローバル履歴を保持するためのシフトレジスタを持っており、実行された分岐の結果を保持しているという面では他の分岐予測器と同一である。

パーセプトロンの分岐予測器は、n\times (h+1)ビットの整数重みビットW[0..n-1, 0..h]を保持している。nは設計におけるパラメータである。重みは通常8ビットである。行列の行は(h+1)長であり、重みベクトルと呼ばれる。各重みベクトルは1つのパーセプトロンの重みを保持しており、この単位でパーセプトロンの学習が行われる。重みベクトルw[0..h]では、最初の重みw[0]はバイアスである。BooleanベクトルG[1..h\in {1..h}\times {\text{taken}, \text{not taken}}]が、グローバル履歴レジスタである。

3.1.1 予測とアップデートのアルゴリズム

図2では、オリジナルのパーセプトロンの分岐予測器についての疑似コードを示している。予測アルゴリズムはアドレスpcに対してBooleanの値を返す。

分岐の結果が分かれば、学習アルゴリズムが動作し分岐予測がアップデートされる。トレーニンアルゴリズムは整数パラメータ\thetaが渡さる。\thetaはロングた無の精度とフェーズ動作のトレードオフのための値であり、\theta = \lfloor 1.93h + 14\rfloor が最適な値であると言われる。したがって、\thetaは履歴長によって与えられる固定値である。一度分岐の結果が分かると、パーセプトロン分岐予測器がアップデートされる。

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

3.1.2 実装

パーセプトロン分岐予測器の実装方法についていくつか検討した。

行列 Wはタグのないダイレクトマップメモリとして実装した。 n個のブロックを持ち、 i番目のブロックには h個の8ビットの重みベクトルが格納されている。したがって、分岐予測が必要な時には、アドレスpcに該当するメモリブロックが呼び出される。

重みデータの符号を反転させる必要がある場合、ビット全体のビット反転に置き換えても性能に対する影響はあまりない。これにより予測の計算に必要なレイテンシを削減することができる。

 y_\text{out}の計算にはWallaceツリーの加算器を使用した。通常の加算器を用いると O(h)の遅延が必要だが、 O(\log h)の遅延で完了させることができる。

3.1.3 パーセプトロンベースの分岐予測器の弱点

パーセプトロン分岐予測器の弱点はその長いレイテンシである。高速な演算器を使用しても、 y_\text{out}の計算に必要なレイテンシは、一般的な不快パイプラインを持つマイクロアーキテクチャに必要な演算回路のレイテンシよりも長くなる。このようなパイプラインでは、分岐予測器の性能が非常に重要[8]で、レイテンシを隠ぺいするために特殊な方法が使用されている[7]。

3.2 パスベースのニューラル分岐予測器

パーセプトロン分岐予測器の代替手法として、ニューラル分岐予測器を提案する。この分岐予測器は重みベクトルの選択を分岐のパスに応じて選択する。これまでは分岐アドレスのみに基づいて重みを選択していたが、これよりも分岐の精度を高めることができる。この手法は2つの利点を持つ。まず、 y_\text{out}の計算は分岐予測よりも前に完了するためレイテンシを短縮できる。また、パスの要素が実行されると、すぐに次のステップに進むことができる。次に、分岐予測器にパスの情報が埋め込まれるので、予測精度を向上させることができる。

3.2.1 直観的な説明

新しい分岐予測器の構成は、パーセプトロン分岐予測器の構成と非常に似ている。行列 Wに重みベクトルを保持し、分岐命令がフェッチされて分岐予測が必要な場合、1つの重みベクトルが Wから読み込まれる。しかし、0番目の重み、つまりバイアス重みのみが現在の分岐予測に使用さえっる。最後の h回の分岐に基づいて分岐予測の加算が行われ、各課sんは前の分岐予測の最中に実行される。

図3はパーセプトロン分岐予測器(a)と新しい分岐予測器(b)の違いを示している。この図では、2つの分岐予測器が分岐 b _ {t-7}から b_tまでを通過するにあたり、どのように予測を行っているかを示している。縦の軸は各ステップにおいてアクセスされる W要素を示している。各予測器は分岐履歴を h=7まで保持できる。各予測では、分岐 b_tの予測に使用される重みは x[0..7]である。パーセプトロン分岐予測器は、時間 tにおいてベクトルにアクセスし、各重みを足し合わせて一度に y_outを計算する。一方で、新しい分岐予測器の x[0..7]の重みは、これまでの分岐 b _ {t-7}から b_tに関連づいた主mいの要素によって組み立てられる。阿多アリ氏分岐予測器では、 y _ {out}の計算中にその被加数は保持される。時間 tにおいて、残りの被加数は重みバイアス x[0]のみである。分岐 b _ {t-i}によって生成された予測は、 b_tにとっては i番目に最近の投機ヒストリビットであることに注意する。図3では、重みの位置 y[0..7]と z[0..7]は過去の分岐 b _ {t-1} b _ {t-2}の計算に使用されていることに注意する。

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

2つの分岐予測器のもう一つの違いは、予測に使われる重みの探索である。オリジナルのパーセプトロン分岐予測器では、重みベクトルの各重みは b_jに属しており、 b_tの予測に使用されている。新しい分岐予測器では、 b_jのためにフェッチされた重みベクトル b_j i番目の重みは、分岐 b _ {i+j}の予測のために使用されるということである。

3.2.2 予測アルゴリズム

図4は現在の分岐と以降の h個の分岐を予測してアップデートするためのアルゴリズムを示している。 W, n, hはこれまでに定義した。 SR[0..h]と R[0..h]を、 h+1個の整数のベクトルとする。 Wの最初のカラムはバイアス重みである。 SR[h-j]には現在のものから j番目に後の分岐予測に使用される被加数である。 SRは投機的アップデートされる。 Rはアップデートアルゴリズムにて説明するが、投機的でない SRの値を保持している。 SRは部分和を保持するためのキューであると考える。

3.2.3 アップデートのアルゴリズム

パスベースのニューラル分岐予測器の更新は、概念的には元のパーセプトロン分岐予測器の更新に似ている。 ただし、新しい更新アルゴリズムは、各重みベクトルが元の分岐予測器のように1つの分岐ではなく、複数の分岐 hに関連付けられているという事実に対処する必要がある。 分岐 b_tが完了し、その結果を使用して分岐予測器を更新する準備ができている場合、 b_tに関連付けられている重みベクトルのほとんどは、まだ完了していない将来の分岐を予測するために使用されるため、更新できない。 したがって、行列 W h+1個の独立にアドレス指定可能な高速メモリとして設計する。分岐予測器が更新されると、対応する重みに個別にアクセスできる。 バイアスの重みを持つメモリは、低レイテンシで最終的な y _ {out}値を計算する論理に最も近い場所に位置される。

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