2.3.1 先进分支预测之“感知机分支预测器”

通过前文的描述我们看到，分支预测的本质是模式学习，即通过对历史的分支进行学习，预测未来再次出现的概率，比如一个 for 循环，最简单的预测方式就是猜循环会继续而不会跳出。

感知机分支预测器是一种基于简单感知机（Perceptron）模型的分支预测方法。简单感知机是一种最早期的、最简单的神经网络模型。这种模型的设计灵感来自生物神经网络中的神经元：接收一组输入，对每个输入进行加权求和，然后通过一个激活函数（通常是一个阈值函数）来决定输出。AMD的Zen架构的处理器采用了感知机分支预测器。

1957年，Frank Rosenblatt引入了感知机，感知机原理如图2-6所示。感知机是二分类的线性模型，输入为实例的特征向量，输出为实例的类别（取+1或-1）。感知机对应于输入空间中将实例划分为两类的分离超平面。感知机的目的是求出该超平面，为求得超平面加入了损失函数，利用梯度下降法对损失函数进行最优化。感知机的设计灵感来源于生物神经元的学习能力。感知机是一个单层神经网络，也是机器学习的基本思路，它由一个处理器组成，接受多个带权重和偏移量的输入，生成单个输出。感知机的工作方式是将输入与权重相乘，将所有乘积的加权和输入一个激活函数。

之后有科学家提出了一种基于感知机的分支预测方法，可以作为传统二位分支预测缓冲区的替代方案。他们提出的感知机分支预测器是第一个使用神经网络进行分支预测的动态预测器。预测器利用长分支历史，因为硬件资源可以线性扩展历史长度，从而提高预测方法的准确性。

感知机分支预测器的工作原理如图2-7所示，系统处理器在SRAM中维护一个感知机表格，类似于二位计数器。根据权重数量和硬件预算，表格中的感知机数量被固定。当获取一个分支指令时，通过对分支地址进行压缩映射，在感知机表格中产生一个索引，然后将该索引处的感知机移动到一个权重向量寄存器（在这个实验中使用的是带符号的权重）。通过计算权重和全局历史寄存器的乘积来产生输出。如果输出值为负，则预测分支不被取；如果输出值为正，则预测分支被取。当知道实际结果时，根据实际结果和预测值来通过训练算法更新权重。

在这项研究中，分支行为被分类为线性可分和线性不可分。对于线性可分的分支行为，感知机分支预测器的表现更好。与复杂的神经网络相比，感知机做出的决策更容易理解。另一个选择感知机作为分支预测器的因素是其硬件实现的效率更高。

在感知机分支预测器中，每个分支都有一个对应的感知机。感知机的输入是一组最近的分支历史记录，每条记录表示该分支上一次是取还是不取。每个输入都有一个相应的权重，这些权重是在处理器执行过程中通过机器学习方法不断更新的。

感知机分支预测器的优点是可以学习并正确预测一些复杂的分支模式，这是许多其他类型的分支预测器难以做到的。然而它的缺点是需要更多的硬件资源（用于存储权重）和具有更高的计算复杂性（用于进行加权求和与激活函数计算）。