Branch Prediction Championship Simulatorの続きを試す。
パーセプトロン予測器。いわゆるニューラルネットワークに使われるようなパーセプトロンで予測を行う。 一番最初に出てきた論文は以下。基本的に以下の論文をベースにソースコードを見ながら考えていく。
パーセプトロンなので、複数の入力を使って予測(Taken/UnTaken)を行っていく。 パーセプトロンへの入力は、これまでの分岐履歴の結果と、それぞれの履歴列に対する重みを格納している配列となる。
分岐履歴とPCに基づいて引いた重みテーブルをそれぞれ掛け合わせ、最終的に足し合わせる。
- GHRにおいて成立したと記憶しているビット : 重みを加算する
- GHRにおいて不成立と記憶しているビット : 重みを減算する
これによって何が分かるかというと、GHR内のそれぞれの分岐命令の結果が、最終的な予測にどれだけ寄与するかが重みによって指定される。 ある分岐の結果が以降の分岐に強く相関するとその重みは強くなり、全く創刊するとその重みはマイナス方向に強くなる、とする。
この計算結果に基づいて分岐予測を行い、最終的に分岐結果が得られた時点で重みのアップデートを行う。 重みのアップデートについては、分岐予測の結果と実際の結果が異なっていた場合：
- GHRの、分岐結果と同じ方向を予測した重み : 重みを上げる
- GHRの、分岐結果と逆の方向と予測した重み : 重みを下げる
となる。いろんな条件があってややこしいが、
- 分岐結果がTakenの場合 (1)
- GHRの-1のビット(UnTaken) : 最終的にTakenの方向に寄与したいので、重みをマイナス方向にもっていき、GHRとの掛け算でプラスの大きな値になるように
- GHRの1のビット (Taken) : 最終的にTakenの方向に寄与したいので、重みをプラス方向にもっていき、GHRとの掛け算でプラスの大きな値にになるように
- 分岐結果がUnTakenの場合 (-1)
- GHRの-1のビット (UnTaken) : 最終的にUnTakenの方向に寄与したいので、重みをプラス方向にもっていき、GHRとの掛け算で小さな値(マイナス)になるように
- GHRの1のビット (Taken) : 最終的にUnTakenの方向に寄与したいので、重みをマイナス方向にもっていき、GHRとの掛け算で小さな値(マイナス)になるように
という理屈だと思う。これに基づいて、PerceptronのChampionship Kitの実装を読んでいく。
アップデートはこの変だと思う。分岐予測ミスしたときにのみアップデートする、ということか。分岐がヒットしたときに強化する、ということはしないのか？
if((temp <= THETA) || (resolveDir != predDir)) { for(int i=0; i <= LEN_GHR; i++) { if(resolveDir == ghr[i]) { // weights[PC][i] += 1; weights[PC][i] = sat_incr(weights[PC][i]); } else { // weights[PC][i] -= 1; weights[PC][i] = sat_decr(weights[PC][i]); } } }
BUDGET = 4, LEN_GHR = 28, TABLE_SIZE = 141, THETA = 68 MPKBr_1K : 182.0000 MPKBr_10K : 36.2000 MPKBr_100K : 10.6600 MPKBr_1M : 8.3340 MPKBr_10M : 7.9609 MPKBr_30M : 8.0317 TRACE : ../traces/SHORT_MOBILE-24.bt9.trace.gz NUM_INSTRUCTIONS : 1000000000 NUM_BR : 38684342 NUM_UNCOND_BR : 2221649 NUM_CONDITIONAL_BR : 36462693 NUM_MISPREDICTIONS : 311565 MISPRED_PER_1K_INST : 0.3116
ちなみにこれ、当たっても外れても重みを更新するとどうなるんだろう。
// if((temp <= THETA) || (resolveDir != predDir)) if((temp <= THETA))
結果的に悪くなったな。強すぎる相関も良くないってことか？
BUDGET = 4, LEN_GHR = 28, TABLE_SIZE = 141, THETA = 68 MPKBr_1K : 182.0000 MPKBr_10K : 37.6000 MPKBr_100K : 14.9800 MPKBr_1M : 12.3510 MPKBr_10M : 12.0282 MPKBr_30M : 12.0083 TRACE : ../traces/SHORT_MOBILE-24.bt9.trace.gz NUM_INSTRUCTIONS : 1000000000 NUM_BR : 38684342 NUM_UNCOND_BR : 2221649 NUM_CONDITIONAL_BR : 36462693 NUM_MISPREDICTIONS : 464191 MISPRED_PER_1K_INST : 0.4642
