报名编号：CICC1740 团队名称：小型三极管
地址预测简介：
在RISC-V指令集架构中，跳转指令分为有条件跳转指令和无条件跳转指令，其中无条件跳转指令又分为直接跳转指令和间接跳转指令。直接跳转指令和分支跳转指令的跳转地址是通过当前地址加上指令中的立即数计算得出的，因此跳转地址是固定的，只需要使用一段存储空间来记录跳转地址即可。当下一次同一位置的跳转指令出现时，就可以将之前存储空间中保存的跳转地址作为下一次的跳转地址。然而，对于间接跳转指令来说，跳转地址需要通过索引通用寄存器进行计算，而通用寄存器中的值通常是不断变化的，因此对间接跳转指令进行预测比较复杂。幸运的是，在一个程序中，大多数的间接跳转指令都是作为程序中函数调用返回的功能使用的，而函数调用指令和函数返回指令通常是成对出现的，因此可以对这两种类型的指令进行地址预测。预测间接跳转指令的地址通常使用两种方法：一种是基于历史记录的方法，记录之前跳转指令的目标地址，然后在下一次遇到相同的跳转指令时，直接使用历史记录中的地址作为预测地址；另一种是基于全局历史记录的方法，记录所有跳转指令的历史记录，并使用这些历史记录来预测跳转地址。除此之外，还可以使用一些机器学习算法来对跳转地址进行预测。这些方法通常结合使用，以提高跳转指令的预测精度。
BTB 地址预测：
由于条件跳转指令和直接跳转指令的跳转地址是固定的，因此我们可以使用一个缓冲区来存储这些指令的跳转地址。当再次执行这些指令时，它们的目标跳转地址就是缓冲区中记录的地址。然而，由于我们无法将所有跳转指令的目标地址都保存在缓冲区中，因此只能使用PC的一部分位作为缓冲区的地址，我们称这个缓冲区为BTB（Branch Target Buffer）。
BTB使用类似于Cache的索引机制，其中PC的一部分位（称为索引Index）用于访问BTB中存储的跳转信息。为了避免PC的Index位索引到BTB的不同位置时发生冲突，BTB还将PC的另一部分位作为tag保存在BTB中。当处理器执行跳转指令时，它会首先访问BTB，比对PC中的tag位和BTB中的tag位是否匹配。如果匹配，则可以直接从BTB中读取跳转指令的目标地址，并将其作为下一个要执行的指令的PC值。如果不匹配，则处理器需要计算跳转指令的目标地址，并将其作为下一个要执行的指令的PC值。在一些处理器核中，BTB还记录了跳转指令的历史跳转信息，当方向预测失败时，可以使用BTB中保存的预测位进行预测。因此，BTB可以提高处理器执行跳转指令的效率，从而提高程序的整体性能。BTB地址预测的示意图如下图所示。

BTB对于跳转目标地址为固定值的指令非常有效，但是BTB的容量不能过大，否则会占用过多的面积和时序资源。如果BTB的表项过小，则可能会出现类似于Cache的冲突情况，也就是BTB的地址覆写问题。当连续的跳转指令的BTB索引位相同时，但Tag位不同的情况下，记录新的跳转指令时会覆盖掉旧的跳转指令对应的Tag。当旧的跳转指令再次出现时，就无法命中BTB并预测目标地址了。这种情况的出现会导致BTB中对应的Tag被不断替换，从而导致地址预测失败，降低分支预测的命中率。因此，在设计BTB时需要权衡容量和性能，以避免出现地址覆写问题。