FPGA開発日記

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

分岐予測の評価キット Branch Prediction Championship Kit を試す (13. BATAGEの詳細)

TAGE分岐予測詳細の続き。BATAGEの論文の細かいところを見て行く。

https://dl.acm.org/doi/10.1145/3226098

ポイント

  • デュアルカウンタと呼ばれる新しいPredictionオートマトン
  • デュアルカウンタと米巣信頼度推定を利用した予測・更新のアルゴリズム
  • 割り当て頻度を減らすためのControlled Allocation Throttling(CAT)と呼ばれる新手法

Cold Counter問題について

ベイズ信頼度推定を利用した予測・更新アルゴリズム

TAGE-SCを使うことによりコールドカウンタの問題の解決策となりうるが、分岐予測器が複雑になる。そこで本論文では、SCを使わずにコールドカウンタ問題を解決する方法を考える。

TAGEのコールドカウンタ問題の根本的な原因は：

  1. TAGEはほぼすべての分岐予測ミスに対してタグ付きエントリを割り当てる
  2. TAGEはアップダウンカウンタの「温度」を正確に推定することができない。

2の問題については、カウンタが温まっているかどうかを正確に予測することができない問題であり、カウンタに対してn0, n1を付与することを提案している。n1がTaken / n0がNotTakenの回数をカウントすることにより、カウンタの温まり具合を正確に推定することができる。これにより、uカウンタも削除することができる。もしエントリの信頼度が低い場合、それを無視して、次にヒットするエントリをチェックすることができるようになる。

分岐予測の信頼度について、1981年のSmithの論文において、アップダウンカウンタが飽和するとき、そのかぬたが提供する分岐予測が正しい可能性があるということを示した。 x\in[-2c, 2c-1]のカウンタにおいて、細粒度な信頼度は、 |2x+1|として表現される。この値が大きいほど、予想はりょり確実である。粗粒度な信頼度は、 |2x+1|とカウンタの値を比較することによって得られる。

ここでn0とn1からカウンタの信頼度を取得する方法を考える。|n1-n2|としてしまうと意味がないので、もう少し詳細に考えてみる。

例えば、以下の2つの状態を考える。

  • predictor A : n1 = 2, n0 = 0 (predict taken)
  • predictor B : n1 = 3, n0 = 6 (predict not-taken)

この情報を見て、どちらの方が信頼度が高いといえるか？差分を取得する方法であれば、予測器Bの方が信頼度が高いと考えられるだろう。

分岐はあるパスにおいて、分岐は固定だが不明な確率qを持っていると仮定することを提案する。一様な事前分布 P0(q) = 1から始まり、なんやかんや計算して、mispredictionの確立 \hat{m}は以下のようになる。

[tex: \hat{m} = \int{0}^{1} qP(q|n_1, n_0) dq = \dfrac{B(n{1} + 2, n{0} + 1)}{B(n{1} + 1, n{0} + 1)}] ただし [tex: B(x, y) = \int{0}^{1}{t^{x-1}(1-t)^{y-1}dt}]

n_1 > n_0であるならば、予測はTakenである。その結果、なんか難しい表が作られた。

結論としては、

  • \hat{m} \lt 1 / 3 → high : 表において赤色
  • \hat{m} = 1 / 3 → medium : 表においてオレンジ

  • \hat{m} > 1 / 3 → low : 表において黒

  • \bar{m} = 0 → high

  • \bar{m} = 1 → medium
  • \bar{m} = 2 → low

この3値は以下の論理で生成可能である。

  • \text{medium} = (n_1 = (2n_0 + 1)) \vee (n_0 = (2n_1 + 1))
  • \text{low} = (n_1 < (2n_0 + 1)) \wedge (n_0 < (2n_1 + 1))

\bar{m} = 2\times\text{low} + \text{medium}

if (taken) { // branch is taken
    if (n1 < nmax) n1++;   // nmaxはSaturateを示す
  else if (n0 > 0) n0––; // Saturateしてたら、n0側をデクリメントする
} else { // branch is not taken
    if (n0 < nmax) n0++;   // nmaxはSaturateを示す
    else if (n1 > 0) n1––; // Saturateしてたら、n1側をデクリメントする
}

Decay(減衰)のメカニズム

BATAGEではconfidence levelを用いて有益なカウンタ情報を残す。

  • a tagged entry giving a high confidence prediction cannot be evicted.

ただし、High Confidenceといってもこれ以上使われないエントリはロックする必要が無い。そういうエントリは「減衰する」という方法がある。エントリの減衰は、

if (n1 > n0) n1––;
if (n0 > n1) n0––;

これは一定頻度で行われるのか？

エントリアップデートのメカニズム

  • L_h : 最長のパス (最大エントリインデックス)
  • L_p : 予測に使用したエントリインデックス
  • L_p : L_p の次に長いヒットしたエントリインデックス

CAT (Controlled Allocation Throttling)

予測に失敗した際に、1つのエントリの身を割り当てる。最適な割り当て確率を見つけることになる。