Sniperを使った各種分岐予測器の動作確認 (5. Gshare分岐予測器のモデルを調査)

SniperのGshareモデルを探すと既に存在していた。

github.com

PHTを参照するためのインデックスの作り方は、こんな感じになっている。

GsharePredictor::DualSaturatingPredictor GsharePredictor::getPHTEntry(IntPtr ip) {
   return this->pht[(this->bhr & this->mask) ^ (ip & this->mask)];
}

単純にPCとBHRをXORする実装になっている。なるほど。

PredictionとUpdateはこんな感じ。 update() は bhr < 1 ではなく bhr << 1 ではないかな？

bool GsharePredictor::predict(bool indirect, IntPtr ip, IntPtr target) {
   GsharePredictor::DualSaturatingPredictor predictor = this->getPHTEntry(ip);
   return predictor.predict();
}

void GsharePredictor::update(bool predicted, bool actual, bool indirect, IntPtr ip, IntPtr target) {
   updateCounters(predicted, actual);
   GsharePredictor::DualSaturatingPredictor predictor = this->getPHTEntry(ip);
   predictor.update(actual);
   this->bhr = (this->bhr < 1) | actual;
}

実際に実行してみて、性能を測定してみよう。

とりあえずCoremarkを実行してみよう。どうなるかな：

                                     | Core 0    
  Instructions                       |    3589169
  Cycles                             |    3977144
  IPC                                |       0.90
  Time (ns)                          |    3977144
  Idle time (ns)                     |      31178
  Idle time (%)                      |       0.8%
Branch predictor stats               |           
  num correct                        |     325287
  num incorrect                      |     257698
  misprediction rate                 |     44.20%
  mpki                               |      71.80

めっちゃ性能が落ちてしまった。Branch Prediction Rateが非常に悪い。なんかおかしいなあ。

	Gshare	One-Bit	a53	pentium_m
num correct	325287	506039	527535	569213
num incorrect	257698	76946	55450	13772
misprediction rate	44.20%	13.20%	9.51%	2.36%
MPKI	71.80	21.44	15.45	3.84

各命令におけるヒット率をダンプしてみた。例えば、 0x80001370 は非常にヒット率が悪い。デバッグする。

c791 beqz    a5,8000137c

EIP: 0x80001388 Correct: 59160 Incorrect: 2040 Accuracy: 96.6667%
EIP: 0x80001a40 Correct: 25920 Incorrect: 3240 Accuracy: 88.8889%
EIP: 0x800019b6 Correct: 25920 Incorrect: 3240 Accuracy: 88.8889%
EIP: 0x80001378 Correct: 28870 Incorrect: 80 Accuracy: 99.7237%
EIP: 0x80001370 Correct: 940 Incorrect: 27930 Accuracy: 3.25598%
EIP: 0x800014d6 Correct: 27780 Incorrect: 130 Accuracy: 99.5342%
EIP: 0x800014cc Correct: 890 Incorrect: 26890 Accuracy: 3.20374%
EIP: 0x80001fb6 Correct: 0 Incorrect: 15840 Accuracy: 0%
EIP: 0x80001fbe Correct: 1760 Incorrect: 14080 Accuracy: 11.1111%
EIP: 0x80001fca Correct: 12880 Incorrect: 1920 Accuracy: 87.027%
EIP: 0x80001f76 Correct: 2720 Incorrect: 10400 Accuracy: 20.7317%

デバッグすると、やっぱりGshareのC++実装モデルのミスみたいだ。修正するとちゃんと良い精度を出せるようになった。

EIP: 0x80001388 Correct: 58807 Incorrect: 2393 Accuracy: 96.0899%
EIP: 0x80001a40 Correct: 27627 Incorrect: 1533 Accuracy: 94.7428%
EIP: 0x800019b6 Correct: 27916 Incorrect: 1244 Accuracy: 95.7339%
EIP: 0x80001378 Correct: 28749 Incorrect: 201 Accuracy: 99.3057%
EIP: 0x80001370 Correct: 27771 Incorrect: 1099 Accuracy: 96.1933%
EIP: 0x800014d6 Correct: 27594 Incorrect: 316 Accuracy: 98.8678%
EIP: 0x800014cc Correct: 26677 Incorrect: 1103 Accuracy: 96.0295%
EIP: 0x80001fb6 Correct: 15420 Incorrect: 420 Accuracy: 97.3485%
EIP: 0x80001fbe Correct: 13216 Incorrect: 2624 Accuracy: 83.4343%
EIP: 0x80001fca Correct: 11700 Incorrect: 3100 Accuracy: 79.0541%
EIP: 0x80001f76 Correct: 10714 Incorrect: 2406 Accuracy: 81.6616%
EIP: 0x80001f66 Correct: 12896 Incorrect: 144 Accuracy: 98.8957%

                                     | Core 0    
  Instructions                       |    3589139
  Cycles                             |    2202044
  IPC                                |       1.63
  Time (ns)                          |    2202044
  Idle time (ns)                     |      31154
  Idle time (%)                      |       1.4%
Branch predictor stats               |           
  num correct                        |     537369
  num incorrect                      |      45616
  misprediction rate                 |      7.82%
  mpki                               |      12.71

	Gshare	One-Bit	a53	pentium_m
num correct	537369	506039	527535	569213
num incorrect	45616	76946	55450	13772
misprediction rate	7.82%	13.20%	9.51%	2.36%
MPKI	12.71	21.44	15.45	3.84

ただし、Pentium Mモデルの方がまだ性能がいいなあ。