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

A Survey of Techniques for Dynamic Branch Prediction
- Sparsh Mittal

で、パーセプトロン分岐予測器なんて勉強したこともなかったので、サーベイ論文ではなく原文に当たることにした。調査したのは上記の論文にも引用されている原文"Dynamic Branch Prediction with Perceptrons"である。

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

論文 : Dynamic Branch Prediction with Perceptrons

3. パーセプトロンを用いた分岐予測器

本セクションでは、我々の分岐予測器を理解するために必要なバックグラウンドについて説明する。パーセプトロンについて説明し、どのように我々の分岐予測器に使用するのかについて説明する。また、この分岐予測器の利点と欠点について説明する。我々の手法は、基本的に2レベル分岐予測器であり、パタンヒストリテーブルをパーセプションのテーブルに置き換えるだけである。

3.1 なぜパーセプトロンなのか？

パーセプトロンは、分岐予測器において自然な選択肢であり、その理由はパーセプトロンは効率的にハードウェアに実装吸うことができるからである。ニューラルネットワークのそれ以外の形態としては、バックプロパゲーションや、決定木などの機械学習向けの手法として利用されているが、実装コストが大きすぎるために適切ではない。この論文では、ADALINE[25]やHebb learning[8]などの他のシンプルなニューラルアーキテクチャについても検討したが、パーセプトロンが最も効率が良かった(ADALINEはハードウェアの効率が悪く、Hebbは精度が低い)。

パーセプトロンの一つの利点は、ハードウェアが学習した値の相関などの「重み」などの値を調べることによって、ハードウェアが生成した予測の意味を簡単に理解できるからである。対照的に、ニューラルネットワークの多くの形式の弱点んは、ニューラルネットワークが予測を行うまでに、どのようにして決定したかを理解するのが困難なことである。ニューラルネットワークからルールを抽出する技術も提案されている[21]が、その制度はあまり高くない。パーセプトロンはこのような不透明性が発生しない; パーセプトロンの決定プロセスは、簡単な数式により理解することができる。この特徴については、5.7章で議論する。

3.2 パーセプトロンはどのように働くのか

パーセプトロンは1962年に提案された、脳の学習機能を模擬した手法である。ここでは、最もシンプルなパーセプトロン[2]である「単一レイヤパーセプトロン」を使用する。単一レイヤパーセプトロンでは、1つの人工ニューロンと、複数の入力ユニットと、1つの出力ユニットを持っている。我々の用途では、重みは符号付きの整数である。出力は重みベクトル $w _ {0..n}$ と入力ベクトル $x_{1..n}$ の内積である( $x _ 0$ は常に1であり、「バイアス値」を入力している)。パーセプトロンの出力 $y$ は以下のようにして計算できる :

$y = w_0 + \sum_{i=1}^n x_iw_i$

パーセプトロンの入力はバイポーラであり、つまり各 $x _ i$ は-1あるいは1であり、それぞれ分岐しない、分岐するに相当する。パーセプトロンにおいて負数は分岐しないと予測したことを意味し、正数は分岐すると予測したことを意味する。

f:id:msyksphinz:20190807002716p:plain — 図1. パーセプトロンモデル。入力値 $x _ {1}, ... x _ {n}$ は重みを通じてパーセプトロンに接続され、内積が計算される。 $w_0$ はバイアスに対する重みである。(本論文より抜粋)

図1. パーセプトロンモデル。入力値 $x _ {1}, ... x _ {n}$ は重みを通じてパーセプトロンに接続され、内積が計算される。 $w_0$ はバイアスに対する重みである。(本論文より抜粋)

3.4 パーセプトロンの学習

パーセプトロンの出力が一度計算されると、以下のアルゴリズムによってパーセプトロンが学習される。分岐が成立しなかった場合は $t=-1$ とし、分岐が成立した場合は $t=1$ とする。 $\theta$ はスレッショルドであり、学習アルゴリズムによって学習がどれくらい十分に完了したかを示している。

if sign(y_out) != t or |y_out| <= theta then
  for i:= 0 to n do
    w_i := w_i + t*x_i
  end for
end if

$t$ と $x_i$ は常に-1か1のため、このアルゴリズムでは分岐の結果が $x_i$ と合致した場合に $i$ 番目の重みがインクリメントされ、そうでない場合はデクリメントされる。緒間的には、全体的に合致する、つまり正の相関がある場合は値が大きくなる。そし、全体的合致しない、つまり負の相関がある場合は、値が小さくなる。どちらの場合でも、重みの値は予測に対して大きな影響を与える。これらに対して弱い相関がある場合は、重みの値はは0に近づき、パーセプトロンの出力に対する影響度が落ちていく。

3.4 線形分離可能性

パーセプトロンの制約は、「線形分離可能」な関数に対してのみ学習が可能であると言う事である[8]。つまり、 $n$ 次元の空間に対するすべてのパーセプトロンの入力を想像すると、そのときの学習結果の解は以下の式で示される「超平面」(例えば、 $n=2$ の場合は直線)により入力に対するパーセプトロンの答えが「False」と「True」に分離できる直線となる。

$w_0 + \sum_{i=1}^n x_iw_i = 0$

Boolean関数に対して $x _ {1..n}$ Trueの領域とFalseの領域を分離することができる $w _ {0..n}$ が存在する場合、それは「線形分離可能」であるという。パーセプトロンの出力は上記の等式によって決定されるため、線形分離可能な関数しか学習することができない。例えば、パーセプトロンは2つの入力に対するANDは学習することができるが、XOR関数は学習することができない。何故ならばXORは線形分離可能ではないからである。

後で紹介するように、プログラム中の分岐の動作に関する多くの関数は線形に分離可能である。また、パーセプトロンを時間とともに学習させるため、非線形なものに対しても適用可能であるが、その制度は100%ではない。対照的に、gshareのような2レベルのPHTでは、十分にトレーニング時間を取ればどのようなBoolean関数に対しても学習可能である。

3.5 まとめ

パーセプトロンを利用して、特定の分岐の結果について、グローバル履歴と現在の分岐から相関を学習することができる。これらの相関は重みとして表現される。重みが大きいと相関が強く、グローバル履歴中のとある分岐が、これから予測すべき分岐の予測に対して強い相関があることを示している。

図2はパーセプトロン分岐予測器のブロックダイアグラムを示している。プロセッサは高速SRAM中にN個のパーセプトロンのテーブルを保持している。これは他の分岐予測手法に置け®う2ビットカウンタと同じような立ち位置である。パーセプトロンの数 $N$ はハードウェアの面積、重みの数つまり何個の分岐履歴を記憶しておけるかによって決定される。特殊な回路が $y$ の値を計算し、学習を行う。フェッチステージにおいてプロセッサが分岐命令に遭遇すると、以下のステップが実行される。