Branch Prediction Championship Simulatorの続きを試す。
なんとなくPerceptron Predictorについて理解できたので、もう一歩進んでPath-Based Branch Predictionについて資料を読んでみる。 読んでいるのは以下の論文。
この論文で出てくる以下の図が最初から意味不明なのだが、よくよく考えてみると、Weightのテーブルを引いた後一気に加算しておくのは面倒なので、
i回目の分岐予測するために、iからi-LENまでのテーブルにそれぞれの重みを分散して格納しておき、分岐が発生するたびにそれを取り出してあらかじめ加算しておく、というので計算量を減らす目的らしい。なるほど。
逆に言うと分岐結果が判明して学習するときには、複数の異なるWeightテーブルにアクセスしないといけない、ということだよね。 でもまあこれは、各ヒストリを別々のSRAMに持っておいて同時並行的に別々のエントリにアクセスすればたぶん問題ないか。
というわけでこの論文に従って、Branch Prediction SimulatorにPath-Basedを実装してみたのだが、分岐予測ミスが多発してしまいやり直し。 実装がどこかミスっているのだが、こういう時に長いテストはどうやって解析すればいいのか面倒だね。
もうちょっとサンプルプログラムを読んで、ハードウェアがどのようになっているのか見てみる。 以下のような感じで、結果的に分岐命令に使用される重みは過去の分岐命令の重みテーブルからも産出されている。
いろいろ検索していると、Branch Predictor Kitに使えそうなソースコードを見つけた。 自分で書いてみたやつだとどうもうまくいかないので、こっちを使ってみよう。
こっちを改造して実行してみると、良い結果が得られた。どこが違うんだ？色々見てみよう。
BUDGET = 4, LEN_GHR = 28, TABLE_SIZE = 141, THETA = 68 MPKBr_1K : 257.0000 MPKBr_10K : 62.5000 MPKBr_100K : 27.1200 MPKBr_1M : 16.0550 MPKBr_10M : 14.8087 MPKBr_30M : 14.7566 TRACE : ../traces/SHORT_MOBILE-24.bt9.trace.gz NUM_INSTRUCTIONS : 1000000000 NUM_BR : 38684342 NUM_UNCOND_BR : 2221649 NUM_CONDITIONAL_BR : 36462693 NUM_MISPREDICTIONS : 569586 MISPRED_PER_1K_INST : 0.5696
