【读书报告】从TAGE看分支预测器设计

注：本文是高等计算机体系结构课程的作业，因为觉得作业不能白写，而且读书报告似乎被我写成了科普向的文章，所以打算把这些作业发在 blog 上 \_(:з」∠)_

自流水线的概念被提出起，处理器的性能就进入了一个飞速提升的时代。而随着 RISC、超标量等技术的诞生和发展，指令级并行性的开发越来越被人所重视，指令级并行度本身也在技术的更迭中不断上升。为了提升处理器的性能，进一步挖掘 ILP，人们选择让处理器尽可能同时分析和调度更多的指令。但由于控制转移指令的存在，尤其是条件分支，处理器不得不采用推测执行的方式来跨越基本块的边界，将流水线填得更满——由此，就诞生了分支预测技术。

“分支预测” 技术正如其名，是一种 “预测” 未来的技术。但实际上，它可以做得很简单，例如对所有分支都预测不跳转；也可以做得很复杂，例如结合过往的分支跳转情况，进行各类预测。在本科期间初次了解分支预测技术时，我曾痴迷于此——一度惊讶于简单的计数器居然也可以预知未来，而复杂的多级结构居然可以将预测正确率推上一个常人无法想象的顶峰。

借读书报告的机会，我终于能从历史的角度，学习和认识分支预测器的发展过程。这篇读书报告虽然是针对 TAGE 分支预测器的论文撰写的，但实际上我将课程中提到的所有关于分支预测的文献都大略的看了一遍。本文将结合这些文献，着重探讨 TAGE 分支预测器的技术要点，兼以浅谈分支预测器的普适设计思想。

什么是好的分支预测器

早在 1981 年，Smith 就曾写过一篇关于分支预测策略研究的文章。在这篇文章中，他对比了当时已经存在的多种分支预测技术，并在此基础上提出了一些新的思路。此外，他结合多个测试程序的 trace 数据，给出了这些分支预测策略的准确度分析。在这篇文章中，我们已经可以看到使用 n 位饱和计数器阵列来进行分支预测的先例了，这种方法被后人称作双模（bimodal）分支预测。而在文章发表的时代，双模预测器的性能是最优秀的。

时间来到了上世纪 90 年代，Yeh 和 Patt 提出了一种性能更优的分支预测策略，他们称其为两级自适应分支预测（two-level adaptive training branch prediction）。这种策略将分支历史和计数器阵列合二为一，实现了更为精准的分支预测。两级自适应预测是一种极为经典且巧妙的预测方法，该策略及其衍生策略曾一度被用在了诸如 Intel P6 等的微结构设计中。而自这篇文章之后，分支预测器的分类又多了一个维度：分支历史，由此划分出了全局分支预测技术和局部分支预测技术，分支预测器的性能也被提升到了一个新的高度。

1993 年，McFarling 发表了一篇文章，首次提出了融合预测器（combined predictor）的思想。在文章中，McFarling 首先使用 SPEC89 中的一些程序测试并对比了当时存在的诸多分支预测策略的性能，包括双模预测、局部预测、全局预测、gselect 和 gshare。之后，他提出了一种将两类分支预测器结合的方法。实验数据表明，结合后的分支预测器性能要更加优异。

实际上，McFarling 的文章告诉了我们两个事实，其一：当不采用融合预测的方式时，即在单个的分支预测器中，表现效果最好的，无论是局部还是全局预测，其核心原理都是尽可能将分支历史和分支指令的地支相结合。这一点并不难理解，因为从常理上讲，分支指令未来的结果往往和过去的执行情况有关，而不同分支指令的结果又通常不同，前者可用分支历史描述，后者则使用指令地址区分。所以，分支预测的效果，通常会和这两个两个因素呈现较强的相关性。

其二：不同形式的分支预测器，往往是为了预测处在不同情景下的分支而设计的。当每一个分支都在绝大部分情况下偏向某个特定的方向时，双模预测器效果最好；当分支只和自己相关，且具备简单而重复的执行模式的时候，局部预测器的效果最好；而当分支的执行情况不仅和自己相关，还受到其他分支的执行情况的强烈影响时，全局预测器的效果最好。这就是为什么文章中采用了两种分支预测器结合的方法，因为实际的分支往往涵盖了上述各类情况，不存在一种“一招鲜，吃遍天”的分支预测策略。

那既然如此，我们为什么不直接将分支历史和分支地址拼起来，得到一个足以精确描述分支情况的序列，然后再用这个序列寻址计数器阵列来实现分支预测呢？因为显然，这样的话我们得到的序列一定很长，从而导致这个计数器阵列需要占用巨大的面积。如果使用 SRAM 实现的话，阵列本身将比主存还要大。即便根据之前的推测，这种方法的效果一定很好，而且分支历史越长效果越好（当然，边际效益递减在此处依然适用）。

