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

Question

我正在我的计算机体系结构类中完成一项任务,我们必须在C++中实现分支预测算法(对于Alpha 21264微处理器体系结构).

我只是想了解给定的解决方案,特别是正在发生的事情:

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

特别,

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

任何人都可以向我提供解释吗？谢谢.

Answer 1

我认为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++ )
    {
       ...
    }
}

当内循环执行下一次时,一位计数器将错误预测分支,而2位计数器可以阻止它.

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

天真的方法是使用分支地址作为索引.但它忽略了不同分支之间的相关性.这就是全球分会历史的原因(详情请参阅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是最好的解决方案.