分支預測器
Clash Royale CLAN TAG#URR8PPP
 | 本條目需要擴充。 (2012年4月29日) |
在電腦架構中，分支預測器（英语：Branch predictor）是一種數位電路，在分支指令执行结束之前猜測哪一路分支將會被執行，以提高处理器的指令流水线的效能。使用分支預測器的目的，在於改善指令管線化的流程。現代使用指令管線化處理器的效能能夠提高，分支預測器对于现今的指令流水线微处理器获得高性能是非常关键的技術。
目录
1 简介
2 实现
2.1 静态预测
2.2 下一行预测
2.3 饱和计数
2.4 两级自适应预测器
2.5 局部分支预测
2.6 全局分支预测
2.7 融合分支预测
2.8 Agree预测器
2.9 循环预测器
2.10 间接跳转预测
2.11 函数返回的预测
2.12 overriding分支预测
2.13 神经分支预测器
3 历史
4 参考文献
5 外部链接
简介
条件分支指令通常具有两路后续执行分支。即不采取（not taken）跳转，顺序执行后面紧挨JMP的指令；以及采取（taken）跳转到另一块程序内存去执行那里的指令。
是否条件跳转，只有在该分支指令在指令流水线中通过了执行阶段（execution stage）才能确定下来。
如果没有分支預測器，处理器将会等待分支指令通过了指令流水线的执行阶段，才把下一条指令送入流水线的第一个阶段—取指令阶段（fetch stage）。这种技术叫做流水线停顿（pipeline stalled）或者流水线冒泡（pipeline bubbling）或者分支延迟间隙。这是早期的RISC体系结构处理器采用的应对分支指令的流水线执行的办法。
分支预测器猜测條件運算式两路分支中哪一路最可能发生，然后推测执行这一路的指令，来避免流水线停顿造成的时间浪费。如果后来发现分支预测错误，那么流水线中推测执行的那些中间结果全部放弃，重新取得正确的分支路线上的指令开始执行，这招致了程序执行的延迟。
在分支预测失败时浪费的时间是从取指令到执行完指令（但还没有写回结果）的流水线的级数。现代微处理器趋向采用非常长的流水线，因此分支预测失败可能会损失10-20个时钟周期。越长的流水线就需要越好的分支预测。
一条条件跳转指令第一次遇到，还没有任何信息可以去预测分支。此后保持这条指令是采取还是不采取跳转的历史记录，就可以作为再遇到这条指令时猜测最可能的分支。
分支预测不同于“分支目标预测”（Branch target predictor）。后者是指对指令高速缓存中的内容，检测出其中的条件跳转指令与无条件跳转指令，然后为指令高速缓存预装入（prefetch）相应的跳转目标代码块。
实现
静态预测
静态预测（Static prediction）是最简单的分支预测技术，因为它不依赖于代码执行的动态历史信息。代替地，它仅依赖于分支指令自身。[1]
SPARC与MIPS的最早实现（作为第一代商用RISC体系结构处理器）使用单方向静态分支预测：总是预测条件跳转不发生，因此总是顺序取下一条指令推测执行。仅当条件跳转指令被求值确实发生了跳转，则非顺序的代码地址被加载执行。两种CPU都是在解码阶段评价分支指令，取指令占用1个周期。因此分支目标需要两个周期（即经过了取指令、解码两个周期）才能确定。两种处理器都会在分支指令进入流水线的执行阶段时，插入一个分支延迟间隙。分支指令完成流水线的执行阶段，就已经能确定是否跳转，这时就可以决定是后续的顺序出现的指令被继续执行还是跳转到的新指令进入流水。
更复杂的静态预测假定向后分支将会发生，向前的分支不会发生。向后分支，是指跳转到的新地址比当前地址要低。这有助于配合经常出现的程序的循环控制结构。
一些处理器允许分支预测提示出现在代码中。Intel Pentium 4就是如此。但这一特征在Intel此后的处理器中不再支持。[2]
静态预测也用于某些处理器分支动态预测没有任何可用信息时的一个最后的办法。Motorola MPC7450 (G4e)与Intel Pentium 4都是如此。[3]
下一行预测
一些超标量处理器(MIPS R8000, Alpha 21264 and Alpha 21464 (EV8))使用此种技术。
饱和计数
饱和计数器（saturating counter）或者称双模态预测器（bimodal predictor）是一种有4个状态的状态机：
2位饱和计数器
- 强不选择（Strongly not taken）
- 弱不选择（Weakly not taken）
- 弱选择（Weakly taken）
- 强选择（Strongly taken）
当一个分支命令被求值，对应的状态机被修改。分支不采纳，则向“强不选择”方向降低状态值；如果分支被采纳，则向“强选择”方向提高状态值。这种方法的优点是，该条件分支指令必须连续选择某条分支两次，才能从强状态翻转，从而改变了预测的分支。
最初的不具有MMX的Intel Pentium处理器使用了这种饱和计数器。虽然实现不够完美。[2]
在SPEC'89 benchmark测评中, 饱和预测达到了93.5%正确率，如果每条条件分支指令都映射了自己的计数器。[4]
预测器表使用条件分支指令的地址作为索引。因此处理器可以在分支指令解码前就给它分配一个预测器。
两级自适应预测器
两级自适应预测器。pattern history table中的每个条目是上文的2位饱和计数器。
对于一条分支指令，如果每2次执行发生一次条件跳转，或者其它的规则发生模式，那么用上文提到的饱和计数器就很难预测了。如图所示，一种二级自适应预测器可以记住过去n次执行该指令时的分支情况的历史，可能的2n种历史模式的每一种都有1个专用的饱和计数器，用来表示如果刚刚过去的n次执行历史是此种情况，那么根据这个饱和计数器应该预测为跳转还是不跳转。
例如，n = 2。这意味着过去的2次分支情况被保存在一个2位的移位寄存器中。因此可能有4种不同的分支历史情况：00, 01, 10, 11。其中0表示未发生跳转，1表示发生了分支跳转。现在，设计一个模式历史表（pattern history table），有4个条目，对应于2n = 4种可能的分支历史情况。4种历史情况的每一种都在模式历史表对应于一个2位饱和计数器。分支历史寄存器用于选择哪个饱和计数器供现在使用。如果分支历史寄存器是00，那么选择第一个饱和计数器；如果分支历史寄存器是11，那么选择第4个饱和计数器。
假定，例如条件跳转每隔2次执行就发生一次，即分支情况的历史序列是001001001...。在这种情况下，00对应的饱和计数器将是状态“强选择”（strongly taken），表明在两个0之后必然是出现一个1。01对应的饱和计数器将是状态“强不选择”（strongly not taken），表示在01之后必然是出现一个0。这也同样适用于10状态。而11状态从未使用，因为不可能出现连续两个1。
2级自适应预测器的一般规则是n位分支历史寄存器，可以预测在所有n周期以内出现的所有的重复序列的模式。[2]
2级自适应预测器的优点是能快速学会预测任意的重复模式。此方法1991年被提出。[5] 已经变得非常流行。以此为基础很多变种方法被用于现代微处理器。
局部分支预测
局部分支预测（local branch predictor）对于每个条件跳转指令都有专用的分支历史情况缓冲区；模式历史表可以是专用的，也可以是所有条件分支指令共用。
Intel Pentium MMX, Pentium II, Pentium III使用局部分支预测器，记录4位的历史情况，每条条件跳转指令使用专用的局部模式历史表，当然是包含24 = 16个条目。
对SPEC'89 benchmark测评，非常大的本地预测器的正确率达到97.1%[6]。
全局分支预测
全局分支预测器（global branch predictor）并不为每条条件跳转指令保持专用的历史记录。相反，它保持一份所有条件跳转指令的共用的历史记录。优点是能识别出不同的跳转指令之间的相关性。缺点是历史记录被不相关的不同的条件跳转指令的执行情况稀释了（diluted）；甚至历史记录没有一位是来自同一个分支指令，如果有太多的不同的分支指令。
这种方法只有在历史缓冲区足够长，才能发挥出效能。但是模式历史表的条目数是历史缓冲区位数的指数量级。因此只能是在所有的条件跳转指令间共享这个大的模式历史表。
AMD的CPU，以及Intel的Pentium M, Core，Core 2使用了此种方法。
SPEC'89 benchmark评测，非常大的gshare预测器达到了96.6%正确率，略低于局部分支预测。
融合分支预测
融合分支预测器（alloyed branch predictor）[7]组合了本地与全局预测原理，把本地与全局的分支历史情况连接（concatenating）起来。VIA Nano处理器可能采用此方法。[2]
Agree预测器
Agree预测器是一种两级自适应全局预测器，但是附加了一个bias饱和计数器，用来记录历次预期的准确度。最终输出结果是全局预测与bias饱和计数器的异或[8]。Intel Pentium 4使用了此种方法，但此后的Intel处理器放弃了此种方法。
循环预测器
程序循环的控制部分所对应的条件跳转指令最好用专门的循环控制器来预测分支。将要重复N次的循环的底部的条件跳转指令，前N-1次选择跳转，只有一次不跳转而是顺序执行。条件跳转指令有很多次选择了一条分支，只有一次选择另一分支，这种行为将被作为循环行为被检测。这种条件跳转指令可以用简单的计数器很容易地检测出来。循环预测器是一种混合预测器，其中元预测器判断该条件跳转指令是否具有循环行为。许多微处理器现在都有循环预测器。[2]
间接跳转预测
间接跳转指令（indirect jump）是指操作数不是要转去的下一条指令地址（这是直接跳转），而是一个存储位置（寄存器或者内存），这个存储位置的内容才是要转去的下一条指令地址。例如je EAX，表示在ZF标志寄存器为1情况下，跳转到寄存器EAX所保存的内存地址开始的代码快。
间接跳转指令可以选择多于两条分支的执行路线。Intel与AMD的更新的处理器使用两级自适应预测器能预测间接跳转。间接跳转指令在历史缓冲区贡献了超过1位的表示。没有这种预测机制的处理器，就简单地预测间接跳转指令是否会如同上次一样选择同一目标。[2]
函数返回的预测
许多处理器有专门用于表示函数调用返回地址的return stack buffer。[2]
overriding分支预测
快速与精确，是分支预测需要平衡的两个性能指标。有时就设置两个分支预测器。第一个是简单且快速。第二个是更慢、更复杂、表更大、可以覆盖第一个预测器作出的预测。
Alpha 21264与Alpha EV8处理器使用一个快速的、单周期的下一行（next line）预测器处理分支目标，提供一个简单快速的分支预测。两个微处理器都有更复杂的、两个周期的分支预测期，可以覆盖下一行预测器的不准确的结果。
Intel Core i7有两个分支目标预测器（Branch target predictor），可能有两个或更多分支预测器。[9]
神经分支预测器
1999年提出的神经分支预测器（neural branch predictor）[10]。突出优点是能够利用很长的历史记录，仅导致了资源的线性增长。而传统预测器的资源需要量与历史长度是指数增长关系。这种方法主要缺点是高延迟。
神经分支预测器的准确度非常突出。（参见Intel's "Championship Branch Prediction Competition" [11]）。Intel在IA-64的模拟器 (2003)中实现了这一方法。
历史
分支预测对于指令流水线、超标量的处理器是非常重要的，如Intel Pentium, DEC Alpha 21064, MIPS R8000, IBM POWER等处理器。这些处理器依赖于1位或2位预测器。
参考文献
^ P. Shen, John; Lipasti, Mikko. Modern processor design: fundamentals of superscalar processors. Boston: McGraw-Hill Higher Education. 2005: 455. ISBN 0-07-057064-7.
^ 2.02.12.22.32.42.52.6 Fog, Agner. The microarchitecture of Intel, AMD and VIA CPUs. 2009 [2009-10-01].
^ The Pentium 4 and the G4e: an Architectural Comparison, Ars Technica
^ S. McFarling Combining Branch Predictors Digital Western Research Lab (WRL) Technical Report, TN-36, 1993
^ Yeh, T.-Y.; Patt, Y. N. Two-Level Adaptive Training Branch Prediction. Proceedings of the 24th annual international symposium on Microarchitecture. Albuquerque, New Mexico, Puerto Rico: ACM: 51–61. 1991. 引文使用过时参数coauthors (帮助)
^ S. McFarling Combining Branch Predictors Digital Western Research Lab (WRL) Technical Report, TN-36, 1993:8
^ Skadron, K.; Martonosi, M; and Clark, D.W. A Taxonomy of Branch Mispredictions, and Alloyed Prediction as a Robust Solution to Wrong-History Mispredictions. Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques. Philadelphia. Oct 2000. 引文使用过时参数coauthors (帮助)
^ Sprangle, E.; et. al. The Agree Predictor: A Mechanism for Reducing Negative Branch History Interference. Proceedings of the 24th International Symposium on Computer Architecture. Denver. June 1997. 引文使用过时参数coauthors (帮助)
^ WO 2000/014628,Yeh, Tse-Yu & H P Sharangpani,「A method and apparatus for branch prediction using a second level branch prediction table」,发表于16.03.2000
^ Towards a High Performance Neural Branch Predictor, Proceedings of The International Joint Conference on Neural Networks - IJCNN '99, Washington DC, USA, 1999.
^ Championship Branch Prediction 互联网档案馆的存檔，存档日期2008-05-28.
外部链接
- Seznec et al. (1996). "Multiple-Block Ahead Branch Predictors" — demonstrates prediction accuracy is not impaired by indexing with previous branch address.
- Seznec et al. (2002). "Design Tradeoffs for the Alpha EV8 Conditional Branch Predictor" — describes the Alpha EV8 branch predictor. This paper does an excellent job discussing how they arrived at their design from various hardware constraints and simulation studies.
- Jimenez (2003). "Reconsidering Complex Branch Predictors" — describes the EV6 and K8 branch predictors, and pipelining considerations.
Fog, Agner. The microarchitecture of Intel, AMD and VIA CPUs. 2009 [2009-10-01].
Andrews, Jeff. Branch and Loop Reorganization to Prevent Mispredicts. Intel Software Network. 2007-10-30 [2008-08-20]. （原始内容存档于2008-04-17）.
Yee, Alexander. What is Branch Prediction? - Stack Overflow Example.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||
