本题链接：

https://hdlbits.01xz.net/wiki/Cs450/gshare

分支预测器生成条件分支指令方向的选择/不选择预测。它位于处理器流水线的前端，负责将指令导向正确的程序执行路径。分支预测器通常与分支目标缓冲区(BTB)一起使用，其中 BTB 预测目标地址，而分支预测器选择的是分支到目标还是继续沿直通路径获取。

在流水线的后期（通常在分支执行或停用时），执行的分支指令的结果将被发送回分支预测器，以训练它通过观察过去的分支行为来更准确地预测未来的分支。当存在错误预测的分支时，也可能存在流水线刷新。

在本练习中，假定分支方向预测器位于右边的图中所示的假设的处理器流水线的提取阶段。本练习只构建由图中的蓝色虚线矩形显示的分支预测器。

分支方向预测是一个组合路径：pc寄存器用于计算已选择/不选择预测，影响next-pc多路复用器确定下一个周期pc的值。

相反，对模式历史表（PHT）和分支历史寄存器的更新将在下一个时钟上升沿生效，正如存储在触发器中的状态所预期的那样。

Gshare 预测变量

分支预测器通常构建为由程序计数器和分支历史记录索引的计数器表。表索引是分支地址和历史记录的哈希表，并尝试为每个分支和历史记录组合提供自己的计数器索引（至少减少冲突次数）。每个计数器索引都包含一个两位饱和计数器，用于执行与过去相同的分支和历史模式时记住分支方向。

这种预测变量样式的一个例子是 gshare 预测变量。在 gshare 算法中，分支地址 （pc） 和历史位“共享”表索引位。基本 gshare 算法通过将 N 个分支地址位和 N 个全局分支历史位一起计算 N 位 PHT 表索引。

然后使用 N 位索引访问两位饱和计数器的 2^N 项表中的一项。此计数器的值提供预测（ 0 或 1 = 未取，2 或 3 = 已取）。

训练以类似的方式索引表。训练 pc 和历史用于计算表索引。然后，该索引处的两位计数器根据分支的实际结果递增或递减。

引用

1. S. McFarling, "Combining Branch Predictors", WRL Technical Note TN-36, Jun. 1993

描述

使用 7 位 pc 和 7 位全局历史构建 gshare 分支预测器，全局历史记录经过哈希处理（使用异或）为 7 位索引。此索引访问包含两位饱和计数器的 128 个计数器索引（类似于  cs450/counter_2bc ）。分支预测器应包含一个 7 位全局分支历史寄存器（类似于 cs450/history_shift ）。

分支预测器有两组接口：一组用于预测，另一组用于训练。预测接口用于处理器的获取阶段，要求分支预测器对所获取的指令进行分支方向预测。一旦这些分支沿着流水线前进并被执行，分支的真实结果就变得已知。使用实际的分支方向结果对分支预测器进行训练。

当一个给定的 pc 分支预测被请求（predict_valid = 1）时，分支预测器用于做出预测的分支历史记录器的预测的分支方向和状态。然后（在下一个上升沿）为预测的分支更新分支历史寄存器。

当要求对分支进行训练 （ train_valid = 1 ）时，分支预测器会被告知正在训练的分支的 pc 和分支历史记录值，实际的分支结果以及分支是否为错误预测（需要流水线刷新）。更新模式历史表 （PHT） 以训练分支预测器以便下次更准确的预测此分支。此外如果正在训练的分支被错误预测，也会在错误预测的分支完成执行后立即将分支历史寄存器复位。

如果在同一周期中发生错误预测和预测（针对不同的、较新的指令）的训练，则两个操作都需要修改分支历史记录寄存器。发生这种情况时，训练优先。因为无论如何都会丢弃被预测的分支。如果同一 PHT 条目的训练和预测同时发生，则预测会在训练之前得到 PHT 状态，因为训练仅在下一个时钟上升沿修改 PHT 。下面的时序图显示了训练时的时序和同时预测 PHT 条目0的时序。第4周期的训练请求改变了第5周期的 PHT 进入状态，但是第4周期的预测请求输出了第4周期的 PHT 状态，而没有考虑第4周期训练请求的影响。

areset 是一个异步复位，它将整个 PHT 清除到 2b'01（弱不选择）。它还会将全局历史记录寄存器清除为 0。

题目

答案

输出波形

异步复位

训练条目（pc = 0xa, history = 0 和 2）

错误预测的历史记录恢复

分支预测器（英语：Branch predictor）是一种数字电路，在分支指令执行结束之前猜测哪一路分支将会被执行，以提高处理器的指令流水线的性能。

条件分支指令通常具有两路后续执行分支。即不采取（not taken）跳转，顺序执行后面紧挨JMP的指令；以及采取（taken）跳转到另一块程序内存去执行那里的指令。

是否条件跳转，只有在该分支指令在指令流水线中通过了执行阶段（execution stage）才能确定下来。

如果没有分支预测器，处理器将会等待分支指令通过了指令流水线的执行阶段，才把下一条指令送入流水线的第一个阶段—取指令阶段（fetch stage）。这种技术叫做流水线停顿（pipeline stalled）或者流水线冒泡（pipeline bubbling）或者分支延迟间隙。这是早期的RISC体系结构处理器采用的应对分支指令的流水线执行的办法。

分支预测器猜测条件表达式两路分支中哪一路最可能发生，然后推测执行这一路的指令，来避免流水线停顿造成的时间浪费。如果后来发现分支预测错误，那么流水线中推测执行的那些中间结果全部放弃，重新获取正确的分支路线上的指令开始执行，这招致了程序执行的延迟。

在分支预测失败时浪费的时间是从取指令到执行完指令（但还没有写回结果）的流水线的级数。现代微处理器趋向采用非常长的流水线，因此分支预测失败可能会损失10-20个时钟周期。越长的流水线就需要越好的分支预测。

一条条件跳转指令第一次遇到，还没有任何信息可以去预测分支。此后保持这条指令是采取还是不采取跳转的历史记录，就可以作为再遇到这条指令时猜测最可能的分支。

饱和计数器（saturating counter）或者称双模态预测器（bimodal predictor）是一种有4个状态的状态机：

• 强不选择（Strongly not taken）

• 弱不选择（Weakly not taken）

• 弱选择（Weakly taken）

• 强选择（Strongly taken）

当一个分支命令被求值，对应的状态机被修改。分支不采纳，则向“强不选择”方向降低状态值；如果分支被采纳，则向“强选择”方向提高状态值。这种方法的优点是，该条件分支指令必须连续选择某条分支两次，才能从强状态翻转，从而改变了预测的分支。

全局分支预测器（global branch predictor）并不为每条条件跳转指令保持专用的历史记录。相反，它保持一份所有条件跳转指令的共享的历史记录。优点是能识别出不同的跳转指令之间的相关性。缺点是历史记录被不相关的不同的条件跳转指令的执行情况稀释了（diluted）；甚至历史记录没有一位是来自同一个分支指令，如果有太多的不同的分支指令。

这种方法只有在历史缓冲区足够长，才能发挥出性能。但是模式历史表的条目数是历史缓冲区位数的指数量级。因此只能是在所有的条件跳转指令间共享这个大的模式历史表。

参考内容：

分支预测器 - 维基百科，自由的百科全书 (wikipedia.org)：

https://zh.wikipedia.org/zh-cn/%E5%88%86%E6%94%AF%E9%A0%90%E6%B8%AC%E5%99%A8

Combining Branch Predictors：

https://www.hpl.hp.com/techreports/Compaq-DEC/WRL-TN-36.pdf