分支预测损耗分析
背景
CPU组成：控制器CU（Control Unit）：指令寄存器IR(InstructionRegister)、程序计数器PC(ProgramCounter)、操作控制器OC(OperationController)；算数逻辑运算单元ALU；寄存器。
指令流水线（Instruction pipeline）：计算机指令在CPU内部会会被转译成一个或多个微指令（uop），这些uop在不同的cpu模块中依次执行。如果CPU一次处理一个指令，那么某个模块在执行时，其他模块都处于空闲状态，所以CPU会将多条指令以流水线的形式执行，以充分利用CPU模块提高吞吐来提高多指令执行速度，即指令流水线。
指令流水线级数(depth)：一个指令被分成多少个阶段执行。
CPU时钟周期：流水线最慢一级的处理时间（逻辑处理+流水线寄存器）
流水线延迟：完整的指令处理时间（指令流水线级数*CPU时钟周期）
吞吐量：每秒可处理最小单位指令数（G instruction per second）（1s/CPU时钟周期）
如三级流水线的CPU架构中，三条指令I1、I2、I3能够在4个时钟周期完成：
分支预测
CPU处理分支时会先预测将会执行的指令，然后将对应的指令放进流水线，但可能会预测错误，导致流水线清空。
分支预测错误成本
记D=流水线深度，K=指令预测错误出现的深度，则分支预测错误的成本为（K-1）时钟周期。所以流水线级数越高，分支预测错误带来的损耗越大。
预测错误演示和分析如下：
以4级流水线为例，4条一般指令（不同颜色）可以在8个时钟周期内通过不同的阶段并执行完。
而如果绿色跟紫色指令有依赖关系，如分支依赖、数据依赖，则在第3个时钟周期，本应该译码的紫色需要等待绿色执行完后再进行，增加的气泡表示指令延迟，相当于nop；第4时钟周期时，绿色执行后，紫色才恢复执行。此时指令执行完成额外消耗1个时钟周期。
而如果绿色跟紫色指令是分支（控制）依赖关系，且分支预测错误了，则会将当前流水线清空，并将正确分支的指令重新放进流水线执行；如Clock4，新的三条指令被重新放进pipeline重新开始执行。最终指令执行完成额外消耗3个时钟周期。
分支预测器
分支預測器（英語：Branch predictor）是一種數位電路，在分支指令執行結束之前猜測哪一路分支將會被執行，以提高處理器的指令管線的效能。
動態預測：利用分支指令發生轉移的歷史來進行預測，並根據實際執行情況動態調整預測位，準確率可達90%，現在幾乎所有處理器都採用動態預測。
详细的分支预测器介绍：分支预测器介绍
C++关键字 __builtin_expect
likely/unlikely作用于编译器，编译器将更可能的分支指令放在分支后面，而更不可能的分支指令需要跳转执行，这样CPU分支预测器在预测的初期会更倾向于预测顺序执行的指令；而当CPU分支预测器的样本足够时会自动调整该分支预测结果。所以likely/unlikely对分支刚开始执行时有帮助，基本上还是依赖于CPU的分支预测器。
Many CPUs have a branch predictor, thus using these macros only helps the first time code is executed or when the history table is overwritten by a different branch with the same index into the branching table. stackoverflow
REFER
L11-Pipelined-Datapath-And.pdf
部分微架构流水线级数
| 微架構 （Microarchitecture） | 管線層數 （Pipeline stages） |
|---|---|
| Sony Cell | 23 |
| IBM PowerPC 7 | 17 |
| IBM Xenon | 19 |
| AMD Athlon | 10 |
| AMD Athlon XP | 11 |
| AMD Athlon 64 | 12 |
| AMD Phenom | 12 |
| AMD Opteron | 15 |
| ARM7TDMI (-S) | 3 |
| ARM7EJ-S | 5 |
| ARM810 | 5 |
| ARM9TDMI | 5 |
| ARM1020E | 6 |
| XScale PXA210/PXA250 | 7 |
| ARM1136J (F)-S | 8 |
| ARM1156T2 (F)-S | 9 |
| ARM Cortex-A5 | 8 |
| ARM Cortex-A8 | 13 |
| AVR32 AP7 | 7 |
| AVR32 UC3 | 3 |
| DLX | 5 |
| Intel P5（Pentium） | 5 |
| Intel P6（Pentium Pro） | 14 |
| Intel P6（Pentium III） | 10 |
| Intel NetBurst（Willamette） | 20 |
| Intel NetBurst（Northwood） | 20 |
| Intel NetBurst（Prescott） | 31 |
| Intel NetBurst（Cedar Mill） | 31 |
| Intel Core | 14 |
| Intel Atom | 16 |
| LatticeMico32 | 6 |
| R4000 | 8 |
| StrongARM SA-110 | 5 |
| SuperH SH2 | 5 |
| SuperH SH2A | 5 |
| SuperH SH4 | 5 |
| SuperH SH4A | 7 |
| UltraSPARC | 9 |
| UltraSPARC T1 | 6 |
| UltraSPARC T2 | 8 |
| WinChip | 4 |
| LC2200 32 bit | 5 |
Gitalking ...