最近看到一篇绝佳的文献《Processor Microarchitecture: An Implementation Perspective》，刚好能回答这个问题。
本文为该论文阅读笔记，对应原文第三章「The Instruction Fetch Unit」，主要介绍了取指单元的一些设计方法。感兴趣的同学推荐去阅读作者的原文。
一、取指单元概述
取指单元（Instruction Fetch Unit）负责向处理器输送需要执行的指令，主要由 Instruction Cache 和 计算下一个指令地址的单元组成。由于当下的高速处理器每一个周期会至少消耗一条指令，因此对于取值单元来说，下一条指令地址的计算必须和 ICache 的访问并行执行。
对于正常执行的指令来说，只是继续向下取指即可；但对于分支指令来说，由于分支跳转的地址只有在执行完之后才能真正确定，这会非常的耗时。大多数高性能处理器为了应对此问题，都会有分支预测(branch prediction)的功能，来预测分支指令下一条指令的地址，具体需要完成如下两个功能：
- 预测分支的 true or false：主要由分支预测器 (branch predictor) 完成
- 预测分支的跳转地址：主要由 BTB (branch target buffer) 完成。有些处理器还会有返回地址栈 (return address stack，RAS) 来预测函数返回时的地址
上图给出了取指单元的一般结构图。可以看到，下一条指令的地址会有多个来源。取指单元最终选择其中一个结果，从 ICache 中取指：
- 正常线性取指：直接取下一条指令
- BTB：预测的分支指令跳转地址
- RAS：提供函数返回的地址
- 执行单元返回的地址：一般是执行单元在发现分支预测错误或者发生异常时，提供的跳转地址
二、Instruction Cache
为了尽可能地减少分支预测错误而造成的重新取指的延迟，ICache 一般用 data & tag parallel 的方式，以达到节省一个 cycle 延迟的目的。
另外，ICache 会倾向于使用 VIPT(virtual index physical tag) 的方式，让 TLB 访问和 Cache 访问并行，从而减少取指延迟。
对于超标量处理器来说，一个周期会需要多条指令。不过大多数情况下 Cache Line 的长度(典型值为 64Byte) 能够覆盖多条指令，因此单端口的 ICache 就足够了。_（不知道最新的架构会不会需要多端口）_
（另外在翻看 wikichip 的时候，发现即使是最近的 arm 架构，例如 Neoverse N1，L1 ICache 的端口速率仅有 16 byte/cycle，如果是 4 发射的 EU 的话，连发射所需的指令数都跟不上。但是 fetch 单元却可以输出 4-8 条指令，不知道是不是主要靠 MOPs Cache 来缓存已经解码过的指令来维持发射速率）
2.1 Trace Cache
和按照程序二进制文件的顺序存储指令的传统 ICache 不同，trace cache 会记录运行时分支 taken or not taken 的情况，将该组合的指令连续存放。由于分支在运行时会有不同的组合，因此同一个指令会在 trace cache 中被存放多份，而不像传统的方式一样只存储一份。这种 cache 组织方式会最大程度的保证指令被连续读取，因此在分支较多的程序中会有比较高的收益。
（但我这里个人理解，只有在分支的 pattern 比较固定时，才能明显避免 PC 来回跳转，不然跟传统的 Cache 没有什么区别。另外配合分支预测的话，传统 Cache 可能也没多少损失？感觉有点奇怪，可能是我对这段的理解不太对劲）
三、Branch Target Buffer (BTB)
要想实现预测一条指令是否为分支指令，只需要在硬件上添加一个以 PC 为 index 的表即可。该表的表项里面，可以仅使用单个 bit 来标记该指令是否为分支指令，也可以用多个 bit 来更精细的标记该指令具体的分支类型（如条件分支、函数调用、函数返回等等）。
除了指令类型外，表项中还会包括预测的该分支指令的目标地址。另外对于条件分支指令来说，还需要一些能够预测该分支是否要跳转的信息。
分支指令的目标地址通常就存放在表项中，如下图所示：
当取指时的 PC 在表中找到匹配的 index 时，说明该指令为分支指令。硬件会接着读取表项，将表项中的目标地址作为预测的跳转地址。表项中存储的目标地址，往往是该分支上一次实际跳转的地址。当发现跳转地址错误时，硬件会更新该表项。
这个既可以在指令解码前就预测指令是否是分支指令，也可以预测分支指令的目标地址。这个表往往被称为 branch target buffer (BTB)。
在程序中，绝大多数的分支有两个明显的特点：
- 分支跳转的目标地址是定值；
- 跳转地址往往离 PC 不远。
因此，使用最多的分支指令是 PC relative 类型的分支指令，即目标地址为 PC + offset，这种指令在循环结构中很常见。
对于 offset 固定的 PC relative 指令，虽然目标地址可以直接计算得到，但是需要在分支预测单元加一个加法器，这一行为会导致一个周期的气泡。为了避开这一个周期的气泡_（当然更多的是为了适配更多类型的分支指令）_，目标地址最好还是以预测而非计算的方式得到。
当使用了 BTB 后，对于这类指令，由于目标地址是不变的，目标地址项并不需要更新，每次预测的地址也保证是正确的。而对于目标地址需要在 runtime 才能确定的指令，也能一定程度的预测正确，不必每次都等到目标地址被算出后再跳转。
四、Return Address Stack (RAS)
对于函数来说，由于可能在多个地方被调用，其返回地址会变化很大。用 BTB 虽然可以预测返回地址，但准确率并不高。
不过众所周知，函数的调用是一级一级进行的，返回也是一级一级逆序进行的。因此硬件上用一个 LIFO 的栈结构就能很好的确定函数的返回地址，该栈结构就是 return address stack (RAS)。
当程序调用函数时，硬件会对 RAS 压栈。而当硬件取到的指令被判定为返回指令时（用前面 BTB 的 tag 就能判别），直接将 RAS 的栈顶地址弹出作为预测的返回地址即可。
一般来说，RAS 的项数不会很多（一般为数十项）。当函数调用层级过深，超过 RAS 深度时，旧的项会被清除，保留最新的项。不过对于绝大多数程序而言，这种事情不太会发生。
五、Conditional Branch Prediction
条件分支是指那些不在 runtime 计算结果，就无法决定是否需要跳转的分支。当然，如果等到硬件执行单元计算出条件结果后再跳转的话，会插入很多气泡，不利于硬件性能。因此需要对这类分支的条件进行预测，决定分支是否要跳转。
分支条件的预测，可以通过静态方法进行，也可以通过动态方法来进行，或者是两者的结合。
5.1 静态分支条件预测
一种静态分支预测的方法是：对程序进行 profiling，即真实运行程序并统计每个分支跳转的情况，根据统计结果决定每个分支是否跳转，并通过编译器将结果写到程序中。指令需要有额外的 bit，用来指示该指令被预测为跳转或不跳转_（当然硬件发现预测错误后，还是会 flush 流水线重新取指的）。_
这种方式的好处是硬件设计简单，硬件上几乎不需要什么分支条件预测的逻辑，只需要读编译器写入的 bit（1 bit 就够）即可完成分支条件预测。但缺点也很明显，就是预测的精度可能不是很高。
5.2 动态分支条件预测
动态分支条件预测是指硬件单元收集一些过去的程序运行时的信息，通过这些信息来动态的预测分支条件。
一种非常经典的动态分支条件预测器结构如下图所示：
程序过去执行时分支的信息被存放在一个长度为 2^n 的表中，表中的每一项为 2 bit。该表通过指令 PC 的最低 n bits 来索引。每一项的 2 bits 都构成一个有限状态机，用来预测分支跳转条件。
这种预测器被称作局部分支预测器（local branch predictor）。这是因为该预测器在进行预测时，每个分支指令只使用自己过去的跳转状态来进行预测。对于 highly biased 的分支（不知道该咋翻了，大概意思就是分支在一定时间内要么经常跳转，要么经常不跳转，总之会偏向一边），该分支预测器表现很好。如果分支条件经常是 not taken，那么状态机的状态会是 00；而如果分支条件经常是 taken，那么状态机的状态会是 11；即使分支条件 taken or not taken 发生变化，只要在一定时间内不要频繁波动，状态机也会跟随这分支条件的变化而有效变化。
当然，两个分支指令的最低 n bits 有可能是完全一样的，因此会映射到同一个表项中，这种情况被称为 aliasing。一般来说，aliasing 会降低这类预测器的性能（毕竟会互相干扰嘛）
2-bit 局部分支预测器一般可以达到 >80% 的预测精度，在一些特殊的程序上可以达到 99%。但是对于高性能的处理器来说，由于预测错误带来的性能损失，即使只有 10% 的预测错误也会造成很大的性能影响。预测错误会导致流水线被 flush，取指单元需要重新从正确的分支地址中取出指令，重新填充流水线，这一过程至少需要 10+ 周期。这对于分支较多的程序来说影响会非常大。如果处理器是一个超标量处理器的话，一次分支预测错误带来的损失则会更大。例如处理器重新填充流水线需要 10 个周期，每个周期可以 4 发射的话，一次错误的分支预测相当于损失了 40 条指令的执行。
为了进一步提升分支条件预测器的精度，目前的处理器会引入一种叫关联预测器（correlating predictor，或被称为 two-level branch predictor）的硬件单元。不同于局部预测器，关联预取器不仅会根据当前分支指令的历史信息来预测，还会根据它的“邻居”的历史信息来预测。
一种最简单的关联预测器结构如下：
硬件用一个叫 branch global history 的寄存器，来存储最近几次分支的条件结果（每个分支用 1 bit 存储即可）。一般 10~20 个 bit 就足够了。这个寄存器跟指令 PC 做 hash 后，得到的 index 用来从表中选取状态机。更新分支预测结果时，也用同样的方法从表中找到对应的状态机并更新。这种预测器也被称为 gshare。
关联预测器的核心思路是：对于同一个分支指令，根据不同的全局分支条件结果，选用不同的状态机来预测当前分支的条件结果。当然，关联预测器也无法完全避免 aliasing 的问题。如果每一种分支条件结果、每一个分支都有对应的状态机的话，虽然 aliasing 的问题被避免了，但表项会过大。因此为了保证硬件设计的高效，aliasing 还是不可避免的，但从性能角度上能一定程度上容忍。
branch global history 有很多种跟 PC 做 hash 的方式。例如前面提到的 gshare，两者通过 bitwise OR 操作来作为 index 就能取得不错的效果。当然也可以像下图一样，用多个寄存器来存储全局的历史分支信息。预测时，先通过 PC 选择用哪个寄存器，再通过该寄存器与 PC 的 hash 后得到的 index 从表中选择状态机：
影响关联预测器预测分支条件精度的因素有：
- global history register 的数量
- 有限状态机表的项数
- 有限状态机状态数量（比如 3-bit、4-bit 有限状态机有更多的状态数）
- PC 到状态机的映射方法（例如 hash 函数是怎样的，多个 global history register 如何选择等等）
没有适合所有程序的预测器。有的程序可能更适合使用全局分支信息来进行预测，而有的程序可能恰恰相反。因此，一些处理器会集成多种预测器，并进行混合。
混合分支预测器（hybrid branch predictors）除了有多个预测器外，还有一个额外的单元用来选择具体采用哪个预测器的结果（selector），其结构如下图所示：
selector 也是根据 PC 和一些全局信息，选定有限状态机来决定使用哪一个预测器的结果。当分支执行的结果出来后，根据多个预测器的表现，来更新选择的策略（当然预测错误的预测器本身也需要更新）。
混合分支预测器不仅仅可以适应不同的程序，它的另一项作用在于：不同的预测器 warm-up 时间不同，因此需要 selector 在程序执行的不同时间点选择合适的预测器。当程序刚刚启动，或 CPU 刚刚从别的线程切换回来时，预测器里面存储的信息是与当前程序无关的，无法用来准确预测分支条件，需要运行一段时间进行 warm-up 来将预测准确率提升到较高水平。局部预测器因为只使用当前分支的历史跳转情况，因此能够很快的完成 warm-up；而关联预测器虽然最终预测精度较高，但需要更长的时间 warm-up。因此当发生程序刚启动或线程切换的情况时，selector 会先选择 warm-up 较快的局部预测器，一段时间后选择精度更高的关联预测器。
▎论文链接：
https://www.morganclaypool.com/doi/abs/10.2200/S00309ED1V01Y201011CAC012
作者： 田子宸
文章来源：OpenPPL
推荐阅读
更多嵌入式AI干货请关注 嵌入式AI 专栏。欢迎添加极术小姐姐微信（id:aijishu20)加入技术交流群，请备注研究方向。
