前回の続き：msyksphinz.hatenablog.com
TAGEの実装(gem5)を読むと、FoldedHistory がテーブル数ぶん存在し、さらに tag 用が2本ある。
1. GHRは1本だが、foldはテーブルごとに必要
GHRは1本のビット列だが、テーブル $T_i$ はそれぞれ異なる履歴長 $L_i$ を参照する。したがって
fold(GHR, L1)とfold(GHR, L2)は別物
であり、テーブルごとに圧縮履歴を持つのは自然である。
2. なぜ毎回 fold を計算しないのか
C++モデルであっても、分岐予測は非常に高頻度で呼ばれる。毎回 GHR の長いビット列を走査して fold を計算するとコストが高い。そこで gem5 は
- 分岐結果が入るたびに、各テーブルの fold 値を増分更新
- 予測時は保存してある fold 値を参照
という構成を取る(スループット重視)。
3. tag 用 fold が2本あるのは何のためか
gem5のタグ生成(gtag())は次の形を取る(メモの通り)。
tag = (pc>>instShiftAmt) ^comp0 ^ (comp1<<1); tag&= (1<<tagWidth)-1;
ここで comp0 = computeTags[0][i].comp、comp1 = computeTags[1][i].comp は、同じGHR窓を
- 幅 $w$ と
- 幅 $w−1$
で折り畳んだ2種類の指紋である。
idx衝突は不可避なので、tagの役割は「同じidxに来た別文脈を弾く」ことになる。しかし長履歴を短い tag 幅に圧縮すると偏りが出やすく、tag衝突(偽ヒット)が増える。そこで、2種類の折り畳みを混ぜて tag を“ハッシュ的”にし、偽ヒットを減らす。
