分岐予測器最新技術を読み解くメモその1

高性能なプロセッサを作るためには、予測精度の高い分岐予測器が不可欠です。

ほとんどの分岐予測器は、主に以下の情報を使います。 * 分岐命令のあるアドレス(プログラムカウンタの値、PC) * 直近のいくつかの分岐について、分岐が成立だったか、不成立だったかの系列(グローバル履歴、ghist) * 最近の高性能分岐予測器では、「直近のいくつか」というのは1000個とかのオーダーだったりします

分岐予測器は、PCとghistが完全一致するようなパターンを以前に見たことがあれば、その時と同じ方向に分岐するだろう、というように予測をします。

しかし、これを愚直に実装した分岐予測器(実質的にgshareに相当します)は以下のトレードオフがあり、高い精度を出すことは困難です。

  • グローバル履歴を長くとる場合
    • (Good) 長いグローバル履歴パターンに相関のある分岐を当てることができる
    • (Bad) 直前のグローバル履歴のみに相関するようなパターンで、無駄に多くのパターンを学習してしまう
      • 覚えられるパターン数に限界がある条件下では、非常にもったいない
  • グローバル履歴を短くとる場合
    • (Good) 覚えなければいけないパターン数は少ない
    • (Bad) 長いグローバル履歴パターンを見ないと当てられないパターンを当てられない

ここ10年以上、高い精度を出すことができるということになっている分岐予測器(のパラダイム)にTAGEというのがあります。 TAGEは、ghistの完全一致ではなく、部分一致(というか前方一致)で判断を行う分岐予測器です。

TAGEの特徴は以下のような感じです。

ghistを使う長さが異なる予測器をたくさん配置する

単一の予測器ではトレードオフの関係になってしまいますが、複数の予測器を並べることで、どちらのパターンにもうまく対応しようという作戦です。

ghistを使う長さを等比数列で選ぶ

GEHLとも呼ばれる、TAGEよりも昔からある手法です。

ghistを使う長さが4の場合と10の場合では当てられる分岐の種類が変わってきますが、104と110ではそう大きく変わらないでしょう。 この直観から、ghistを使う長さを等比数列で選ぶとよさそうだということになります。

最初のTAGEでは、使用するghistの長さは4, 7, 11, 17, 27, 44, 70(4と70の間を等比分割し、整数に丸めたもの)でした。

予測器をトーナメント式に並べる

覚えているパターンの中で、ghistが一致したの最長一致を探すことと等価です。 最長一致したものを使う方が信頼度が高いと考えられるため、この手法は有効です。

タグ付きの学習を行う

TAGE以前の分岐予測器では、容量を節約するため、Table[hash(PC, ghist)]に記録された結果を読みだす、のような方式でした。 この方法だと本当に以前見たことのあるパターンなのか、それとも単にハッシュが衝突しただけなのか、という区別がつきません。 単にハッシュが衝突しただけの場合、関係ない過去の結果と混同してしまい、分岐予測器の精度が低くなります。

しかし、TAGE以前の分岐予測器は、「このパターンは以前見たことのないパターンである、単にハッシュが衝突しただけである」と分かったところで、その情報を役にたてられない方式ばかりでした。 「以前見たことがない」と分かったところで、何らかの予測をしないといけないためです。

TAGEでは予測器がトーナメント式に並んでいるため、「このパターンは見たことがない、信頼できる予測結果は出せない」とトーナメントで敗退することで、関係ない過去の結果との混同を防ぎます。

最近の改良:バンクインタリーブ

オリジナルのTAGEでは、予測器ごとに一つのテーブルが使われます。この方式では、長いグローバル分岐履歴が不要なプログラムにおいて、長いグローバル分岐履歴で学習する予測器用のテーブルは有効活用されません。あるいは、長いグローバル分岐履歴に相関が強いプログラムに対しては、短いグローバル分岐履歴で学習する予測器用のテーブルが無駄になっています。

これに対し、各予測器が個別のテーブルを使うのではなく、一つの巨大なテーブルを共有して使えば、問題を解決できます。

ただし、各予測器が無秩序にテーブルの要素にアクセスすることを許す場合、そういうハードウェア(多ポートのRAM)は現実的ではありません。

アドレス[0, 128)の範囲に最大一回、アドレス[128, 256)の範囲に最大一回、アドレス[256, 384)の範囲に最大一回、のようにある程度秩序だってアクセスされる場合、そういうハードウェア(バンク分けされたRAM)を作ることは現実的にできます。

よって、「各予測器はテーブルのランダム(だが再現可能な)番地に過去の結果を保存する。ただし、各予測器がアクセスするアドレスの上位数ビットは必ず相異なる」のような制約を満たすハッシュ関数を作る必要があります。

下位ビットはどうでもいいので、上位ビットの制約をどうするかという問題です。 結論としては、要するに、各予測器(1, 2, 3, ...)に対して、重複がなくランダムな値(たとえば、6, 4, 13, ...)をマッピングすればいいことになります。 つまり、PCやghistを使って"シャッフル"すればよいだけです。 ただし、ghistのうち使えるのは、一番短くghistを使う予測器(T1)が使うghistの長さ分だけです。長いghistが異なっても、T1が使う部分が同一であれば同じ部分にマッピングされる必要があります。 そうしないと、T1の学習結果が毎回同じところに保存されなくなってしまいます。

実際には、T1の学習結果を保存するアドレスを生成するためにはT1が使う長さのみghistを使う、T2の学習結果を保存するアドレスを生成するためにはT2が使う長さのみghistを使う、……のようにしても大丈夫ですが、並列に計算するのが困難になります。

T1, T2, ……T10がアクセスするアドレスに関してはT1が使う長さのみghistを使う、T11, T12, ...がアクセスするアドレスに関してはT11が使う長さのみghistを使う、のような二段階に分けた方式だと、それほど並列性を落とさず、性能もほぼ限界まで出せるということでした。