所以，分支预测策略总会受到实际硬件实现的限制。考虑到成本、面积、功耗和时序，我们很难将理想情况下的分支预测器迁移到现实的硬件实现中去。从这一点来看，分支预测器的实现实际上是理想和现实的制衡，我们必须根据实际情况做出权衡，舍弃一部分精度，或者牺牲一部分面积。好的分支预测策略往往做了更好的权衡，使得其适用范围更广，准确率更高，而且硬件实现还不复杂。但要做到这件事情，实际上是相当困难的。如果我们按时间顺序回顾分支预测器的发展，我们就会发现，前人所做的一系列优秀的工作，无疑都在当时的硬件水平下，做到了理想和现实的完美权衡。

此时再把目光投向 1993 年，我们便可知 McFarling 的文章做了多么难能可贵的探索，尤其是提出融合分支预测的思想这一点。后期也有很多处理器处理器都使用了类似的思想，例如 Alpha 21264 中的竞争分支预测器。而这种思想，深深影响着之后的分支预测器设计，直到 TAGE 诞生的那个年代——融合分支预测的思想几乎在TAGE分支预测器中发挥到了极致。

GPPM 分支预测器

TAGE 分支预测器是一种性能极为优秀的现代的分支预测器。有传言说，英特尔曾一度在自己的处理器中采用了基于 TAGE 的分支预测器。而 TAGE 分支预测器本身，脱胎于 GPPM 分支预测器，其在结构上与后者有诸多相似之处。所以，要想理解 TAGE 的设计思想，我们就必须先理解 GPPM 分支预测器的结构。

GPPM 分支预测器其实是一个简称，它的全名叫做 global-history PPM-like tag-based branch predictor，同样由 TAGE 预测器的作者在早些年前提出。GPPM 的结构如图所示，它由五个并列的分支预测器组成。最左侧是一个实现简单的双模预测器，由 4096 个三位计数器和 m 位（meta-predictor）组成；而右侧是四个类似 Gshare 结构的全局预测器，由全局历史寄存器和 1024 项的 SRAM 组成，SRAM 中的每项包括一个三位饱和计数器、一个八位的 tag 和一个 u 位（useful）。

当需要执行分支预测时，五个分支预测器会同时工作：双模预测器直接使用 PC 寻址计数器阵列，给出预测结果；四个不同的全局预测器使用不同的 hash 策略，将 PC 和不同长度的分支历史进行 hash，得到 10 位的地址和 8 位的 tag。前者用来来寻址 SRAM，后者用来判断是否命中，如命中，则 SRAM 内计数器产生的分支预测结果有效。GPPM 会优先采用使用较长分支历史的全局预测器的预测结果，如果四个全局预测器全部未命中，则使用双模预测器的结果兜底。

当较低一级的分支预测器预测失败时，GPPM 会尝试在上级的分支预测器中分配新的条目，来试图学习这个新的分支的情况。预测器会尝试占用未设置 u 位的条目，并且使用双模预测器中对应项的m位来初始化该条目中的饱和计数器。关于 u 位、m 位的判断和更新规则，读者可自行参考原论文，此处不再赘述。

GPPM 的结构看似很复杂，实际上蕴含着很简单的道理。前文已经陈述过分支历史和分支地址之于分支预测的重要性，而且我们应该尽可能综合考量不同分支历史下的分支预测情况，以便于对不同类型的分支做出更准确的预测。GPPM 基于多分支预测器、不同历史长度的设计正是为了解决这样的问题。

TAGE 分支预测器

TAGE 预测器的结构如图所示，可以看到他和先前的 GPPM 预测器如出一辙。不过在细节上，TAGE 预测器和 GPPM 预测器依然存在一些差异。

文章中仅提出了一种参数化的 TAGE 预测器框架，所以预测器的各部分的具体情况都可根据实际情况进行更改，方便我们考察不同设计之间的性能差异。图中所示的是一个 5-component TAGE 预测器，其由五个分支预测器组成。和 GPPM 类似，最左侧的分支预测器是一个兜底用的基础预测器，右侧的四个是基于标签的全局预测器，这些预测器的权重从左至右依次递增。和 GPPM 不同的是，在组成上，基础预测器不一定是一个双模预测器，而且基础预测器中也不再需要 m 位作为元预测器了；全局预测器中的 u 域也不再是单一的位，而变成了一个计数器——这些改变，都是因为 TAGE 预测器的更新策略相比于 GPPM 有了较大的变化。

