2.3.2 先进分支预测之“TAGE分支预测器”

TAGE（TAgged GEometric history length predictor）分支预测器是一种具有高预测准确性的分支预测技术，它是由André Seznec和Pierre Michaud在2006年提出的，在“A Case for （Partially）TAgged GEometric history length Branch Prediction”论文中，作者详细描述了TAGE分支预测器的设计和实现。

TAGE分支预测器的基本思想是：结合了不同历史长度的多个预测器（基础预测器），以及一个或多个带标签的预测器（TAGE分支预测器）。这种结构的优势在于，能够根据不同的程序行为和历史信息，选择最适合的预测器来进行预测。这也就意味着，TAGE 分支预测器可以自我调整，以适应不同的程序行为。我们可以将其名称“TAGE”分为“TA”和“GE”来了解它的设计思路。

“TA”代表标签（Tagged），在许多分支预测策略中，索引通常是基于程序计数器或者程序计数器和全局历史记录（Global History）的异或运算结果来获取的。出于对存储效率的考虑，只有一部分信息被用于索引，这可能导致别名现象（Aliasing），也就是多个不同的分支可能映射到同一个预测表条目。为了解决这个问题，TAGE 分支预测器引入了标签的概念。通过将多余的程序计数器信息存储为标签，可以更准确地识别哪些预测是真正的匹配，哪些是别名，从而更准确地选择预测条目。

“GE”代表几何（Geometric），是指TAGE分支预测器使用了几何级数的全局历史长度，如32、64、128、256等。这基于一个普遍的认识：全局历史匹配的长度越长，预测的准确性就越高。因此，TAGE 分支预测器原则上会优先选择最长的匹配来进行预测。然而，这并不适用于所有的情况。有些分支可能比较简单，不需要那么长的历史信息，短一些的历史长度就可以进行准确的预测，这就是TAGE 分支预测器中“useful counter”的作用。如果一个短的历史长度能够提供良好的预测结果，这种情况就会通过“useful counter”反映出来，从而在预测时给予适当的权重。

“useful counter”是一个无符号的计数器，记录的是一个预测条目的有用性，它会根据预测器的历史性能进行增减。如果一个条目在过去的一段时间内对预测结果的准确性做出了重要贡献，那么这个条目的“useful counter”就会增加。当需要为新的预测条目腾出空间时，预测器会选择“useful counter”值最小的条目进行替换，因为这些条目在过去被证明对预测的准确性贡献最小。

TAGE分支预测器如图2-8所示，TAGE分支预测器的主要特性如下。

● 几何历史长度：TAGE分支预测器利用了不同长度的全局分支历史，来获取更广泛和深入的程序行为信息。这种方法使得TAGE分支预测器在面对复杂的程序行为时，能够更好地进行预测。

● 部分标记：即每个预测器条目都带有一个标签，这个标签可以用来检查预测器条目是否与当前的全局历史匹配，如果匹配，则使用该条目进行预测；否则，使用基础预测器进行预测。

● 高预测精度：由于TA G E分支预测器结合了多个预测器的优势，并能够根据不同的程序行为选择使用最适合的预测器，因此它的预测精度通常比其他的分支预测器要高。

TAGE 分支预测器由基础预测器（T0）和一系列的带标签的预测器组件（Ti）组成。基础预测器通常是一个简单的以程序计数器为索引的二位计数器双模表，负责提供默认预测。双模表预测器通常被用于捕捉分支行为的局部模式。每个带标签的预测器组件的索引基于不同的历史长度，这些历史长度形成几何级数，以此来捕捉分支行为的全局模式。每个带标签的预测器组件的条目由一个签名计数器 ctr（用其符号来提供预测）、一个部分标签，以及一个无符号有用计数器 u 组成。当进行预测时，基础预测器和带标签的组件会被同时访问。基础预测器提供一个默认预测，带标签的组件只在标签匹配时提供预测。如果存在匹配的带标签的预测器组件，则使用历史最长的那个预测器组件提供的预测作为总体预测，否则，使用基础预测器的预测作为默认预测。

图2-8 TAGE分支预测器

TAGE 分支预测器还定义了“提供者组件”和“替代预测”的概念。提供者组件是最终提供预测的预测器组件，替代预测则是如果在提供者组件上出现错误则会发生的预测。如果在多个带标签的预测器组件上有标签匹配，则使用历史最长的那个组件（提供者组件）的预测作为最终预测；如果提供者组件出现错误，则使用历史次长的组件（提供替代预测的组件）的预测作为替代预测。

TAGE 分支预测器的预测精度较高，但其设计和实现的复杂度也较高。在实际应用中，可能需要进行一些权衡和优化。