分支预测：CPU 岔路口的老练指路员

可视化演示

展示现代处理器分支预测核心机制：两级自适应预测器GHR+PHT、TAGE标记几何长度多表预测、BTB目标缓冲与误预测流水线冲刷代价。支持三种模式切换。

分支预测背景

快递分拣中心的传送带一刻不停，流水线上的 CPU 也同理：取指、译码、执行、访存、写回五个工位像接力一样同时干活。可当包裹（指令）走到「如果易碎就走上层」的岔口时，后面的工位就犯难了——不给个准信，他们不知道该提前准备哪路的缓冲材料。若等到分拣结果出来再动手，整条传送带就得干瞪眼等一个周期又一个周期，这就是流水线里著名的控制冒险（control hazard）。

猜错方向，代价更惨：后面已经冲进错误通道的一串包裹全被判了死刑，需要从岔口重新按正确路径再送一遍。在 CPU 术语里这叫 flush（冲刷），被冲掉的指令白白消耗了取指和译码的力气，浪费的周期数差不多等于流水线的深度。也就是说，分支预测器的准确率直接决定了处理器实际能跑多快。

分拣中心意识到，与其等结果，不如高薪请一位「指路员」专门站在岔口前提前喊话。这个岗位，就是 CPU 里那几万个晶体管组成的分支预测器。往后读，你会看到这位指路员从菜鸟长成老江湖的完整故事。

静态与基础预测

最早的指路员最省钱：一根筋，所有包裹一律默认走下层。这叫静态预测（static prediction），编译阶段就定死了，准确率只有可怜的六七成。后来老板换了个机灵点的，让他记住上次这个包裹走哪条路，下次就还猜那条路——这是一位计数器（1-bit counter），状态只有 0 和 1。可它太「健忘」，工人习惯刚变，它就一错再错。

于是老员工想了个稳招：别一锤子买卖，记两次的账。规则是：状态 0 和 1 时预测「不跳」，状态 2 和 3 时预测「跳」；实际走了跳转，状态就往上挪一格，没跳就往下挪一格。这个「挪一格，卡上限」的计数器叫两位饱和计数器（2-bit saturating counter）——饱和，就是数值顶到天花板 3 后不再增加，跌到地板 0 后不再减少。它最大的优点是「有脾气」：偶尔一次异常不会让它变卦，连续两次出错才肯改口。

这位「会记仇」的指路员比一根筋强了不少，稳定模式下的准确率能到 85%~90%。但他只盯着眼前最近的几次记录，有点「记性短」。如果他还能记住整场分拣的「风向」，是不是更厉害？下节的两位老员工来了。

两级自适应

老指路员渐渐发现，光记一个包裹的习惯不够，还得看「今天全场的风向」。暴雨天，几乎所有包裹都往特殊通道走；晴天，大家又回到普通通道。于是他在白板上记下最近连续 8 个岔路口的处理结果，这串 0/1 记录叫全局历史（global history）；某条特定岔路自己的历史则叫局部历史（local history）。把这两种情报合起来用，就是两级自适应预测器（two-level adaptive predictor）。

具体怎么查呢？仓库里有一张巨大的模式历史表（PHT），每栏都是一个小两位计数器。指路员把「当前是几号岔口（PC）」和「最近全场记录（GHR）」揉成一个数值作为栏目号，去表里取那个计数器来预测。不同分支地址与不同历史组合会被散列到不同栏目，互不干扰。最经典的做法名叫 gshare（全局历史共享）：把 PC 和 GHR 逐位异或，再取模落到表上。

有了「个人习惯 + 全场风向」双料情报，指路员的准确率轻松突破 90%。但这位老员工只有一本固定厚度的账本，记忆长度改不了。真正的高手，是随身带着五本厚薄不一的账本，见机行事。

TAGE预测器

赌场老师傅的绝活是「看碟下菜」：对最近的事，用最薄的账本；对很久远但反复出现的规律，得靠最厚的账本。TAGE 预测器（TAgged GEometric history length predictor） 就是这个思路——一组预测器组件 \(T_0, T_1, \dots, T_n\)，第 \(i\) 个组件使用的历史长度按几何级数增长：1、2、4、8、16……位数越多的组件，能看到越长远的相关性。

光有长度还不够，账本里的每一行都得写上「这条记录属于哪个岔口」，否则不同岔口的记录会互相串台。这个标记就是 tag（标签）。预测时，指路员从最厚的账本开始找：哪本账上恰好有这条岔路带相同标记的记录，就相信那本；翻完所有厚的都没有，才轮到最薄的基础账本 \(T_0\)。形式上，找到所有带 tag 匹配的组件中编号最大的那个 \(i^*\)，用它的计数器输出。

