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
分岐命令の実行毎にテーブルがどのように更新されるのか、簡単に見て行こうと思う。