Branch Prediction Championship Simulatorの続きを試す。
Hashed Perceptronという分岐予測器について勉強する。論文は以下を参照している。
とりあえず細かいことは無視してソースコードを読んでみるのがいい気がする。そのあとで論文を読んでみよう。
概要としては、TAGEと似たような複数長の分岐ヒストリを使うようなものに思える。
複数長のヒストリを持っているのだが、どこまでの長さのヒストリを使ってハッシュ値を生成するか、 というのを別々に切り替えて生成しているように見える。
#define NTABLES 16
// geometric global history lengths
int history_lengths[NTABLES] = {0, 3, 4, 6, 8, 10, 14, 19, 26, 36, 49, 67, 91, 125, 170, MAXHIST};
// 12-bit indices for the tables
#define LOG_TABLE_SIZE 12
#define TABLE_SIZE (1 << LOG_TABLE_SIZE)
// this many 12-bit words will be kept in the global history
#define NGHIST_WORDS (MAXHIST / LOG_TABLE_SIZE + 1)
// tables of 8-bit weights
int tables[NUM_CPUS][NTABLES][TABLE_SIZE];
// words that store the global history
unsigned int ghist_words[NUM_CPUS][NGHIST_WORDS];
この例だと重みテーブルは16個、それぞれ4096エントリを持っている。
そしてそれぞれの16個のテーブルのどこにアクセスするのかを決めるのだが、230ビット近くあるGHRを細かく区切りながらハッシュ関数を計算し、 PCだけで計算するか、近場のGHRの相関を使用するか、どんどん遠くの相関を使用するか、というのを決めている。
そして16個のテーブルで使用するGHRを等比数列的に配置することで、等差数列的に配置するよりも効率的にテーブルを探索できるようにしている。
bool PREDICTOR::GetPrediction(uint64_t pc)
{
// initialize perceptron sum
int cpu = 0;
yout[cpu] = 0;
// for each table...
for (int i = 0; i < NTABLES; i++) {
// n is the history length for this table
int n = history_lengths[i];
// hash global history bits 0..n-1 into x by XORing the words from the
// ghist_words array
unsigned int x = 0;
// most of the words are 12 bits long
int most_words = n / LOG_TABLE_SIZE;
// the last word is fewer than 12 bits
int last_word = n % LOG_TABLE_SIZE;
// XOR up to the next-to-the-last word
int j;
for (j = 0; j < most_words; j++)
x ^= ghist_words[cpu][j];
// XOR in the last word
x ^= ghist_words[cpu][j] & ((1 << last_word) - 1);
// XOR in the PC to spread accesses around (like gshare)
x ^= pc;
// stay within the table size
x &= TABLE_SIZE - 1;
// remember this index for update
indices[cpu][i] = x;
// add the selected weight to the perceptron sum
yout[cpu] += tables[cpu][i][x];
}
return yout[cpu] >= 1;
}
MPKBr_1K : 133.0000 MPKBr_10K : 23.0000 MPKBr_100K : 3.8600 MPKBr_1M : 1.5290 MPKBr_10M : 1.1278 MPKBr_30M : 1.0278 TRACE : ../traces/SHORT_MOBILE-24.bt9.trace.gz NUM_INSTRUCTIONS : 1000000000 NUM_BR : 38684342 NUM_UNCOND_BR : 2221649 NUM_CONDITIONAL_BR : 36462693 NUM_MISPREDICTIONS : 39017 MISPRED_PER_1K_INST : 0.0390
分岐命令の実行毎にテーブルがどのように更新されるのか、簡単に見て行こうと思う。
