プロセッサアーキテクチャについて再度復習その9。ニューラル分岐予測器。

A Survey of Techniques for Dynamic Branch Prediction
- Sparsh Mittal

その2回目。パーセプトロン分岐予測器の実装について。調査したのは上記の論文にも引用されている原文"Dynamic Branch Prediction with Perceptrons"である。

https://www.cs.utexas.edu/~lin/papers/hpca01.pdf

論文 : Dynamic Branch Prediction with Perceptrons

6. 実装

ここでは、効率的な分岐予測器を実装する方法について提案する。

パーセプトロンの出力の計算

パーセプトロンの入力としては-1と1しか取り得ないため、内積の計算には乗算器は必要ない。その代わりに入力ビットが1である場合は加算し、-1であれば減算を行えばよい。この計算は乗算回路に似ている。1ビット毎の整数で計算される部分積を足し合わせて乗算の値を作る操作に似ている。さらに、予測には最上位の符号ビットのみ不要なため、出力の他のビットは予測の出力ほど高速に計算する必要はない。

学習

3.3節の学習のアルゴリズムはハードウェアにより効率的に実装できる。ループイタレーション内での依存関係が存在しないので、すべてのループは独立に並列に実行できる。 $x_i$ と $t$ は-1もしくは1であるため、ループの本体は「 $t=x_i$ ならば $x_i$ をインクリメントし、そうでなければデクリメントする」という簡単な実装に変換することができる。また、 $w_i$ は最大でも9ビットであるので：

for each bit in parallel
  if t = xi then
    wi := wi + 1
  else
    wi := wi  - 1
  end if

遅延

0.25umプロセスにおいて $54\times 54$ の乗算器は2.7nsの速度で実装される。これは700MHzの動作周波数において2サイクル程度に相当する。より履歴長が長くなると、我々の実装は $54\times 54$ の乗算器の実装に似てくる。ただし、データ相関のための部分積は最大で9ビットである。したがって、乗算回路に少なくとも1つ必要なキャリー伝搬加算器はそれほど深くする必要はない。我々の分岐予測器において、多くのハードウェアを使用するような実装である場合は最大でも2サイクルで予測を生成できる。ハードウェアのサイズを小さくすると、1サイクルで予測を生成できる。2サイクルは可変長パスの分岐予測器に要求されるサイクル数である[23]。遅延を削減するために、ハードウェアのパイプライン化を提案している。

Jimnezらの研究では、分岐予測器の遅延を削減するためにのいくつかの技法を提案している[13]。もし分岐命令がパーセプトロンが予測する前に到達した場合、もしくは予想した分岐アドレスが実際には誤っていた場合、小さなgshareのテーブルにより高速な分岐が行われる。2つのgshareテーブルを使用した似たような分岐予測器は、大きな分岐予測器を1つ使う場合に比べて47%高速化される。