分岐予測の評価キット Branch Prediction Championship Kit を試す (12. BATAGEの実装を読む)

TAGE分岐予測詳細の続き。BATAGEの論文をざっくり読んでみたので、例によってC++のモデルをチェックする。

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

batageのソースコードは、TAGE-SC-Lのものとまた異なっており、もう一度読み直す必要がある(ただし多少シンプル)。

各コンポーネントについて再度おさらいしよう。

• b / b2

以下のbとb2の2つでbase predictorを構成する。bimodal predictorになっている。LOGBとLOGB2がそれぞれ異なるのは、Hysterisis側のビット数を省略している？

   int b [1<<LOGB];   // bimodal predictions
   int b2 [1<<LOGB2]; // bimodal hystereses

• tagged_entry ** g

TAGEのコンポーネント。2次元配列でtagged_entryを構成する。

tagged_entry ** g; // tagged entries

初期化のコードで、これらのコンポーネントの初期化を行う。bimodal predictorの初期値はWeakly Takenとなっている。

batage::batage()
 {
   g = new tagged_entry * [NUMG];
   for (int i=0; i<NUMG; i++) {
     g[i] = new tagged_entry [1<<LOGG];
   }
   gi = new int [NUMG];
   for (int i=0; i<(1<<LOGB); i++) {
     b[i] = 0; // not-taken prediction
   }
   for (int i=0; i<(1<<LOGB2); i++) {
     b2[i] = (1<<BHYSTBITS)-1; // weak state
   }

予測の際は、タグのマッチしたコンポーネントを取り出し、ベクトルsに格納しておく。

bool
 batage::predict(uint32_t pc, histories & p)
 {
 #ifdef PC_SHIFT
   pc ^= pc >> PC_SHIFT;
 #endif

   hit.clear();
   s.clear();
   for (int i=0; i<NUMG; i++) {
 #ifdef BANK_INTERLEAVING
     bank[i] = p.phybank(i);
 #endif
     gi[i] = p.gindex(pc,i);
     if (getg(i).tag == p.gtag(pc,i)) {
       hit.push_back(i);
       s.push_back(getg(i).dualc);
     }
   }

最後にベクトルsを比較し、もっともconflevel()が低いものを選択するということらしい。conflevelってconfidence levelってこと？これが低い方がいいということ？

bi = pc & ((1<<LOGB)-1);
   bi2 = bi & ((1<<LOGB2)-1);
   s.push_back(dualcounter(b[bi],b2[bi2]));

   bp = 0;
   for (int i=1; i<(int)s.size(); i++) {
     if (s[i].conflevel(meta) < s[bp].conflevel(meta)) {
       bp = i;
     }
   }

   return s[bp].pred();

conflevel()の実装だが、正直良く分からん。

int
 dualcounter::conflevel(int meta)
 {
   if (n[1]==n[0]) return 3;
   bool low = lowconf();
   bool promotemed = (meta>=0) && (sum()==1);
   bool med = ! promotemed && mediumconf();
   return (low<<1) | med;
 }

• TakenとNotTakenの数が一致していれば3
• lowconf()は、自信度がないということか？実装を見ると、TakenとNotTakenの差があまり大きくない、という意味に見える。

bool
 dualcounter::lowconf()
 {
   return (n[1] < (2*n[0]+1)) && (n[0] < (2*n[1]+1));
 }

USE_METAというdefineマクロが有効化されているが、これは論文には登場していないらしい。そんなあ。

 // meta predictor, for a small accuracy boost (not in the BATAGE paper)
 // inspired from the meta predictor in TAGE, but used differently
 #define USE_META

その結果、Taken側とNotTaken側が大きく差がついていない状態だとconflevel()が大きくなり、そうでない場合はconflevel()は小さくなる。

そうすると、先ほどのアルゴリズムの通り、conflevel()の小さい、つまりTakenとNotTakenの差分が大きい方が優先的に選ばれる、という結果になる。

次にupdate()側、当該ヒットしたたぐのコンポーネントのカウンタをアップデートする。Takenならばn[1]側、Not Takenならばn[0]側をアップデートする。

void
 dualcounter::update(bool taken)
 {
   ASSERT((n[0]>=0) && (n[0]<=nmax));
   ASSERT((n[1]>=0) && (n[1]<=nmax));
   int d = (taken)? 1:0;
   if (n[d] < nmax) {
     n[d]++;
   } else if (n[d^1] > 0) {
     n[d^1]--;
   }
 }

CATとかの動作は引き続き調べる。