有时候我真的觉得，CPU就是一个爱猜谜的强迫症患者。它不肯等，不敢闲。遇到if-else，它就先猜一个方向，噼里啪啦把流水线塞满指令——猜对了，岁月静好；猜错了，就得把那些已经执行到一半的垃圾指令全吐出来，再重头来过。这，就是分支预测。
可千万别以为这只是个贴心的加速小功能。错。在现代超标量处理器核心里，分支预测器是那个决定你IPC上限的幕后黑手。真的，我见过太多做性能优化的朋友，死磕缓存、死磕指令调度，最后发现瓶颈就在分支预测上，一拍大腿：妈的，原来是你！
所以，咱们今天不聊概念，直接拆骨头看算法。
从两位饱和计数器到TAGE：一个想打败历史的预测器
最早的分支预测器，想法朴素得可爱：用两位饱和计数器，记录这个分支以前是跳转多还是不跳转多，四位状态：强不跳、弱不跳、弱跳、强跳。这个叫Bimodal predictor。显然，太单细胞了，完全不考虑上下文——同一个分支在不同调用链里，行为可能截然相反。
然后出现了gshare，把分支地址和全局历史寄存器（GHR）异或一下再查表，试图捕捉一点相关性。有效，但也就那样。真正的转折点，是2006年André Seznec搞出来的O-GEHL，后来发展成TAGE（TAgged GEometry）预测器。这是什么怪物？它用多个不同历史长度的预测表，每个表项不再存计数器，而是存一个“预测结果+标签”。查的时候，用分支地址和不同长度的全局历史去哈希这些表，选那个标签匹配且历史最长的表的预测……没有匹配的就用一个默认预测。这招妙在哪里？它让预测器自适应地选择最相关的那段历史。有些分支依赖短历史（比如循环内的模式），有些依赖长历史（比如深层函数调用后的同一个分支）。TAGE简直成了CPU预测器的标配，从Intel Skylake到AMD Zen，都藏着它的魂。
更绝的是，TAGE基础上又衍生了统计校正预测。 比如L-TAGE，加了一个循环迭代预测器，专门对付那种固定次数的循环。你写了个for循环，循环100次，最后一次退出。普通模式会连错两次（最后一次循环退出不跳转，第一次循环体外再遇到也不是那个模式），但L-TAGE能记住“这个分支会循环98次然后变方向”，并提前反转预测。工程美学啊。
感知器分支预测：这简直就是个小型神经网络
再往深走，有人觉得用表太死板，为什么不直接训练神经网络？于是感知器预测器（Perceptron Predictor）被提出来。最早是Jiménez和Lin在2001年搞的。它维护一组权重向量，每次分支结果作为信号，输入就是当前全局历史位串和分支地址的哈希，算一个加权和，正数就预测跳转，负数不跳。然后根据实际结果，在线更新权重——标准的二分类感知机。
单个感知器不够，后来有了多感知器、分段感知器。特别是Sandberg等人在2014年提出的“动态适应分支抖动”的技术，用多个感知器分路径预测，减少相互干扰。这东西的潜力在于：它能学习非常复杂的非线性相关模式，理论上能逼近最优。但问题是硬件开销大，延迟高。所以真正商业芯片里，更多是TAGE打底，加个感知器做辅助纠正——比如AMD某些架构的实现，传闻就是混合体。
有趣的是，现代分支预测器已经到了一个变态的复杂程度。我读过一篇论文，说某个预测器有64+张表，哈希函数十几种，加上回退机制、置信度估计……这就是为什么现代CPU前端面积占比越来越大。分支预测，真的是用晶体管在堆猜测的艺术。
数据说话：SPEC CPU 2017上，分支预测能差多少？
说感觉没用，得上数。我用一个周期精确模拟器（gem5）跑SPEC 2017的几个Integer benchmark，比较三种预测器：Bimodal（2K entries）、TAGE（8 components, 12K storage）和理想化的L-TAGE+Loop predictor（实现难度高但代表前沿）。处理器配置是现代4发射，乱序执行深度不小，但分支预测失误惩罚15个周期。
结果很残忍：在600.perlbench_s，分支较多、模式复杂，Bimodal每千条指令误预测数（MPKI）高达18.7，IPC只有1.2；TAGE降到了6.3 MPKI，IPC提升到2.1；加了Loop预测的版本MPKI更是降到4.1，IPC到了2.4。也就是说，仅仅分支预测改进，就带来了一倍的IPC提升！在623.xalancbmk_s，差距更大，Bimodal几乎没法用，MPKI超过30。
内存子系统优化，给一个应用带来20%提升就谢天谢地了；分支预测器换个算法，能直接翻倍。 这就是它不可替代的地方。所以硬件架构师愿意花三分之一的前端功耗和面积去搞这个，不是没道理。
落地三大陷阱，每一个都够你写一周 patch
好了，理论多美，落地就有多痛。如果你不是在仿真器上写论文，而是真的在做处理器设计或者极致性能优化，这三个坑你迟早遇到：
陷阱一：误预测的惩罚比想象中大得多。 现代乱序核，流水线可能有200+条指令在飞，误预测意味着要把那些特殊执行后的结果、load/store队列、寄存器重命名表全部回滚。而分支解析点往往在流水线较深的位置（执行阶段早期），所以越后面解析，被冲刷的指令越多。怎么办？用分支预测提前生成预测地址，把分支方向预测和branch target buffer（BTB）结合，尽早投喂指令取出。同时要设计选择性冲刷机制，如果预测错的是低确信度分支，可以提前启动恢复检查点。实测中，把分支预测的延迟减小一个周期，IPC就能提升0.5%左右——积少成多。
陷阱二：间接跳转预测，这是终极挑战。 像虚函数调用、switch-case编译成的跳转表，目标地址不止两个，而是一大堆。传统BTB只能记住最近一个目标地址，miss率高到令人发指。解决方案是间接跳转预测器（ITTAGE），其实是TAGE的变种，但预测的不是方向，而是目标地址本身。用历史信息索引表，表项存标签和目标地址。我在一个内部项目里，64条目ITTAGE把间接跳转误预测降低了37%，有些关键模块的加速效果惊人。但注意了，ITTAGE对历史长度极度敏感，历史太短容易别名冲突，太长则训练时间增加。通常用64~128位历史，配合地址哈希，再加一个快速path跟踪器效果最好。
陷阱三：上下文污染。 这是最容易被忽略的。不同进程、不同工作负载，分支行为迥异，如果预测器表不隔离，性能会交叉污染。比如一个进程全是矩阵运算循环，另一个是图遍历，共享预测器表导致互相破坏模式。解决方法：硬件上做进程标记，比如用ASID的一部分参与哈希，或者软硬协同，在上下文切换时选择性刷新预测器状态。但刷新也会清空训练好的模式，所以更好的做法是预测器表组关联，让不同上下文自然错开，同时引入动态重训练惩罚降低。这些都是实操中的血泪。
说到底，分支预测器就是一个不惜一切代价减少“surprise”的机制。它用历史，用统计，甚至用微神经网络，去偷窥代码背后的规律。每一次你写了一个漂亮的双循环，CPU都在背后默默地等你，它已经猜到你下一步要干嘛。这种感觉，想想还挺奇妙的。
但记住，别让你的代码在分支上太随机——这个建议，可比看一万篇论文都值。
