TAGE分岐予測詳細の続き。BATAGEの論文の細かいところを見て行く。
https://dl.acm.org/doi/10.1145/3226098
CAT(Controlled Allocation Throttling)について。
ベイズ推定による自信度の見積もりはcold-counter問題を緩和させることができるが、根本的な問題を解決しない。根本的な問題とは、すべての分岐予測を起こしたタグ付きエントリに対する割り当てである。
予測の難しい分岐では、分岐の精度は割り当ての確率が1よりも小さいときに発生し、これをAllocation Throttlingと呼んでいる。これはTAGEおよびBATAGEにおいて有効である。この問題はAllocation Throttlingによりいくつかのトレースにおいて予測精度を減少させるが、実際には平均的に予測精度を向上させる。
つまり、割り当てられるかどうかは確率的であり、それをCATという1つの変数により管理する、ということになる。
Not High Confidenceと呼ばれる中・低信頼度のエントリの量と、MHCと呼ばれるModerately High Confidenceと呼ばれる中程度に高い信頼度状態のエントリを比較する。
- MHC状態 :
MHC状態は一般に過渡的な状態である。ランダムな分岐の振る舞いによる統計的揺らぎの他に、割り当てと減衰がMHCエントリーの存在の2大原因である。
- NHCエントリがMHCエントリの方が大幅に多い場合、割り当てが容易であるが、割り当てられたエントリが中信頼度または低信頼度の状態にとどまるため、積極的になりすぎる可能性がある。
- MHCエントリがNHCエントリよりも多い場合、割り当てが困難であり、割り当てられたエントリはすぐに高信頼度状態に進化するため、割り当てはより積極的に行うことができる。
CATでは、NHCとMHCの割合F_nとF_mを監視する。しかし、 の比率を知りたいだけなので、以下のようにして推定する。
割り当て施行における平均スキップ・エントリ数は であり、MHCである高信頼性エントリの割合は である。したがって、スキップされたMHCエントリの平均値である。
MHCの平均エントリスキップ数が閾値CATRを下回る場合、割り当て確率を減少させる。この確率は1/MINAPを下回ることはできない。
スキップされたMHCエントリの平均値がCATRよりも大きな場合、割り当て確率を増加させる。
とここまで読んでみてもその特性がちゃんと理解できない。ソースコードをチェックしてみたほうがいい気がする。
if (分岐予測ミスが発生) { r = random in [0, MINAP - 1]; if (r >= ((cat * MINAP) / (CATMAX + 1))) { mhc = 0; s = random in [1, SKIPMAX]; for (i = m+s; i <= G; i++) { if (m[i] < 1/3) { // decay with probability PDEC if (m[i] > 0.17) mhc++; } else { overwrite tag; initialize dual-counter; cat = cat + 3 - 4*mhc; cat = min(CATMAX, max(0, cat)); break; } } } }