c - C でのパーセプトロン分岐予測子の実装

Question

パーセプトロンによる動的分岐予測に関する論文http://www.cs.utexas.edu/~lin/papers/hpca01.pdfを読んでいました。トレース行に記録されている 1000 個の PC アドレス (ワード アドレス) と 1000 個の分岐の実際の結果のリストが与えられた場合、C でパーセプトロン分岐予測子を実装する方法を考えていました。基本的に、これらのトレースを使用して、さまざまな予測変数の精度を測定したいと考えています。トレース ファイルからの分岐結果は、予測子のトレーニングに使用する必要があります。助言がありますか？

Answer 1

かなり単純だと思います。セクション 3.2 と 3.3 は、あなたが本当に理解しなければならないすべてです。

セクション 3.2 では、出力 percepatron は、過去の履歴に加重係数を掛けた合計であると述べています。

#define SIZE_N 62 //or whatever see section 5.3
float history[n] = {0}; //Put branch history here, -1 not taken, 1 taken.
float weight[n] = {0};  //storage for weights

float percepatron(void )
{
    int i;
    float y=0;
    for (i=0;i<SIZE_N;i++) { y+= weight[i] * history[i];}
    return y;
}

次に、3.3 では、重み付け係数はトレーニングから取得されます。これは、過去の結果の比較でそれぞれをトレーニングするだけです。

void train(float result, float y, float theta) //passed result of last branch (-1 not taken, 1 taken), and perceptron value
{
    int i;
    if ((y<0) != (result<0)) || (abs(y) < theta))
    {
     for (i=0;i<SIZE_N;i++;) {
          weight[i] = weight[i] + result*history[i];
       }
    }
}

したがって、残っているのはシータだけです。

float theta = (1.93 * SIZE_N) + 14;

したがって、使用法は次のとおりです。

y = percepatron();
//make prediction:
if (y < 0) predict_not_taken();
else predict_taken();
//get actual result
result = get_actual_branch_taken_result();//must return -1 not taken, 1 taken
//train for future predictions
train(y,result,theta);

//Then you need to shift everything down....
for (i=1;i<SIZE_N;i++)
{
  history[i] = history[i-1];
  //weight[i] = history[i-1]; //toggle this and see what happens :-)
}
history[0] = 1; //weighting - see section 3.2