lab2 Paper Summary
1 Motivation
在现代处理器中，当遇到一个分支指令时，比起暂停几个周期，处理器会尝试选择预测分支跳转的位置以提高处理器的性能。
随着处理器流水线阶段数逐渐增加，不进行分支预测或是分支预测错误的代价越来越大，这迫切地需要我们设计一个好的分支预测器。
基于论文当时对已有预测器的调研发现，较广泛使用的基于饱和计数器表的分支预测器对于分支预测历史的”记忆能力“相对较差。
这启发我们使用神经网络来“学习“分支预测的模式。同时，考虑到时钟周期等问题，分支预测器的实现不能过于复杂。因此，论文采用了单层感知机来进行分支预测
2 Challenges
1、资源限制：由于空间资源有限，我们需要尽可能简单且有效地实现单层感知机的训练与预测过程。而且由于一个感知机所占内存要比“饱和比特”所占内存大，我们存储的感知机数更少，会导致更严重的别名问题。
2、线性可分限制：由于从理论上讲，单层感知机只适用于线性可分问题，对于线性不可分问题，其预测性能会有所下降，对于大部分程序而言，单层感知机是否能够达到一个可接受的性能标准，是有待研究的问题。
3、延迟与训练时间：为了满足处理器流水线的需要，我们需要在单个时钟周期内完成感知机的预测与训练。这需要特殊的电路设计
3 Design
论文提出了一个两级预测结构，用感知机取代传统的饱和计数器。具体设计为：
第一步：与传统的两级分支预测器类似，将跳转指令地址通过Hash后，从对应的表中找到我们需要的感知机。
论文中没有给出明确的Hash方法，我们这里还是默认其采用地址与跳转历史进行异或运算的方法
第二步：用取出的感知机和跳转历史计算预测值y，如果y>0，则预测跳转，反之预测不跳转。
具体计算方法为
其中w为权重值，x为跳转历史。
第三步：得知分支跳转结果后，根据结果与预测值的关系，对感知机的权重进行更新，并写回到感知机表中。
具体更新方法为：
其中t为真实的跳转结果。
通过以上的设计，我们的感知机可以在大部分情况下表现优秀，根据文章中的陈述，感知机预测器整体略优于GSahre和Bimode预测算法，并且在内存资源丰富时表现突出（可以记忆更长的历史跳转记录）。
4 Appendix
此外，为了满足预测与训练能够在一个时钟周期内完成，文章中还提到了一些电路设计
1、由于x的值只可能为1或-1，故我们不需要使用乘法器，只需要在x为1时加上权重，为-1时减去权重即可，同时由于对于预测结果而言，我们只关心符号位，故我们只需要优先计算符号位，其他位置不用着急计算。
2、同时，由于各权重之间没有依赖关系，我们可以并行更新：
3、根据threshold的设计，即 ，可知，每个权重位只需位。
通过以上设计，可以尽可能地减小时间与空间的资源占用。
总的来说，这篇论文抓住了以往的预测算法对于跳转历史的使用不够充分的问题，并抓住这个关键点加以解决，设计出了感知机算法，并取得了不错的表现。
然而正如论文中所提到的，该算法只适用于线性可分问题。对于线性不可分的问题则无计可施，尽管其能够达到一个可以接受的性能表现，但却没有了进一步优化的可能。接下来的工作可能可以聚焦在这个问题进行优化。