文章指出，GPPM 预测器的性能不佳，根本原因是其更新策略设计的不够好，而 TAGE 预测器的更新策略就修正了原先的诸多问题。例如，当分支预测失败时，GPPM 会尝试在上级的多个预测器中各分配一个新的条目，而 TAGE 最多只会在一个预测器中分配新条目，并且通常是离发生失败的预测器最近的那个预测器。在一些情况下，因为 u 计数器的存在，预测失败不会立即导致新条目的分配，这在某种程度上可以避免抖动的现象。

此外，u 计数器的更新策略和之前相比也有所不同。如果 TAGE 在预测时，其内部的多个分支预测器都给出了有效结果，并且优先级最高的两个预测器的结果不相统一，则它们对应项的 u 计数器会被更新，确保预测正确的项的 u 计数器的数值会更高。此外，所有预测器中 u 计数器的数值会被定期减小，以避免某项永远会占据 SRAM 中的宝贵空间的情况，这一点也解决了 GPPM 中存在的问题。

为何 TAGE 如此优秀？

我有相当长一段时间都认为，分支预测这件事本身就是个玄学。因为那些性能很好的分支预测器的结构，看起来似乎都是先对 PC 和分支历史做一个哈希，然后再设置几级不同的 SRAM，再使用某些奇怪的方式更新其中对应项的内容，再如何如何，最终像变魔术一样得到一个分支预测结果。但实际上并非如此，优秀的分支预测器中，每一个结构都有其存在的意义。正如 GPPM 的文章中详细讲述了其结构的设计思路，而 TAGE 这篇文章还详细分析了其与 GPPM 预测器有所不同的具体原因。

相比于 GPPM，TAGE 预测器的更新策略最大限度地降低了单一预测结果所引发的扰动。同时，为了使得每个单独的分支历史和分支地址，尽可能和分支预测器中的项一一对应，TAGE 在预测错误时最多只会分配一个新条目，而 GPPM 可能会分配多个。另外，TAGE 中 u 计数器的设计，无论是针对分支预测结果进行增减，还是定期减小 u 计数器的数值，都是为了模拟 LRU 策略，从而实现尽可能科学的分支记录替换算法。这些分析都在理论上解释了 TAGE 比 GPPM，乃至其他各类分支预测器优秀的原因。

GPPM 和 TAGE 在设计思路上，也有很多优秀之处。比如他们在全局预测上都采用了基于标签的思路，只有在由分支历史和分支地址计算得到的标签成功匹配时，预测结果才会有效，而早期的 Gshare 分支预测器中并不存在这样的设计。这在很大程度上避免了分支历史和分支地址 hash 之后导致的碰撞，从而进一步避免了不相干分支的预测结果对当前预测结果的干扰，这自然会带来理论上更高的预测正确率。因为前文提到分支预测器的设计需要向现实妥协，这就导致存储分支记录的存储器不能设置的很大，就像缓存一样，它也会存在各种别名问题，而标签就是为了解决别名而设计的。

另外，TAGE 预测器还可以更好的根据不同的情景，选择合适的策略对分支进行预测。先前提到的分支预测器，无论是单一的分支预测器还是融合的分支预测器，可供选择的策略都太少了。TAGE 在设计上可支持多个全局预测器，在多种不同的历史长度中进行选择，从而支持多种不同的策略。并且，无论是 McFarling 提出的融合预测器，还是 Alpha 21264 采用的竞争预测器，它们虽然也提供了分支预测策略的选择，但用于选择策略的机制依然太过简单，无法适应更多复杂的情况。TAGE 的选择和更新策略可以在学习中不停的淘汰不适合当前情况的策略，并且持续选择最合适的策略进行预测，这也是 TAGE 的精妙所在。

总结

分支预测器只是处理器前端中的一个很小的组成部分，但它本身却集成了数十年来各路研究人员的天才般的智慧。本篇读书报告本来只打算针对 TAGE 预测器的文章进行撰写，但在文献阅读的过程中我逐渐发现，分支预测器的设计思想并不是凭空产生的，现代的许多优秀的分支预测器，在设计思路上往往有着许多历史思想的传承。随着阅读文献的数量的增加，我越来越能感觉到分支预测器在这几十年的历史中发生的变革，也似乎理解了分支预测器的一些深层的设计原理。而在阅读文献的过程中，我也逐渐体会到，优秀的研究具体是什么样子的，优秀的故事应该如何讲述，优秀的实验应该怎样开展。希望我也能在硕士研究生的三年生涯中，做出一样优秀的研究成果。