凭借多本账本的配合，TAGE 的准确率能站上 95% 甚至更高，成为了现代高性能 CPU 的「指路员之王」。不过方向预测解决了，还有一个遗留问题——如果岔口牌子上根本没写去哪个房间呢？此时 BTB 登场了。

间接分支与BTB

分岔口分两种：一种是牌子上白纸黑字写着「易碎品→上层 3 号口」，目标地址直接刻在指令里，这叫直接分支（direct branch）；另一种是牌子写着「到出口问调度员今天去几号口」，目标地址要运行时才知道，这叫间接分支（indirect branch）。典型代表是函数返回 ret——同一个 return 语句，每次返回的调用点都不同，好比外卖员送完一单，下一单的顾客地址永远是新的。

要提前猜到「去几号口」，指路员需要一本通讯录：BTB（Branch Target Buffer，分支目标缓冲器）。它以分支指令的 PC 为索引，记下上一次这条指令跳去了哪个目标地址。遇到岔口时先查通讯录：查到了，直接报出目标地址，取指单元马上转向；查不到，只能按顺序往后走。对于返回类分支，光靠通讯录不够，还有专门的 RAS（Return Address Stack，返回地址栈），用后进先出的栈机理预测 ret 要回的地方，准确率接近 100%。

BTB 的优化也是门学问：表做多大、几路组相联、tag 分配多少位、按历史模式存多个目标——这些设计决定了通讯录查得快不快、准不准。到此，指路员既知道了往哪边拐，也知道了要进哪扇门。最后一步，是算算请这套人马到底值不值。

性能评估与展望

「值得吗？」永远是老板最关心的问题。横评各家指路员的功夫：静态预测约 70%，一位计数器约 80%~85%，两位计数器约 85%~90%，两级自适应约 90%~93%，TAGE 稳稳超过 95%。差距看似只有几个百分点，但换到「每千条指令出错次数（MPKI）」上可不得了：预测准确率 99% 与 95% 的处理器，错误次数相差近 5 倍，而每次错误都要赔上十来个周期的流水线冲澡。

现代处理器的做法是「组合聘用」：大核用多级 TAGE 做主预测器，配上 BTB、RAS 和专门的循环预测器，各管一摊；小核或嵌入式芯片预算有限，挂一个两位计数器就足够了。分支预测这门岔路口生意经，说到底是在准确率、硬件面积和判断延迟之间做权衡——这恰恰是芯片架构师每天的日常。回到传送带前，那位老练的指路员擦了擦汗，笑了笑：所谓聪明的芯片，不过是把每个岔路口都摸透了。

AI 应用场景

Python 演示

class BranchPredictor:    def __init__(self, mode='two_bit'):        self.mode = mode        self.state = 2          # two-bit saturating counter        self.last = 0           # one-bit predictor state        self.correct = 0        self.total = 0     def predict(self):        if self.mode == 'one_bit':            return self.last        return 1 if self.state >= 2 else 0     def update(self, actual):        pred = self.predict()        if pred == actual:            self.correct += 1        self.total += 1        if self.mode == 'one_bit':            self.last = actual        else:            if actual == 1:                self.state = min(3, self.state + 1)            else:                self.state = max(0, self.state - 1)     def accuracy(self):        return 100.0 * self.correct / self.total if self.total else 0.0  def run(pattern, length=200):    seq = [pattern[i % len(pattern)] for i in range(length)]    results = {}    for mode in ('one_bit', 'two_bit'):        p = BranchPredictor(mode)        for a in seq:            p.update(a)        results[mode] = p.accuracy()    return results  patterns = {    'always_taken': [1, 1, 1, 1],    'alternating':  [1, 0, 1, 0],    'mostly_taken': [1, 1, 1, 0, 1, 1, 0, 1],    'pseudo_random': [1 if (i * 7) % 11 < 6 else 0 for i in range(64)],} if __name__ == '__main__':    for name, pat in patterns.items():        r = run(pat)        print('%-14s one-bit: %5.1f%%  two-bit: %5.1f%%' % (name, r['one_bit'], r['two_bit']))

1. self.state = 2两位计数器初始化为中等偏不信状态，即「弱跳转」，避免冷启动时过度自信。
2. return 1 if self.state >= 2 else 0预测规则：状态为 S2/S3 时猜「跳」，S0/S1 时猜「不跳」。
3. self.state = min(3, self.state + 1)实际跳转时信心加一档，封顶 3，这就是「饱和」的含义。
4. self.correct += 1每猜对一次就累计，最后除总数就是准确率。
5. seq = [pattern[i % len(pattern)] for i in range(length)]把短模式循环展开成 200 次分支序列，模拟程序反复执行同一段逻辑。
6. 'alternating': [1, 0, 1, 0]交替模式是两位计数器的「克星」，因为它每次刚建立信心就被打脸。
7. print('%-14s ...' % ...)按列对齐输出两种预测器在同一序列上的准确率，方便横向对比。

常见误区

面试题