本题链接：

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

分支预测器通常由程序计数器和分支历史索引的计数器表组成。表中的每个条目通常使用两位状态，因为一位状态（只记住最后一个结果）没有足够的滞后并且太容易翻转状态。

这个效果不错的两位状态机是一个饱和计数器，它最多可以向上计数到 3（2'b11）或向下计数到 0（2'b00），但不会环回。  “taken”结果会使计数器增加，而 “not-taken” 结果会使计数器减少。 当计数为 2 或 3（2'b1x）时，将采用预测分支。 当强偏置分支偶尔采用不同的方向时，添加一些滞后可以防止预测的翻转。在翻转预测之前需要在相反方向上增加两个增量。

参考

1.  R. Nair, "Optimal 2-bit branch predictors", IEEE Trans. Computers, vol. 44 no. 5, May, 1995

描述

建立一个两位饱和计数器。

当 train_valid = 1 并且 train_taken = 1 时，计数器递增（最大为 3）。当 train_valid = 1 和 train_taken = 0 时，计数器递减（最小为 0）。当不训练时（train_valid = 0），计数器保持其值不变。

areset 是一个异步复位，它将计数器复位为弱不选择 (2'b01)。 输出 state[1:0] 是两位计数器的值。

题目

答案

输出波形

异步复位

向上计数，然后向下计数

分支预测器（英语：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）

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

参考内容：

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

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

Optimal 2-bit branch predictors | IEEE Journals & Magazine | IEEE Xplore：

https://ieeexplore.ieee.org/document/381956