本题链接：

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

分支预测器通常由程序计数器和分支历史记录索引的计数器表组成。分支历史记录是来自最近分支的“taken”或“not taken”结果的序列。

在硬件中，分支历史寄存器可以由 N 位移位寄存器来实现 。预测每个条件分支方向后，其预测方向将会移位到移位寄存器中。因此移位寄存器会保存最新的 N 个分支结果。

由于分支预测是由推测完成的，因此流水线的刷新会增加额外的复杂性。当发生分支预测错误时，处理器状态需要立即回滚到错误的预测分支之前的状态。这包括回滚全局历史寄存器，其中可能包含预测的分支结果，这些结果由比错误预测分支更新的分支移入，但现在需要舍弃。

我们在这里假设分支预测器之外的硬件会记住用于预测每个分支的分支历史寄存器的状态，并将其保存以供用于以后的分支预测器训练和流水线刷新。当发生错误的分支预测时，此硬件会告知分支预测器的分支已预测错误和应该采取的分支，这些状态与预测错误的分支之前程序中的点相对应。

当然，由于处理器重新复位到错误预测分支后的点，因此流水线刷新后的分支历史寄存器需要附加错误预测分支的实际方向。

描述

构建一个 32 位全局历史移位寄存器，功能包括支持回滚状态以响应由分支预测错误引起的流水线刷新。

当进行分支预测  (predict_valid = 1) 时，从 LSB 端移入 predict_taken 以更新预测分支的分支历史记录。（predict_history[0]是最新的分支的方向)

当发生分支错误预测 （train_mispredicted = 1） 时，在错误预测的分支完成后，将分支历史记录寄存器与历史记录一起加载。这是在错误预测的分支 （train_history） 与分支 （train_taken） 的实际结果相连接之前的历史记录。

如果同时发生预测和错误预测，则优先错误预测，因为流水线刷新也会刷新当前进行预测的分支。

predict_history 是分支历史寄存器的值

areset 是一个异步复位，将历史计数器复位为零

题目

答案

输出波形

异步复位

向上计数，然后向下计数

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