プロセッサアーキテクチャについて再度復習その4。分岐予測の続き。
読んでいるのは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
4.1 ループの抜け出しを予測する
Sheerwoodら[73]によれば、ローカルヒストリを用いる分岐予測器では、ローカルヒストリのサイズがの場合に、
よりも大きなループを抜け出すタイミングを予測するのは不可能である。
よりも大きなグローバルヒストリを使用する場合か、ループを抜け出す前にはっきりとした分岐のシーケンスが登場する場合にのみ分岐予測を行うことが可能である。このような状態は、ループ終了バッファ(Loop Exit Buffer : LEB)ベースの分岐予測器を用いてループの終了を予測する方式が提案されている。図10(a)はループの分岐の例を示している。LEBはメインの分岐予測器により予測が失敗した逆方向の分岐をループの分岐として検出し、図10(b)に示すようにLEBに挿入する。全体的な分岐予測器の設計として、メインの分岐予測器は予測を提供し、LEBベースの分岐予測器が高い精度を達成することができる場合にのみ、その予測がLEBにより上書きされる。
LEBでは、TripCountフィールドでループ分岐が最後に不成立だった時から何回成立しているかを示している。Confidenceビットは同じループのTripCountのループが2回以上連続で登場したことを示している。LEBにヒットするすべての分岐では、もしIterCountがTripCountと一致しない場合、IterCountが連続してインクリメントさせる。つまり、IterCountは分岐が連続で成立した回数を記録している。IterCountがTripCountと同じ値になれば、Confidenceビットが1に設定され、ループの終了が予測される。分岐が解決されると、分岐不成立のTripCountとConfidenceビットがアップデートされる。図10(b)には示していないが、分岐予測の失敗から復帰するための余分なカウンタも搭載されている。ループ予測器は、ウォームアップが終了すると最大で100%まで分岐を予測することができる。しかし、ループカウントが頻繁に変わる場合、このような方式では上手く動作しない。
Sendagら[46]らの提案は、これまでの分岐予測器に追加して補完的な分岐予測器 (complementary BP: CBP)を追加するものである。CBPは主に分岐予測に失敗した分岐に着目し、一方でこれまでの分岐予測器は予測可能な分岐に対して投機を行う。彼らは、「分岐予測失敗予測器(branch misprediction predictor : BMP)」というものを使用し、任意のインデックスに対して分岐予測に失敗した分岐間にコミットされた分岐の数を使用する。この情報を使って次に分岐予測に失敗するタイミングを計測する。この情報を使用して、分岐予測に失敗する分岐に対して予測を変更し、正しい方向に分岐を実行する。BMPにより除去される分岐予測の失敗は以下の通りである。
- ループの回数がBPよりも長く、ループの回数が変化する分岐
break命令などによるループから早期に抜け出す状態
BMPはどのような分岐予測引退しても動作する。彼らの技術は全体的な分岐の精度を向上させ、電力を削減できる。
Laiら[92]の提案は、複数の予測訂正器を使用してメインの分岐予測器が予測に失敗した分岐を正すためのデザインである。それぞれの予測訂正器は、異なるパタンに着目する。したがって、タグにより記憶されている分岐のみを正しく訂正することができる。それぞれの予測訂正器では、必要ならば最も自信のない予測は置き換えられる。彼らは部分アップデートポリシーのgskew BP[86]を使用し、全ての予測訂正器はその自身の度合いを記録し、予測の訂正はその自身の値がスレッショルドを超えた場合にのみ訂正されるようになっている。図11に示すように、彼らは3つの予測訂正器実装した：
- ループ終了の分岐を検出するためのインターバル予測訂正器。固定のインターバルでメインの分岐予測器が予測に失敗するという仮定のもと、その予測を訂正するという考え方である。彼らは2つのインターバル値を使用して、早期のループ終了のパタンにも対応している。メインの予測器が予測が正しいかそうでないかによって、予測訂正器の自信度の値は変動する。もしメインの分岐予測器が予測に失敗し、現在のカウンタが2つのインターバル値と一致しない場合、カウンタのインターバル値を変更し、自信度を下げる。また、固定値の自信度が高い場合のインターバル値は1づつ下げられる。それぞれのインターバル予測修正器と、SendagらのBMP[46]は、分岐予測に失敗したときに発動し、次の予測の失敗を避けるためのものであると言う事に注意すること。
- ローカルヒストリとバイモーダルのパタンを記録するためのバイモーダル予測訂正器。
- 2レベルのパタンを記録する2レベルの予測訂正器[78]。他の予測訂正器と同様に「逆転・アップデート」のスキームを持っている。グローバル履歴を使用するため、高い精度を実現し自信度のスレッショルドは他の予測訂正器よりも低い。
精度が低くなるという面では、全体的な分岐予測器のデザインとしては高い予測精度を実現する。このデザインの限界としては、メインの分岐予測器と予測訂正器が同時に動き、半分以上が同じ予測を出力したならば、この構造自体が冗長でありエネルギーを無駄に消費してしまっていることである。
4.2 多重ループをどのように予測するか
ワームホールプレディクタ
Albericio[61]らの提案。ネストされたループを分岐予測するのは難しい。どちらかといえば、ネストされた内部のループを分岐予測するのには、内部のループの結果よりも外部のループの結果を使用した方が精度が上がるという研究がある。
数学的には、2重ループ内の分岐の結果Outcome[i][j]は、Outcome[i-1][j+D]に相関するという研究結果がある。ここでDは0,-1,+1などの比較的小さな値であり、分岐の結果は、1つ前(i-1)外部ループの、近くのインデックス(j+D)に相関しているということである。
図12のループを考えると、arr1, arr2, arr3, arr4の値がループ内で不変であるとすると、Branch1の結果Outcome[i][j]はOutcome[i-1][j+1]と同一であり、Branch2の結果Outcome[i][j]はOutcome[i-1][j]に弱相関している。Branch3の分岐予測結果Outcome[i][j]はBranch4の分岐予測結果Outcome[i][j]と一致している。
for ( i = 0; i < iMax; i++ ) for ( j = 0; j < jMax; j++) { if ( arr1[i+j] > 0 ) {...} // Branch1 if ( arr2[i][j]-arr2[i-1][j] > 0) {...} // Branch2 if ( arr3[j] > 0 ) // Branch3 if ( arr4[j] > 0 ) {...} // Branch4
これらの分岐予測の情報を1次元の配列に保存してしまった場合、予測することは難しいが、多次元のマトリックスに保存すると、強い相関を観察することができる。図13(b)は相関の情報を2次元の行列に保存した結果である。
彼らの提案では、多次元の分岐結果保存用の配列に保存して、パタンを見つけだすという分岐予測器である。サイドプレディクタ―としてISL-TAGE分岐予測器を使用した。これにより、全体のループカウント数から内部ループの分岐を特定することができるようになる。
それぞれのイタレーションでほぼ同一の動きをする分岐では、最初のイタレーションの結果を保存しておき、これを再利用することで分岐予測の精度を向上させることができる。図13(a)この時のサンプルプログラムで、Branch1はjの値にのみ依存しており、つまりjが同一である場合は分岐結果は同一であるため、前のイタレーションの結果が分かっていれば分岐予測は容易に実現できる。
//Z: vector of objects, p: a point while(true) // Loop1 for(j=0; j<nObjects; j++) // Loop2 if(dist(Z[j],p)< theta) // Branch 1 { /* do something */ }
例えばほかの分岐予測では、対角線上のパタンを見つけることもできる。図14(a)では、分岐の結果はiとjに依存している。したがって分岐の結果は対角線上のパタンとして現れる。このような分岐では、最初の分岐の結果を保存しておく。
// A: a matrix, B: right hand side // X & X0: current & partial solution for ( i = 0; i < N; i++ ) { // Loop3 X0[i] = B[i]; for ( j = 0; j < N; j++ ) // Loop4 if ( j != i ) // Branch 2 X0[i]=X0[i]-A[i + j*n]*X[j]; X0[i] = X0[i] /A[i + i*n]; }
Branch2の結果は以下のようになり、このパタンを解析すれば次のイタレーションでの分岐予測ができるようになる。
彼らの提案した分岐予測は、ISL-TAGEに対して副次的に分岐予測を行い、精度が高ければISL-TAGEの予測に対してオーバライドを行う。サイドプレディクタとして使用することで、分岐予測の精度を大幅に上げることができる。
Seznecら[16]の提案は、ネストされたループの分岐の相関を"最内部イタレーション (Inner-most loop iteration : IMLI)"カウンタベースの分岐予測として実現する。IMLIカウンタはループの繰り返しの回数をカウントしており、負の方向へ分岐する分岐命令(ループ終了条件の分岐)が何回成功したかをカウントしている。
この情報を使用するための2つのコンポーネントを提案している。
- 予測が難しい分岐命令に関しては、内部のイタレーションがカウントされる。つまり、
Outcome[i][j] == Outcome[i-1][j]である。このような「同じイタレーションの相関」については、1番目のコンポーネントはIMLIカウンタとPCによりインデックスされるテーブルを用いる。ワームホールプレディクタは通常のループにおいて固定されたイタレーションのみカウントするが内部ループのイタレーション毎に実行される相関のみを追跡するが、この分岐予測器にはその制限はない。 - ワームホールプレディクタは対角線パタンの予測をすることができるが、これに対処するためにそれらの2番目のコンポーネントは、
Outcome[i][j]を予測しながらOutcome[i-1][j]とOutcome[i-1][j-1]の両方が可能になるようにテーブルを使用する。彼らのIMLIベースのBPコンポーネントは、GHベースのBPと一緒に使用することができ、それらを使用することで、ローカルヒストリーを使用することによるさらなる利点は小さくなる。さらに、それらの提案された分岐予測器の推測状態は容易に管理可能であり、それらの分岐予測器を任意のTAGEまたはニューラルベースの分岐予測器を有するサイドプレディクタとして使用することは高い精度を提供する。
4.3 繰り返し回数の多い分岐を予測する
Kampeらの提案 : プログラムによっては、履歴ビットよりも長い期間でループが発生し、予測を行うためのすべての分岐実行パタンを記録することができない。すべての分岐の履歴を取るためには、ビットの履歴が必要となる。これほどの分岐履歴ビットは用意できないので、履歴を時間領域から周波数領域に変換することで、履歴レジスタのサイズを削減することができる。例えば、
ビットの履歴を表現するために必要なビットは52ビットまで削減される。これに基づいて、離散フーリエ変換(DFT)ベースのサイドプレディクターを提案する。DFTの待ち時間とオーバヘッドが生じるため、この分岐予測器はメインの分岐予測の結果が99.99%未満の場合に適用される。
分岐結果のTaken/NotTakenをそれぞれ1/0として、DFTを使用して分岐履歴を周波数領域に変換する(図15(a), 図15(b))。最大ピークの周波数成分だけを記録し、残りの成分は図15(c)に示すように取り除かれる。そして、すべての周波数成分 を加算し、その合計がしきい値よりも高い場合(図15(d))に、時間
で分岐が発生すると予測される(図15(e))。この分岐予測器の欠点は、周波数成分を使用するために、Taken/NotTakenの確率が50%-50%の場合には精度が高くない。このため、ハイブリッド分岐予測器のコンポーネントとして使用すると、予測ミス率を大幅に削減することができる。
周波数領域に履歴を保存する方式と、幾何学的履歴長テーブル(TAGE)の両方を使用することで、大きな周期を持つ分岐の予測を向上させることができる。周波数領域に履歴を保存する方式は長い履歴を必要とする分岐に焦点を当てているのに対して、TAGEの方式は短期及び中長期の履歴を必要とする分岐に焦点を合わせている。
