c++ - 分支预测 - 全局共享实现说明

Question

我正在我的计算机体系结构课程中进行一项作业，我们必须在 C++ 中实现分支预测算法（用于 Alpha 21264 微处理器体系结构）。

提供了一个解决方案作为示例。此解决方案是Global Share Predictor的实现。

我只是想了解给定的解决方案，特别是发生了什么：

*predict (branch_info &b) {...}

具体来说，

if (b.br_flags & BR_CONDITIONAL) {...}

谁能给我一个解释？谢谢你。

score 5 · Accepted Answer

我认为 Scott McFarling 的以下论文提供了详细的答案：

让我用你的代码来解释。

unsigned char tab[1<<TABLE_BITS];

是模式历史表。选项卡中的每个条目都保留一个 2 位饱和计数器。条件分支的方向最终由计数器的 MSB 决定：

u.direction_prediction (tab[u.index] >> 1);

我们使用两位或更多位的计数器而不是仅一位的原因是为了使模式不那么敏感以减少误预测。例如，

for( int i = 0; i < m; i++ )
{
    for( int j = 0; j < n; j++ )
    {
       ...
    }
}

下一次执行内循环时，一位计数器会错误预测分支，而两位计数器可以防止它。

接下来是如何在模式历史表中找到正确的模式。

天真的方法是使用分支地址作为索引。但它忽略了不同分支之间的相关性。这就是引入Global Branch History的原因（更多详细信息，请参阅http://www.eecg.utoronto.ca/~moshovos/ACA06/readings/two-level-bpred.pdf）。

在您的代码中，

unsigned int history;

是存储全局分支历史的分支历史寄存器。

然后有些人发现，将全局分支历史记录和分支地址作为索引结合起来可以比仅使用其中一个更准确的预测。原因是全局分支历史和分支地址都会影响分支模式。如果忽略其中之一，不同的分支模式可能会散列到模式历史表的相同位置，从而导致冲突问题。

在提出 Gshare 之前，有一个解决方案叫 Gselect，它使用全局分支历史和分支地址的串联作为模式历史表的索引。

Gshare提供的解决方案是哈希函数

index = branch_addr XOR branch_history

这正是以下代码的含义：

 u.index = (history << (TABLE_BITS - HISTORY_LENGTH)) ^ (b.address & ((1<<TABLE_BITS)-1));

Scott McFarling 的论文提供了一个很好的例子来展示 Gshare 如何比 Gselect 更好地工作：

假设我们使用以下 Gselect 策略来防止偏差：

index = { {branch_addr[7:4]}, {branch_history[3:0]} }

然后 Gselect 将为这两种情况生成 1111_0000 而 Gshare 可以区分不同的模式。

据我所知，Gshare 是迄今为止消除碰撞的最佳解决方案。

1 回答 1