c - 感知器分支预测器在 C 中的实现

Question

我正在阅读有关使用感知器进行动态分支预测的论文http://www.cs.utexas.edu/~lin/papers/hpca01.pdf 。我想知道如何在 C 中实现感知器分支预测器，如果给定 1000 个 PC 地址（字地址）和 1000 个记录在跟踪行中的分支实际结果的列表。本质上，我想使用这些跟踪来衡量各种预测变量的准确性。跟踪文件中的分支结果应用于训练您的预测器。有什么建议么？

Answer 1

我认为它相当简单。3.2 和 3.3 节是您真正需要了解的全部内容。

第 3.2 节说输出感知器是过去历史乘以它们的加权因子的总和：

#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];
       }
    }
}

所以剩下的就是theta，他们告诉你：

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